CSE1729: Introduction to Principles of Programming
Iterative and Recursive processes
Robert McCartney
117
Recursive vs. iterative: “Recursive”
Consider the familiar factorial function:
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
✤
(6factorial 3)
3*
2(f
actorial 2)
✤
Let’s trace the evaluation of (fact 3). Note how the multiplications
(* 3 ☐),(* 2 ☐), …
are pending while the recursive calls
complete.
2*
1(f
actorial 1)
1*
(1factorial 0)
118
Recursion vs. iteration: “Iteration”
Consider the sqrt-converge function we defined for extracting square roots:
✤
(define (sqrt-converge a b)
(let ((avg (/ (+ a b) 2)))
(if (< (abs (- a b)) .000001) a
(if (> (square avg) x)
(sqrt-converge a avg)
(sqrt-converge avg b)))))
(sqrt-convae”rge a b)
✤
Note that a call to (sqrt-converge a b) typically generates a call to (sqrt-converge a’ b’). In fact, the result of (sqrt-converge a b) is simply the the result of (sqrt-converge a’ b’) without further processing or pending operations. This is called tail recursion.
(sqrt-convear”ge a’ b’)
(sqrt-convear”ge a” b”)
119
Tail recursion requires no memory of pending operations
✤
In general, recursion requires memory of the local state of the calling procedure (including local variables and pending operations) in order to compute a final value.
Tail recursion (or iteration) does not require any such memory. The value of the calling process is simply the value of the subprocess. The caller’s environment can be discarded.
3*
2
2*
1
✤
(a,b)
(a’,b’)
(a”,b”)
1*
1
120
Conversion to tail recursion typically requires passing state
Converting a function definition to a tail recursive call can speed- up computation and significantly reduce memory use.
Recall the original version of factorial:
(define (fact n)
(if (= n 0) 1
✤
✤
✤
Idea: Let’s send the pending operation along to the subprocess. The subprocess is responsible for: computing (n-1) factorial and multiplying the result by n.
Pending
(* n
(fact (- n 1)))))
121
This results in…
New definition: function that computes a factorial and multiplies by a second “accumulator” argument.
(define (fact-accumulate n a)
(if (= n 0) a
(fact-accumulate (- n 1)
(* n a)))
Returns: (factorial of n) x (a)
✤
122
Wrapping this to conceal the internal machinery
(define (fact-tr n)
(define (fact-accumulate m a)
Nothing pending
(if (= m 0) a
(fact-accumulate (- m 1)
(fact-accumulate n 1))
•Now this is tail recursive.
•Why is accumulate an appropriate name for the second
argument?
(* m a))))
123
Another example
Consider computing the sum of the first n numbers in SCHEME.
✤
✤
Note that
1 + . . . + n = n + 1 + . . . + (n 1) | {z } | {z }
X X
n
i
i=1
n 1 i
i=1
✤ And thus: > (define (number-sum n) (if (= n 0)
0
(+ n (number-sum (- n 1)))))
> (number-sum 10)
55
124
Recursive or iterative?
Recursive, as it needs to remember pending operations.
(define (number-sum n)
(if (= n 0)
0
(+ n (number-sum (- n 1)))))
✤
125
Can we make it iterative?
What sort of state do we need to bring along?
(define (sum-iter n a)
(if (= n 0)
a
(sum-iter (- n 1)(+ a n))))
(sum-iter 10 0) => 55
✤
126
Can we make it iterative?
Package the iterative function to hide the extra parameter
(define (sum-i n)
(define (sum-iter n a)
(if (= n 0) a
(sum-iter (- n 1)(+ a n))))
(sum-iter n 0))
✤
127
Another example:
The Fibonacci numbers
The Fibonacci numbe8rs are defined by the rule:
>< 0 i f n = 0 , F n = >: 1 i f n = 1 ,
Fn 1 + Fn 2 if n > 1
Note, then, that the sequence F0, F1, F2, … is
✤
✤
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … each is the sum of the previous two.
128
The Fibonacci numbers in SCHEME
As with the factorial function, we can naturally capture this definition in SCHEME.
(define (fib n)
(cond ((= n 0) 0)
✤
✤
Notice, as with factorial, how closely the SCHEME definition can mirror the mathematical definition.
) )
((= n 1) 1)
((> n 1) (+ (fib (- n 1))
(fib (- n 2))))
129
The Fibonacci evaluation tree
• The Fibonacci function gives rise to an “evaluation tree” as shown. Here each node returns the sum of the value of its children.
• Note that some “sub”- problems are evaluated many times.
• Question: How many times is (f 1) evaluated, in total?
3
(f 4)
2
(f 3)
1
(f 2)
11 10
(f2) (f1) (f1) (f0)
1
0
(f 1) (f 0)
130
Recursive or iterative?
Recursive, as it needs to remember pending operations.
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else
(+ (fib (- n 1))(fib (- n 2))))))
✤
131
Can we make it into an iterative process?
✤
If you were calculating Fibonacci numbers by hand, how would you do it?
132
What state do we need to compute fib(n)?
✤
8>< 0 F n = >: 1
Fn 1 + Fn 2 We need the previous 2 fibs.
i f n = 0 , i f n = 1 , if n > 1
133
Let’s bring them along!
Like with sum, we use parameters:
(define (fib-iter n a b)
(if (= n 0)
a
(fib-iter (- n 1) b (+ a b))))
(fib-iter n 0 1) => same as (fib n)
✤
134
Tracing (fib-iter 5 0 1)
Using this code:
(define (fib-iter n a b)
(if (= n 0)
a
(fib-iter (- n 1)
✤
b
(+ a b))))
(fib-iter 5 0 1)
(fib-iter 4 1 1)
(fib-iter 3 1 2)
(fib-iter 2 2 3)
(fib-iter 1 3 5)
(fib-iter 0 5 8)
5
(fib-iter n 0 1)
135
Package fib-iter:
✤
(define (fib-i n)
(define (fib-iter n a b)
(if (= n 0) a
(fib-iter (- n 1) b (+ a b))))
(fib-iter n 0 1))
136
Time and space savings?
3
(f 4)
(fib-iter 4 1 1)
(fib-iter 3 1 2)
(fib-iter 2 2 3)
(fib-iter 1 3 5)
(fib-iter 0 5 8)
2
(f 3) (f 2)
110
(f2) (f1) (f1) (f0)
1
(f 1) (f 0)
1
•
1
0
137