SICP processo ricorsivo vs processo iterativo: utilizzando una procedura ricorsiva per generare un processo iterativo

Question

in SICP Section 1.2.1 L'autore dà un tale esempio di codice riportato di seguito mostra come utilizzare processo iterativo per risolvere il problema fattoriale:

(define (factorial n) 
    (fact-iter 1 1 n)) 
(define (fact-iter product counter max-count) 
    (if (> counter max-count) 
     product 
     (fact-iter (* counter product) 
       (+ counter 1) 
       max-count))) 

e dire "Può sembrare inquietante che ci riferiamo a una procedura ricorsiva come il fact-iter che genera un processo iterativo. Tuttavia, il processo è realmente iterativo: il suo stato è catturato completamente dalle sue tre variabili di stato e un interprete necessita tenere traccia di solo tre variabili al fine di eseguire il processo. "

Non capisco cosa significhi l'autore. Qual è la differenza tra una procedura ricorsiva e un processo ricorsivo? E perché ha detto la procedura ricorsiva di seguito generando un processo iterativo?

Answer 1

A processo ricorsivo deve mantenere lo stato del chiamante mentre è in corso la chiamata ricorsiva. Per esempio, se hai scritto:

(define (fact-recurse n) 
    (if (< n 2) 
     1 
     (* n (fact-recurse (- n 1))))) 

la chiamata esterna deve ricordare n e attendere la chiamata interiore per tornare prima di poter eseguire la moltiplicazione. Se chiamate il numero (fact-recurse 10) ci saranno 9 moltiplicazioni impilate in attesa quando la funzione raggiunge la fine della sua ricorsione.

Ma in un processo iterativo , lo stato precedente può essere scartato. Questo è possibile nel codice di esempio perché tutte le informazioni necessarie sono passate come parametri nella chiamata ricorsiva. Le variabili nella chiamata esterna non sono più necessarie, quindi nulla deve essere tenuto in pila.

Poiché i parametri della chiamata esterna non sono più necessari, la chiamata ricorsiva può essere tradotto in assegnazioni:

(set! product (* counter product)) 
(set! counter (+ counter 1) 
(set! max-count max-count) 

e poi salta solo per l'inizio della procedura.