SICP: Exercise 1.11.

[.]

Hello,

I've got stuck with another exercise.

"A function f is defined by the rule that f(n) = n if n<3 and f(n) =
f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that
computes f by means of a recursive process. Write a procedure that
computes f by means of an iterative process." [1]

Could you explain this solution? [2]

(define (f n)
(define (iter a b c count)
(if (= count 0)
a
(iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))
(iter 0 1 2 n))

I understand how iteration works (in general), but I don't understand
the last line.
Why do we pass 0 1 2 to a b c?
Where did we get these numbers?

[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2
[2] http://community.schemewiki.org/?sicp-ex-1.11

P.S. Is it OK to post SICP-related questions on this list? Could you
suggest a better place for such questions?

[Jussi Piitulainen]

. writes:

> I've got stuck with another exercise.
>
> "A function f is defined by the rule that f(n) = n if n<3 and f(n) =
> f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that
> computes f by means of a recursive process. Write a procedure that
> computes f by means of an iterative process." [1]
>
> Could you explain this solution? [2]
>
> (define (f n)
> (define (iter a b c count)
> (if (= count 0)
> a
> (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))
> (iter 0 1 2 n))
>
> I understand how iteration works (in general), but I don't understand
> the last line.
> Why do we pass 0 1 2 to a b c?
> Where did we get these numbers?

They are f(0), f(1), and f(2). They come from f(n) = n if n < 3.

> [1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2
> [2] http://community.schemewiki.org/?sicp-ex-1.11
>
> P.S. Is it OK to post SICP-related questions on this list? Could you
> suggest a better place for such questions?

It's OK. We appreciate that you are making an effort with SICP. You
might find more people somewhere else nowadays. I don't quite know
where.

[raof01]

It seems that you get clear idea about iterative procedure and tail-recursion. You cannot get right answer because you got the wrong base case. The base case should be:
if n < 3, return n
if count = 3, return result: the base case where result is 4
if count > 3, calculate the result with iterator.

So it should be:
(define (f-i n)
(let iter ((fn 4) (fn-1 2) (fn-2 1) (fn-3 0) (i n))
(cond ((< n 3) n)
((= i 3) fn)
(else
(iter (+ fn (* 2 fn-1) (* 3 fn-2))
fn
fn-1
fn-2
(- i 1))))))

Or you can just use "do" to do the job for you:
(define (f-do n)
(if (< n 3)
n
(do ((i n (- i 1))
(fn-3 0 fn-2)
(fn-2 1 fn-1)
(fn-1 2 fn)
(fn 4 (+ fn (* 2 fn-1) (* 3 fn-2))))
((= i 3) fn))))

[.]

> > (define (f n)
> >    (define (iter a b c count)
> >      (if (= count 0)
> >        a
> >        (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))
> >    (iter 0 1 2 n))
>

> They are f(0), f(1), and f(2). They come from f(n) = n if n < 3.

I see. Thank you.

There is another issue.
I don't know how to design a recursive procedure (which generates a
recursive or an iterative process).

For example:
It's not clear (for me) from the text of the exercise that we should
use the following to calculate the third operand.

(+ c (* 2 b) (* 3 a))

Another example:
"Exercise 1.12.  The following pattern of numbers is called Pascal's
triangle.
The numbers at the edge of the triangle are all 1, and each number
inside the triangle is the sum of the two numbers above it. Write a
procedure that computes elements of Pascal's triangle by means of a
recursive process." [1]

Solution: [2]

(define (pascal-triangle row col)
(cond ((> col row) 0)
((< col 0) 0)
((= col 1) 1)
((+ (pascal-triangle (- row 1) (- col 1))
(pascal-triangle (- row 1) col)))))

How to understand from the text of the exercise that I should write
the following.

(+ (pascal-triangle (- row 1) (- col 1))
(pascal-triangle (- row 1) col))

I've used a substitution method to watch both procedures in action. I
understand them.
But the design part of the code writing is not clear.
Could you explain it?

[1] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2
[2] http://community.schemewiki.org/?sicp-ex-1.12

[Jussi Piitulainen]

. writes:

> > > (define (f n)
> > >    (define (iter a b c count)
> > >      (if (= count 0)
> > >        a
> > >        (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))
> > >    (iter 0 1 2 n))
> >
> > They are f(0), f(1), and f(2). They come from f(n) = n if n < 3.
>
> I see. Thank you.
>
> There is another issue.
> I don't know how to design a recursive procedure (which generates a
> recursive or an iterative process).
>
> For example:
> It's not clear (for me) from the text of the exercise that we should
> use the following to calculate the third operand.
> (+ c (* 2 b) (* 3 a))

That's the definition, f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. (That
should be "if n >= 3".) The a, b, c in iter are three consecutive
elements of the sequence of f(k) for k = 0, 1, 2, 3, ...

Let me show you the simple solution:

(define (f n)
(case n
((0 1 2) n) ; n < 3
(else (+ (f (- n 1)) ; n >= 3
(* 2 (f (- n 2)))
(* 3 (f (- n 3)))))))

I just wrote the given definition in Scheme. The main reason I
wouldn't do this in practice is not the deep recursion but the fact
that the recursive calls will do the same work many times. I think
SICP illustrates this with Fibonacci numbers.

There are naturally tree-shaped problems where this kind of recursion
is the right thing.

For the given definition, consider the following variant, because I
think the backwards counting is needlessly obscure.

(define (f n)
(define (iter a b c k)
    (if (= k n)
       a
       (iter b c (+ c (* 2 b) (* 3 a)) (+ k 1))))
  (iter 0 1 2 0))

This goes through the same calculations, but now at every step the
meaning of the parameter can be stated simply: the three numbers a, b,
c are f(k), f(k + 1), and f(k + 2). That's why a is f(n) if k = n. If
not, try recursively with f(k + 1), f(k + 2), f(k + 3).

Hope this helps.

> Another example:
> "Exercise 1.12.  The following pattern of numbers is called Pascal's
> triangle.
> The numbers at the edge of the triangle are all 1, and each number
> inside the triangle is the sum of the two numbers above it. Write a
> procedure that computes elements of Pascal's triangle by means of a
> recursive process." [1]

It says "numbers at the edge" are all 1, and "each number is the sum

of the two numbers above it".

You are asked about c(r,k). If it's "at the edge", you know the
answer. The solution [2] you showed did not actually identify the
numbers at the edge, it identified the numbers _outside the whole
triangle_ and set them to 0. That's valid mathematics, but not
provided in the given definition. Try "k = 0 or r = k" as the
definition of "at the edge". (Avoid calling with k < 0 or k > r then.)

> How to understand from the text of the exercise that I should write
> the following.
>
> (+ (pascal-triangle (- row 1) (- col 1))
> (pascal-triangle (- row 1) col))

If c(r,k) is not "at the edge", you need the "two numbers above it",
c(r - 1, k - 1) and c(r - 1, k - 1). The answer is their sum. Row
numbers grow downwards, column numbers to the right, like in a matrix.

> But the design part of the code writing is not clear.
> Could you explain it?

Name the things. (pascal-triangle row col) is an ok name in a program,
c(r,k) is shorter. Look for base cases where the answer is known and
for the recursive cases where the answer is computed from simpler
instances of the same problem - which instances, how? - and then just
write in the following pattern:

(define (solve parameters)
(if (base-case? parameters)
(answer parameters)
(solve (simpler parameters))))

"simpler" means closer to some base case in some way, but that is
probably taken care of when you are given a definition like here.

The numbers in that triangle are very important, by the way, and there
are interesting other ways of computing them.

Keeping these for reference:

[raof01]

Per Paul Graham's comment, you could first write the recursive (not iterative) solution to the problem. Then you try the way to accumulate the result and pass it to the call to the procedure itself. Surely you will get clearer by comparing recursion and iteration.

And if you go further with SICP text, there's some description about loop invariant.

The essence of tail recursion (or iteration) is to put the result as procedure argument. You can see from the example using "do" I gave in previous post.

To give you some idea, let me show you some examples:
1. Calculate x^n:
x^0 = 1
x^n = x*x^(n-1) = x*x*x^(n-2) = ...
Solution:
;; Recursive
(define (exp x n)
(if (= n 0)
1
(* x (exp x (- n 1)))))

;; Iterative
(define (exp-iter x n)
(define (iter x n r)
(if (= n 0)
r
(iter x (- n 1) (* r x))))
(iter x n 1))

;; Iterative with O(logn)
(define (fast-exp-iter x n)
(define (iter x n r)
(cond ((= n 0) r)
((even? n) (iter (* x x) (/ n 2) r))
(else (iter x (- n 1) (* r x)))))
(iter x n 1))

Hope the examples help.

[raof01]

An other example is to calculate f(n)=1!+2!+3!+4!+...+n!
let divide the problem:
f(1) = 1
f(2) = f(1)+2! = f(1)+2*(f1)
f(3) = f(2)+3! = f(2)+3*f(2)
...
f(n) = f(n-1)+n! = f(n-1)+n*f(n-1)

Given these calculation procedures, the loop invariant is f(n-1)+n*f(n-1). Then we increase the counter from 1 to n, until the counter is n+1. This is the stop condition of the iteration.

Now the base case f(1)=1 is there, the calculation will be:
f(i) = iter(f(i-1), counter, result, n),

if counter is not equal to n+1, then iter will call itself to calculate with next i:
f(i+1) = iter(f(i), counter+1, result+counter*f(i), n)

Pay attention here: the increment of counter should be calculated before calculating result because of n*f(n-1)

Finally, the calculation f(i+1) = iter(f(i), counter+1, result+counter*f(i), n) is the iterative way to solve the problem.

(define (factorial_sum n)
(define (iter fi-1 c r)
(if (= c (+ n 1)) r
(iter (* fi-1 c) (+ c 1) (+ r (* fi-1 c)))))
(iter 1 1 0))

PS. It's a little bit hard to write iterative procedure. Exercises help. Once you grab the essence, it's easy. The focus then will be on how to resolve the problem, not on how to implement the solution.

[.]

I assume that this is how person's thought process would look like
if he (or she) decide to solve this exercise. Is this a right
approach?

f(n) = f(n-1) + 2f(n-2) + 3f(n-3) if n >= 3
f(3) = f(3-1) + 2f(3-2) + 3f(3-3)
f(3) = f(2) + 2f(1) + 3f(0)
f(3) = 2 + 2 + 0
f(3) = 4

Let's look at this line:
f(3) = f(2) + 2f(1) + 3f(0)

a = 0
b = 1
c = 2

f() = f(c) + 2f(b) + 3f(a)

We have to store three values to be able to calculate c:
c <- c + 2b + 3a
b <- c
a <- b

(define (f n)
(define (f-iter a b c n)
(if (= n 0)
a
(f-iter b c (+ c (* 2 b) (* 3 a)) (- n 1))))
(f-iter 0 1 2 n))

How should I know that f() = f(c) + 2f(b) + 3f(a) will work for
every a, b, c? In other words: how to be sure that my solution is
right?
Should I check my assumption via recursive process?

It's not clear how to design a recursive process. An example with
Fibonacci numbers had a recursive formula. It's not difficult if
you have a formula. But what should I do if I don't have one?

>> It says "numbers at the edge" are all 1, and "each number is the

>> sum of the two numbers above it".

Right, I forgot about the latter. I've checked some values and it's
pretty clear now. But why should we do the following:

(+ (pascal-triangle (- row 1) (- col 1))
(pascal-triangle (- row 1) col))

Not something like this:

(pascal-triangle (+ (- row 1) (- row 1)) (+ (- col 1) col))

Could you explain this using Fibonacci numbers? Where did we get
(fib (- n 1)) and (fib (- n 2)). I can't see it from this line:
0, 1, 1, 2, 3, 5, 8, 13, 21...

Is this the cause: "each number is the sum of the preceding two"?
So n is not a number itself, but its index. Right? Same goes for
row and col. That's why it's not enough to sum these values up, we
have to apply a recursive procedure to them. Is this correct?

>> Exercises help. Once you grab the essence, it's easy.

Could you suggest a place to practise? Project Euler? How should I
find a
problem which requires recursion?

Thanks for your help.

P.S. I haven't checked the factorial-sum yet.

[raof01]

> Could you suggest a place to practise? Project Euler? How should I
> find a
> problem which requires recursion?

Simply Scheme has lots of exercises. It's available for free: http://www.cs.berkeley.edu/~bh/ss-toc2.html

[Nils M Holm]

. <nkw...@gmail.com> wrote:
> Could you suggest a place to practise? Project Euler? How should I
> find a
> problem which requires recursion?

Re-implement some of the standard Scheme procedures, like REVERSE,
APPEND, MAP with a single list argument, and MAP with a variable
number of arguments (in order of increasing complexity).

Then download the S9fES archive (http://t3x.org) and have a look at
its library. It contains tons of small procedures with a description
at the top of the file and the solution (a working program) below.

Read the description, try to implement the program, and when you
get stuck, have a look at the S9 implementation.

--
Nils M Holm < n m h @ t 3 x . o r g > www.t3x.org

[toby]

On Friday, 25 May 2012 01:57:30 UTC-4, Nils M Holm wrote:

> . <nkwerk@gm..l.com> wrote:
> > Could you suggest a place to practise? Project Euler? How should I
> > find a
> > problem which requires recursion?
>
> Re-implement some of the standard Scheme procedures, like REVERSE,
> APPEND, MAP with a single list argument, and MAP with a variable
> number of arguments (in order of increasing complexity).

Another source of similar tasks is 99 Lisp Problems,
http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html