Ruby左對右遞歸

由於某些原因，Ruby在面對左遞歸時似乎表現更好。例如：Ruby左對右遞歸

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（），我得到不同的結果：

left_recursive_factorial(9001) 
    # => factorial of 9001 

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

我找不到這種行爲作出任何解釋。

似乎有點相關的唯一的東西是關於LL()解析器有左遞歸的問題，我想你可以翻轉它，但我沒有深入挖掘它。

有人可以更詳細地解釋什麼導致左和右遞歸執行不同的方式（通常和特定於Ruby），並且如果您有選擇其中一個或另一個的可能性，爲什麼要選擇它（以及爲什麼還剩下在Ruby中選擇）？

來源

2014-04-30 ndn

似乎ruby在左邊評估乘法的右邊，因此左邊的版本使用[tail遞歸]（https://en.wikipedia.org/wiki/Tail_call），所以它不必添加到堆棧中。 – clcto

@clcto：這看起來不像尾巴呼叫消除。首先，乘法是函數中的最後一個操作，而不是遞歸調用。另一種情況是，如果將數字設置爲9500，則仍然會使堆棧數量減少。 – Chuck

@clcto Ruby絕對是從左到右，而不是從右到左評估操作數和方法參數。此外，操作數的評估順序與是否是尾遞歸無關。乘法必然發生在函數調用之後（因爲你不能乘兩個數字，直到你知道兩個數字），所以該方法不是尾遞歸的，不管哪個數字先被評估。標準的Ruby解釋器無論如何都不會優化尾遞歸。 – sepp2k

好的，我不是任何形式的YARV黑客，但這是我所瞭解的差異。當你調用一個方法時，發送者將方法的參數壓入堆棧，然後被調用的方法將彈出其參數並將其返回值打開。首先遞歸調用，number參數尚未被壓入堆棧，所以每個調用的堆棧佔用的空間稍小。這就是爲什麼你可以從該版本中獲得更多的迭代，但不是更多 - 你正在減少幾個百分比的堆棧使用。

來源

2014-04-30 21:26:01 Chuck

這是有道理的，但我希望得到更詳細的答案。例如，爲什麼python和php似乎無動於衷，而js顯示出類似的行爲。 – ndn

@ndn：這高度依賴於語言實現。例如，Python有遞歸限制，這是解釋器檢查並拒絕遞歸調用（如果已達到）的實際值。你可以用'sys.setrecursionlimit（）'來改變它。在PHP的情況下，我不得不去拿一個反彙編程序，因爲我不知道它是如何工作的。它不會採用推入參數然後調用乘法的堆棧機器方法。相反，它實際上將操作數賦給'*'作爲'MUL'操作碼的操作數，所以這兩個函數之間的唯一區別是'MUL！0，$ 2'和'MUL $ 2，！0'。 – Chuck

Ruby左對右遞歸

回答

相關問題