Editing Tail call (section)

==Example programs==
The following program is an example in [[Scheme (programming language)|Scheme]]:<ref name="sicp">{{cite book|last1=Sussman|first1=G. J.|last2=Abelson|first2=Hal|title=Structure and Interpretation of Computer Programs|date=1984|publisher=MIT Press|location=Cambridge, MA|isbn=0-262-01077-1|url=https://archive.org/details/structureinterpr00abel}}</ref>

<syntaxhighlight lang="scheme">
;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
 (if (= n 0)
    1
    (* n (factorial (- n 1)))))
</syntaxhighlight>

This is not written in a tail-recursive style, because the multiplication function ("*") is in the tail position. This can be compared to:

<syntaxhighlight lang="scheme">
;; factorial : number -> number
;; to calculate the product of all positive
;; integers less than or equal to n.
(define (factorial n)
  (fact-iter 1 n))
(define (fact-iter product n)
  (if (= n 0)
      product
      (fact-iter (* product n)
                 (- n 1))))
</syntaxhighlight>

This program assumes [[Evaluation strategy#Applicative order|applicative-order]] evaluation. The inner procedure <code>fact-iter</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:<ref name="sicp" />

   call factorial (4)
    call fact-iter (1 4)
     call fact-iter (4 3)
      call fact-iter (12 2)
       call fact-iter (24 1)
       return 24
      return 24
     return 24
    return 24
   return 24

into the more [[Algorithmic efficiency|efficient]] variant, in terms of both space and time:

   call factorial (4)
    call fact-iter (1 4)
    replace arguments with (4 3)
    replace arguments with (12 2)
    replace arguments with (24 1)
    return 24
   return 24

This reorganization saves space because no state except for the calling function's address needs to be saved, either on the stack or on the heap, and the call stack frame for <code>fact-iter</code> is reused for the intermediate results storage. This also means that the programmer need not worry about running out of stack or heap space for extremely deep recursions. In typical implementations, the tail-recursive variant will be substantially faster than the other variant, but only by a constant factor.

Some programmers working in functional languages will rewrite recursive code to be tail recursive so they can take advantage of this feature. This often requires addition of an "accumulator" argument (<code>product</code> in the above example) to the function.