Tail recursion: Difference between revisions

Revision as of 11:47, 6 December 2008

Revision as of 00:54, 21 December 2008

Line 17:

<source lang="scheme">

(define;; (factorial n)number -> number

;; to calculate the product of all non-negative integers

(define (fac-times n acc)

;; less than or (ifequal (=to n 0).

(define factorial

acc

(lambda (n)

(fac-times (- n 1) (* acc n))))

(if (<and (integer? n) (>= n 0))

(displaylet fact ([i n] "Wrong[acc argument!"1])

(fac-timesif n(zero? 1))i)

acc

(fac-times (-fact n(sub1 1i) (* acc ni))))

(assertion-violation

'factorial "invalid argument" n))))

</source>

As you can see, the inner procedure <code>fac-timesfact</code> calls itself ''last'' in the control flow. This allows an [[interpreter (computer software)|interpreter]] or [[compiler]] to reorganize the execution which would ordinarily look like this:

call factorial (3)

call fac-timesfact (3 1)

call fac-timesfact (2 3)

call fac-timesfact (1 6)

call fac-timesfact (0 6)

return 6

return 6

Line 43 ⟶ 47:

call factorial (3)

replace arguments with (3 1), jump to "fac-timesfact"

replace arguments with (2 3), jump to "fac-timesfact"

replace arguments with (1 6), jump to "fac-timesfact"

replace arguments with (0 6), jump to "fac-timesfact"

return 6