Ruby left vs right ricorsione

Question

Per qualche motivo, Ruby sembra funzionare meglio quando si trova di fronte alla ricorsione a sinistra. Per esempio:

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 

Quando chiamo questi metodi con un valore di oltre 9000() ottengo risultati diversi:

left_recursive_factorial(9001) 
    # => factorial of 9001 

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

non ho potuto trovare alcuna spiegazione per questo comportamento.

L'unica cosa che sembrava in qualche modo correlata era circa i parser LL() che hanno problemi con la ricorsione a sinistra e credo che si possa capovolgere, ma non ho scavato molto dentro.

Qualcuno potrebbe spiegare un po 'più in dettaglio ciò che causa la ricorsione destra e quella sinistra in modo diverso (in generale e in Ruby in particolare) e se si ha la possibilità di scegliere l'uno o l'altro perché lo si dovrebbe scegliere (e perché è stato lasciato scelto in Ruby)?

Answer 1

OK, io non sono un hacker YARV di alcun tipo, ma ecco la differenza come ho capito. Quando chiami un metodo, il mittente invia gli argomenti del metodo nello stack, quindi il metodo chiamato espelle i suoi argomenti e ne attiva il valore restituito. Con la chiamata ricorsiva, l'argomento number non è stato ancora inserito nello stack, quindi lo stack di ogni chiamata occupa uno spazio leggermente inferiore. Questo è il motivo per cui è possibile ottenere alcune ripetizioni in più rispetto a quella versione, ma non in modo drastico in più: si sta osservando una riduzione di alcune percentuali nell'utilizzo dello stack.