About
Links
Search
Categories
Archives
Subscribe
Ads
Solution to Exercise 1.11:
A recursive process:
(define (fr n)
(cond ((< n 3) n)
(else (+ (fr (- n 1))
(* 2 (fr (- n 2)))
(* 3 (fr (- n 3)))))))An iterative one:
(define (fi n)
(define (f-iter i f-i-1 f-i-2 f-i-3)
(if (> i n)
f-i-1
(f-iter (+ i 1)
(+ f-i-1 (* 2 f-i-2) (* 3 f-i-3))
f-i-1
f-i-2)))
(if (< n 3)
n
(f-iter 3 2 1 0)))Posted by Ken Dyck in Programming
Another iterative version:
(define (f n)
(define (iter a b c i)
(if (= i 0)
a
(iter b c (+ a b c) (- i 1))))
(iter 0 1 2 n))
Thanks for posting your solutions. It’s very useful to compare notes. Any chance you’ll post solutions for chapter 2?
The iterative version patterned after the book’s iterative Fibonacci procedure.
(define (f n)
(define (f-iter a b c count)
(if (= count 0)
c
(f-iter (+
a
(* 2 b)
(* 3 c))
a b (- count 1))))
(f-iter 2 1 0 n))
Hi! I was hoping someone might be able to explain in a bit more detail why the iterative version(s) posted work(s)? I’m just having a bit of trouble wrapping my head around the code. Thanks!
Sure, Alec.
The iterative procedure starts at f(3) and works its way up to f(n). It does this by storing the previous three results, f(i-1), f(i-2), and f(i-3), in parameters. Every iteration it calculates a new f(i) from the previous results (becoming f(i-1) for the next iteration), increments i, and shifts the previous f(i-1) to f(i-2) and the previous f(i-2) to f(i-3). It finally stops when i > n, at which point i-1 == n, so it returns the current f(i-1).
Hope this helps.
It should be noted that the solution posted by Boris at the first comment is incorrect — He probably meant something like the one posted by Jonathan.
And indeed, your solutions are handy!
I think Jonathan’s version is also wrong:
When count=0, it should return a instead of c
Will is wrong. Jonathan is right. When count = 0, that’s when n = 0, which means f(0) = 0 ought to be returned. Recall the definition: (f n) calls (f-iter a b c count). Notice that (f 0) calls (f-iter 2 1 0 0) which should yield 0, not 2. So c, not a.
Jonathan is wrong. His f doesn’t work for negative n, but Ken’s one does.
Jonathan’s version is right if you are following along with the book. The book’s fibonacci procedure does not account for negative numbers, so in the spirit of the book it is correct. At this point in the book, the idea isn’t so much being defensive about the arguments, but the shape and evolution of the procedure.
[...] after a long day at work), so I cheated a bit and looked it up on the internet and found a solution here. So in order to come up with my own solution, I decided to implement a solution using the collector [...]
Just in case you weren’t bored with it yet….
; f2(12) = 10661 in 11 calls
; iterative
(define (f2 n)
(define (f-iter a b c n)
(cond ((< n 2) n)
((= n 2) c)
(else (f-iter b c (+ c (* 2 b) (* 3 a)) (- n 1)))))
(f-iter 0 1 2 n))