To begin exploring how procedures use space, consider the following procedure:
(define (factorial n)
(if (= n 0)
1
(* n (factorial ( n 1)))))
If we were to evaluate (factorial 5)
by hand, writing out each step we get the following:
start with (factorial 5)
replaced by (* 5 (factorial 4))
replaced by (* 5 (* 4 (factorial 3)))
replaced by (* 5 (* 4 (* 3 (factorial 2))))
replaced by (* 5 (* 4 (* 3 (* 2 (factorial 1)))))
replaced by (* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))))
replaced by (* 5 (* 4 (* 3 (* 2 (* 1 1)))))
replaced by (* 5 (* 4 (* 3 (* 2 1))))
replaced by (* 5 (* 4 (* 3 2)))
replaced by (* 5 (* 4 6))
replaced by (* 5 24)
replaced by 120
Each line describes a new step of the computationwhat we need to remember at that time step in order to continue the evaluation. Here is the key observation: if we chose a large enough input for factorial, say 10000, then at some step, we wouldn't be able fit the entire line in our minds.
Computers evaluate procedure calls in the same way. Each function call is stored in the computer's working memoryâ€”a place to store intermediary, incomplete computations. This space is finite and can be overflowed. The important thing to remember is that this problem only occurs on very large inputs. The "working memory" is called the "call stack". When that space is used up by a program, it's called a "stack overflow".
Is there a way to fix factorial such that it does not force the computer to run out of space on large inputs? Consider the following:
(define (factorial n)
(factiter 1 1 n))
(define (factiter product counter maxcount)
(if (> counter maxcount)
product
(factiter (* counter product)
(+ counter 1)
maxcount)))
Test your understanding. Why must we say (> counter maxcount)
? What happens if we were to do (factiter 1 1 3)
?
Now if we were to diagram (factorial 5)
with the code above, we would get the following:
start with (factorial 5)
replaced by (factiter 1 1 5)
replaced by (factiter 1 2 5)
replaced by (factiter 2 3 5)
replaced by (factiter 6 4 5)
replaced by (factiter 24 5 5)
replaced by (factiter 120 6 5)
replaced by 120
In this case, the amount of incomplete computations we had to keep in our minds as we carried through the evaluation didn't grow at each step. We instead carried the incomplete answer to the computation through the arguments, which saves space. In other words, the complete state of the computation is kept in the arguments to the recursive callcalling (factiter 2 3 5)
would produce the same result as (factiter 1 1 5)
, whereas calling (factorial 3)
would produce a different result from calling (factorial 5)
.
Note that this iterative process still uses Recursion, but this is different than saying it is a recursive process.
Looking at these functions side by side, we can identify how these two procedures relate.
Recursive  Iterative 



Important observations on the differences:
product
in the iterative version (1). Notice that calling iterative (factorial 1)
causes the base case to be triggered in factiter
, and 1 is returned.*
procedure is called outside of the recursive call. In the iterative version, all of the arguments are transformed before (or inside of) the recursive call. I.e., (* counter product)
happens first, and then the recursive call gets made. This is the key to why the Iterative version is more space efficent.In formal terms, the Iterative factorial
is more space efficent because the Racket interpreter impliements Tail Call Elimination. In other programming languages and other interpreters that aren't Tail Call optimized, the Recursive and Iterative versions use the same amount of space when run. So why do we care?
In order to write a tailrecursive procedure, here are a few tips.
factorial
, that was product
.factorial
, that was 1, 1, and n
, in (factiter 1 1 n)
.butfirst
'd, etc.) before the recursive call is made.The following questions are for your understanding. You will not be graded. You can check your answers with a staff member.
factorial
keeps track of three things in factiter
. What were those things? Could we rewrite factorial
yet again in order to only keep track of two things?factorial
?