Recursive And Iterative Algorithms on Recursive Functions

Recursive functions get their name from the fact that they’re defined on terms of themselves, that is, they call themselves inside their definition.

But even though some function might be recursive the algorithm it implements by be effectively iterative.

Let’s see how this work while implementing factorial in code, here will be using Lisp but the concept should apply to pretty much all languages.

(define (fact n)
  (if (<= n 1)
      1
      (* n (fact (- n 1)))))

Here we check if n is less than or equal to 1, if so we return 1, otherwise we return n times the result of calling fact with n minus 1.

Let’s see what shape each call to fact produces:

(fact 4)
(* 4 (fact 3))
(* 4 (* 3 (fact 2)))
(* 4 (* 3 (* 2 (fact 1))))
(* 4 (* 3 (* 2 1))
(* 4 (* 3 2))
(* 4 6)
24

On each iteration we defer some computation to do afterwards, we connot compute them without first evaluating what the next value of fact is.

Let’s contrast it with this other implementation of factorial:

(define (fact acc n)
  (if (<= n 1)
      acc
      (fact (* acc n) (- n 1))))

Here we check if n is less than or equal to 1, if so we return acc (standing for accumulator), otherwise we call fact again passing in acc times n and n minus 1.

Let’s see what shape each call to fact this implementation produces:

(fact 1 4)
(fact 4 3)
(fact 12 2)
(fact 24 1)
24

We are no longer deferring some computation to do afterwards, we only need the arguments passed to fact in order to compute the next value.

So even though both functions are recursive in nature, that is, they call themselves in their definitions, they produce very different shapes.

Tail Position

On our second implementation calls itself the tail position, that is, as the last action that procedure will execute. We no longer need to remember to do those deferred computations, all we need is available through the procedure’s parameters.

Our first implementation, in the other hand, doesn’t call itself as the last action, it’s called inside a multiplication operation. We cannot possibly compute the value of the multiplication operation without evaluating subsequent calls to fact, thus we build this chain of deffered computations.

Space and Time

Our first implementation is said to be linear in time, the time it takes is linear to its argument n. It’s also linear in space, it grows more depending on the value of n.

The second implementation is also linear in time but it’s constant on space, it doesn’t need to grow as much.