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 computation--what 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) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count)))
Test your understanding. Why must we say
(> counter max-count)? What happens if we were to do
(fact-iter 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 (fact-iter 1 1 5) replaced by (fact-iter 1 2 5) replaced by (fact-iter 2 3 5) replaced by (fact-iter 6 4 5) replaced by (fact-iter 24 5 5) replaced by (fact-iter 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 call--calling
(fact-iter 2 3 5) would produce the same result as
(fact-iter 1 1 5), whereas calling
(factorial 3) would produce a different result from calling
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.
Important observations on the differences:
productin the iterative version (1). Notice that calling iterative
(factorial 1)causes the base case to be triggered in
fact-iter, 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 tail-recursive procedure, here are a few tips.
factorial, that was
factorial, that was 1, 1, and
(fact-iter 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.
factorialkeeps track of three things in
fact-iter. What were those things? Could we rewrite
factorialyet again in order to only keep track of two things?