Procedura ta nie ma wady poprzedniej metody – oblicza końcową wartość bez żadnego nadmiaru w wynikach pośrednich. Niestety, płaci się za to ogromnym kosztem obliczeń. Funkcja przestaje wywoływać samą siebie, dopiero gdy zwraca wartość 1 – to oznacza, że obliczenie wartości wymaga co najmniej wywołań funkcji (bezpośrednich i pośrednich). Złożoność czasowa jest więc nie mniejsza niż wartość funkcji: (zobacz Notacja dużego O). Równocześnie, jeśli tylko początkowa wartość nie jest równa 0 ani co najmniej jedna ścieżka rekursji kończy się na wywołaniu WspNewtonaRek(1, 0) albo WspNewtonaRek(1, 1). Ścieżka ta prowadzi przez poziomów wywołań, w których parametr był kolejno zmniejszany aż do jedności. Głębokość rekurencji, a zatem złożoność pamięciowa jest więc ściśle liniowa i to w bardzo wrażliwym obszarze stosu.

Kolejnym krokiem pozwalającym na przyspieszenie obliczeń jest wykorzystanie programowania dynamicznego – można w tabeli przechowywać wyniki obliczeń poszczególnych kroków rekurencji, aby skrócić czas potrzebny na znalezienie danej wartości symbolu.