루비 왼쪽 대 오른쪽 재귀

Question

루비는 왼쪽 재귀를 마주 칠 때 더 나은 성능을 보이는 것으로 나타났습니다. 예를 들면 : 나는이 문제에 대한 설명을 찾을 수 없습니다

left_recursive_factorial(9001) 
    # => factorial of 9001 

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

:

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 

내가 9000 이상 값이 방법() 나는 다른 결과를 얻을 전화

.

약간의 관련이있는 유일한 것은 왼쪽 재귀에 문제가있는 파서 LL()이었고 주위를 뒤집을 수는 있지만 그다지 파고 들지 않았습니다.

왼쪽과 오른쪽 재귀가 다르게 (일반적으로 Ruby에서) 반복적으로 수행되는 원인에 대해 조금 더 자세히 설명해 주시겠습니까? 하나를 선택하거나 다른 것을 선택할 가능성이있는 이유는 무엇입니까? (그리고 왜 남았습니까? 루비에서 선택)?

Answer 1

좋아, 나는 YARV 해커가 아니지만 여기 이해할 수있는 차이가있다. 메소드를 호출하면, 송신자는 메소드의 인수를 스택에 푸시합니다. 호출 된 메소드는 인수를 해제하고 리턴 값을 push합니다. 재귀 호출을 먼저 수행하면 number 인수가 아직 스택에 푸시되지 않았으므로 각 호출 스택에 약간의 공간이 필요합니다. 이것이 그 버전에서 반복을 몇 번 더 얻을 수 있지만 그 이상은 아닙니다. 스택 사용량을 몇 % 줄이려고합니다.