Tail Recursion with Scheme

Linear Recursion and Iteration

Recursion is a method where the solution to a problem depends on the solution to the smaller instances of the same problem (or simply: when a procedure or function calls itself it's called a recursion).

Now, lets see what is a linear recursive process, let me demonstrate it with the following example(in Scheme)

;recFactorial.scm

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

Using the above function if we try to calculate the factorial of a number say 4, then it proceeds as follows..

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

Here we can see that the amount of information needed to keep track of the operations increases linearly with n. Thus such a process is called linear recursive process.

An important thing to distinguish here is the recursive process and a recursive procedure.
Recursive procedure refers to the syntactic fact that the procedure definition refers to the procedure itself. But with a recursive process we refer to the evolution (at each step) of the process and not about the syntax of how a procedure is written.

An iterative counterpart for the above example can be given as ..

;iterFactorial.scm
(define (factorial n)
  (fact 1 1 n))

(define (fact product count max-count)
  (if (> count max-count)
      product
      (fact (* count product)
                 (+ count 1)
                 max-count)))

Now using the above definition the execution proceeds as follows..

(factorial 5)
(fact   1 1 5)
(fact   1 2 5)
(fact   2 3 5)
(fact   6 4 5)
(fact  24 5 5)
(fact 120 6 5)
120

We can see that a fixed number of variables is enough to store the information needed for the operations. Such a process along with a fixed rule to update these state variables is called an iterative process. Also the number of steps grows linearly with n, hence called a linear iterative process.

Tail Recursion

A tail call is a procedure call that happens inside another procedure as a final action.

During such a tail call, if the called procedure is same as the calling procedure then the procedure is said to be tail recursive.

This property is significant as the tail-recursive implementation can be done without adding a stack frame to the call stack (ie. an iterative process will be executed in constant space even if the tail-call is a recursive procedure).

In the above examples recFactorial.scm is a recursive procedure whereas the iterFactorial.scm is a tail-recursive one (since the variables count,product are updated before calling fact() again).

Here is another example, suppose we want to define a procedure sum(n) which returns the sum of n numbers (ie. sum(5) = 5+4+3+2+1=15)

The recursive procedure can be given as.. 

(define (recSum n)
   (if (= n 1)
     n
      (+ n (recSum (- n 1)))))

If  we call (recSum 5), process proceeds as follows..

(recSum 5)
(+ 5 (recSum 4))
(+ 5 (+ 4 (recSum 3)))
(+ 5 (+ 4 (+ 3 (recSum 2))))
(+ 5 (+ 4 (+ 3 (+ 2 (recSum 1)))))
(+ 5 (+ 4 (+ 3 (+ 2 1))))
15

Now, the tail-recursive procedure can be given as..

(define (tailSum n total)
    (if (= n 0)
      total
        (tailSum (- n 1) (+ total n))))

(tailSum 5) proceeds as follows..

(tailSum 5 0)
(tailSum 4 5)
(tailSum 3 9)
(tailSum 2 12)
(tailSum 1 14)
(tailSum 0 15)
15

In tail-recursive example the variables n,total are updated before calling tailSum again. It is also evident that tail-recursive implementation uses only constant space.

Tail-recursion is an important property provided by certain language standards, like in functional programming languages (eg: Scheme). (more)