Ruby left vs right recursion

Question

Z jakiegoś powodu Ruby wydaje się lepiej spisywać się w obliczu lewej rekursji. Na przykład:

def left_recursive_factorial(number) 
    return 1 if number.zero? 
    left_recursive_factorial(number.pred) * number 
end 

def right_recursive_factorial(number) 
    return 1 if number.zero? 
    number * right_recursive_factorial(number.pred) 
end 

Kiedy ja nazywam te metody o wartości ponad 9000() uzyskać różne wyniki:

left_recursive_factorial(9001) 
    # => factorial of 9001 

right_recursive_factorial(9001) 
    # => SystemStackError: stack level too deep 
    # from (pry):6:in `right_recursive_factorial' 

nie mogłem znaleźć żadnego wytłumaczenia dla takiego zachowania.

Jedyną rzeczą, która wydawała się być nieco spokrewniona, były parsery LL() mające problemy z lewą rekursją i myślę, że można je odwrócić, ale nie włożyłem w to wiele.

Czy ktoś mógłby dokładniej wyjaśnić, co powoduje, że lewe i prawe rekursje działają inaczej (ogólnie iw Ruby) i czy masz możliwość wyboru jednego lub drugiego, dlaczego wybrałbyś (i dlaczego zostało wybrany w Ruby)?

Answer 1

OK, nie jestem hakerem YARV, ale tutaj jest różnica, jak rozumiem. Kiedy wywołujesz metodę, nadawca popycha argumenty metody na stos, wtedy wywoływana metoda wyrzuca argumenty i przesuwa wartość zwracaną. Po pierwszym wywołaniu rekursywnym argument number nie został jeszcze wepchnięty na stos, więc stos każdego połączenia zajmuje nieco mniej miejsca. Dlatego możesz uzyskać kilka iteracji z tej wersji, ale nie drastycznie więcej - patrzysz na zmniejszenie zużycia stosu o kilka procent.