Rekursja ogona w R

Question

Wydaje mi się, że źle rozumiem rekursję ogona; zgodnie z to this stackoverflow question R nie obsługuje rekursji ogonowej. Jednakże, rozważmy następujące funkcje obliczyć n-tą liczbę Fibonacciego:

wersja iteracyjna:

Fibo <- function(n){ 
    a <- 0 
    b <- 1 
    for (i in 1:n){ 
     temp <- b 
     b <- a 
     a <- a + temp 
    } 
    return(a) 
} 

„Naive” rekurencyjna wersja:

FiboRecur <- function(n){ 
    if (n == 0 || n == 1){ 
     return(n) 
    } else { 
     return(FiboRecur(n-1) + FiboRecur(n-2)) 
     } 
} 

I wreszcie przykład stwierdziliśmy, że powinny być wywołanie rekurencyjne:

FiboRecurTail <- function(n){ 
    fib_help <- function(a, b, n){ 
     if(n > 0){ 
      return(fib_help(b, a+b, n-1)) 
     } else { 
      return(a) 
     } 
    } 
    return(fib_help(0, 1, n)) 
} 

Teraz, jeśli spojrzymy na ślad s gdy funkcje te nazywane są, o to co mamy:

Fibo(25) 
trace: Fibo(25) 
[1] 75025 


trace(FiboRecur) 
FiboRecur(25) 
Thousands of calls to FiboRecur and takes a lot of time to run 

FiboRecurTail(25) 
trace: FiboRecurTail(25) 
[1] 75025 

W przypadkach Fibo(25) i FiboRecurTail(25), odpowiedź jest wyświetlana natychmiast i tylko jedno połączenie jest wykonane. W przypadku FiboRecur(25) wykonano tysiące połączeń, które trwają kilka sekund przed wyświetleniem wyniku.

Możemy również przyjrzeć się z czasów pracy przy użyciu funkcji benchmark z pakietu rbenchmark:

benchmark(Fibo(30), FiboRecur(30), FiboRecurTail(30), replications = 5) 
       test replications elapsed relative user.self sys.self user.child sys.child 
1   Fibo(30)   5 0.00  NA  0.000  0   0   0 
2  FiboRecur(30)   5 13.79  NA 13.792  0   0   0 
3 FiboRecurTail(30)   5 0.00  NA  0.000  0   0   0 

Więc jeśli R nie obsługuje ogon rekursji, co dzieje się w FiboRecurTail(25) który sprawia, że ​​biegać tak szybko jako wersja iteracyjna, podczas gdy "naiwna" funkcja rekursywna działa jak melasa? Czy raczej R obsługuje rekursję ogonową, ale nie optymalizuje "naiwnej" rekursywnej wersji funkcji wywoływanej zwrotnie, jak inne języki programowania (na przykład Haskell)? Rozumiem to z tego post in R's mailing list.

Byłbym bardzo wdzięczny, gdyby ktoś rzucił w to trochę światła. Dzięki!

Answer 1

Różnica polega na tym, że dla każdej rekurencji FiboRecur wywołuje się dwukrotnie. W ciągu FiboRecurTail, fib_help wywołuje się tylko raz.

Dzięki temu masz o wiele więcej funkcji związanych z tym pierwszym. W przypadku FiboRecurTail(25) masz głębokość rekursji ~ 25 połączeń. FiboRecur(25) daje 242,785 wywołań funkcji (w tym pierwsze).

Nie zwlekałem z żadną z procedur, ale zwróć uwagę, że dla obu szybszych procedur wyświetlany jest numer 0.00. Powinieneś zauważyć pewną różnicę przy wyższej wartości wejściowej, ale zauważ, że Fibo iteruje dokładnie tak samo, jak FiboRecurTail recurses.

Answer 2

W podejściu rekursywnym naive wielokrotnie obliczano wiele wartości. Na przykład, gdy obliczysz FiboRecur(30), obliczysz FiboRecur(29) i FiboRecur(28), a każde z tych dwóch połączeń będzie niezależne. I w FiboRecur(29) ponownie obliczysz FiboRecur(28) i , mimo że FiboRecur(28) został już obliczony gdzie indziej, jak powyżej. I dzieje się tak na każdym etapie rekursji. Lub po prostu, dla każdego wzrostu n, wysiłek obliczeniowy prawie podwaja się, ale oczywiście, w rzeczywistości powinno być tak proste, jak dodać dwie ostatnie obliczone liczby razem.

Trochę podsumowanie FiboRecur(4): FiboRecur(0) oblicza się dwa razy, FiboRecur(1) oblicza trzykrotnie FiboRecur(2) oblicza się dwa razy i FiboRecur(3) jest obliczana raz. Te pierwsze trzy powinny być obliczane raz i przechowywane gdzieś, aby można było wyodrębnić wartości, gdy są potrzebne. I dlatego widzisz tyle wywołań funkcji, mimo że nie jest to duża liczba.

w ogonie rekurencyjnego wersji jednak co wcześniej obliczone wartości są przekazywane do następnego etapu przez a + b parametr, który pozwala uniknąć liczne powtarzalne obliczenia jak w naiwnych wersji rekurencyjne, a zatem bardziej efektywny.