SICP. 1.2.2
2022-11-28 Mon

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 \geq 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.

Answer:

Writing a procedure that computes \(f\) by means of a recursive process is quite straightforward.

(defun f (n)
  (cond
   ((< n 3) n)
   (t (+ (f (- n 1))
         (* 2 (f (- n 2)))
         (* 3 (f (- n 3)))))))

(f 0)  ;; 0
(f 1)  ;; 1
(f 2)  ;; 2
(f 3)  ;; 4
(f 4)  ;; 11
(f 5)  ;; 25

Writing a (recursive) procedure that computes \(f\) by means of an iterative process is less straightforward.

My thought process: up to \(2\) we know the answer; the answer is the very same input. For a number \(n\) greater than \(2\), we are able to compute the answer if we know the result for the inputs \(n - 1\), \(n - 2\), and \(n - 3\). In the case of number \(3\) — the first number greater than \(2\) — we do know the answer for the inputs \(3 - 1\), \(3 - 2\), and \(3 - 3\). They are, respectively, \(2\), \(1\), and \(0\). Given that we know that, then we can compute the value of the function given input \(3\): …. But now we have the enough knowledge to compute the value of the function given the input \(4\). And once we know that, we can compute the value of the function given the input \(5\), etc.

So we can use a counter that starts from \(0\) and iterate until we have completed the right number of ``loops'', keeping track of the three relevant values that allows us to compute the value of the process at that time.

(defun f2 (n)
  (f-iter 0 n 0 1 2))

(defun f-iter (counter max-count A B C)
  (if (< counter max-count) ;; keep iterating
      (if (< counter 3)
          (f-iter (1+ counter) max-count 0 1 2)
        (f-iter (1+ counter) max-count B C (+ (* 3 A)
                                              (* 2 B)
                                              C)))
    (if (< counter 3)
        counter
      (+ (* 3 A)
         (* 2 B)
         C))))

(f2 0) ;; 0
(f2 1) ;; 1
(f2 2) ;; 2
(f2 3) ;; 4
(f2 4) ;; 11
(f2 5) ;; 25

Exercise:

The following pattern of numbers is called Pascal’s triangle.

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1
       ...

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.

Answer: You can think of the triangle just as a bunch of lines/rows, each of which is one element more than the previous one.

a
b, c
d, e, f
g, h, i, j
...

What helped me to find a solution was using a row[col] notation.

0[0]
1[0], 1[1]
2[0], 2[1], 2[2]
3[0], 3[1], 3[2], 3[3]
4[0], 4[1], 4[2], 4[3], 4[4]

We can immediately notice two things:

• First, col=0 means we are dealing with the first element of a row. And the first element of a row is always a 1.
• Second, when row=col we are dealing with the last element of a row. And the last element of a row is always a 1.

So, we need a way to find the value of those elements where neither row≠col nor col=0. Saying that an element equals the sum of the two numbers ``above'' it is equivalent to say that an element with inidex i at row r equals the sum of two elements at row r-1, more specifically the sum of those two elements the first one of which has index i-1 and the second one of which has index i.

We have enough rules

;;(tartaglia row col)
;;
;;col=0   ==> 1
;;col=row ==> 1
;;else    ==> (+ (tartaglia (1- row)(1- col))
;;               (tartaglia (1- row) col))

We can write our procedure!

(defun tartaglia (r c)
  (cond
   ((= c 0) 1)
   ((= r c) 1)
   (t (+ (tartaglia (1- r)(1- c))
         (tartaglia (1- r) c)))))

(tartaglia 0 0)
;; => 1
(tartaglia 1 0) (tartaglia 1 1)
;; => 1, 1
(tartaglia 2 0) (tartaglia 2 1) (tartaglia 2 2)
;; => 1, 2, 1
(tartaglia 3 0) (tartaglia 3 1) (tartaglia 3 2) (tartaglia 3 3)
;; => 1, 3, 3, 1
(tartaglia 4 0) (tartaglia 4 1) (tartaglia 4 2) (tartaglia 4 3) (tartaglia 4 4)
;; 1, 4, 6, 4, 1

It works!

As an extra, here is a quick js iterative way of computing the elements:

function tartaglia(n) {
  let previousLine = [1, 1,];
  for (let i = 0; i < n; i++) {
    if (i == 0) {
      console.log( [1] )
    } else if (i == 1) {
      console.log( [1, 1] );
    } else {
      previousLine = line(previousLine);
      console.log(previousLine);
    }    
  }  
}

//Compute line given previous one
function line(arr) {
  let result = [1, ];
  for (let i = 0; i < arr.length-1; i++) {
    result.push(arr[i] + arr[i+1]);
  }
  result.push(1);
  return result;
}

tartaglia(5);
// =>
// [ 1 ]
// [ 1, 1 ]
// [ 1, 2, 1 ]
// [ 1, 3, 3, 1 ]
// [ 1, 4, 6, 4, 1 ]