Exercise1-10 <---> Exercise1-12

Exercise 1.11

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.

Ru: Функция f определяется правилом: f(n) = n, если n < 3 , и f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3), если n >= 3. Напишите процедуру, вычисляющую f с помощью рекурсивного процесса. Напишите процедуру, вычисляющую f с помощью итеративного процесса.

Scheme solution:

Recursive definition is trivial: 

(define (f-rec n)
  (if (< n 3)
      n
      (+ 
       (f-rec (- n 1))
       (* 2 (f-rec (- n 2)))
       (* 3 (f-rec (- n 3))))))

Iterative version requires a bit smarter approach.

We need to keep track of current state of process in parameters. So, let introduce three variables corresponding to states of function in three consecutive instants of time.

Then we need to invent some kind of transformation. Time goes and f(n - 2) becomes f(n - 1), f(n - 1) becomes f(n), and f(n + 1) becomes a new value which we need to calculate.

So this transformation might look like this: 

a <- b
b <- c 
c <- 3a + 2b + c  ( new calculated value of f )

Also we need counter to know when stop.

Let's illustrate this in code: 

(define (f-iter n)
  (define (f-inner a b c k)
    (if (< k 3)
        c 
        (f-inner
         b  ;; a <- b
         c  ;; b <- c
         (+ (* 3 a) (* 2 b) c) ;; c <- calculate new f(n + 1)
         (- k 1)))) ;; decrement counter
  (if (< n 3)
      n
      (f-inner 0 1 2 n)))

Haskell solution:

Recursive definition is: 

f n | n <  3 = n
    | n >= 3 = f(n-1) + 2*f(n-2) + 3*f(n-3)

and iterative definition is: 

f'iter n | n <  3 = n
         | n >= 3 = f'inner 0 1 2 n
  where
    f'inner a b c k | k < 3     = c
                    | otherwise = f'inner b c (3*a + 2*b + c) (k-1)

OCaml solution:

Recursive definition is: 

let rec f n =
  if n < 3 then
    n
  else
    f (n-1) + 2 * f (n-2) + 3 * f (n-3)

and iterative definition is: 

let f_iter n =
  let rec f_inner a b c k =
    if k < 3 then
      c
    else
      f_inner b c (3*a + 2*b + c) (k-1)
  in
    if n < 3 then
      n
    else
      f_inner 0 1 2 n

Standard ML solution:

Recursive definition is: 

fun f n =
  if n < 3 then
    n
  else
    f (n-1) + 2 * f (n-2) + 3 * f (n-3)

and iterative definition is: 

fun f_iter n = let
  fun f_inner (a, b, c, k) =
    if k < 3 then
      c
    else
      f_inner (b, c, 3*a + 2*b + c, k-1)
in
  if n < 3 then
    n
  else
    f_inner (0, 1, 2, n)
end

Oberon/Component Pascal solution:

Recursive definition is: 

PROCEDURE F (n : INTEGER) : INTEGER;
VAR result : INTEGER;
BEGIN
  IF n < 3 THEN
    result := n
  ELSE
    result := F(n-1) + 2*F(n-2) + 3*F(n-3)
  END;
  RETURN result
END F;

and iterative definition is: 

PROCEDURE FIter (n : INTEGER) : INTEGER;
VAR a, b, c, k, t : INTEGER;
    result : INTEGER;
BEGIN
  IF n < 3 THEN
    result := n
  ELSE
    a := 0; b := 1; c := 2; k := n;
    WHILE k >= 3 DO
      t := 3*a + 2*b + c;
      a := b; b := c; c := t;
      k := k-1
    END;
    result := c
  END;
  RETURN result
END FIter;

Exercise1-10 <---> Exercise1-12

Comments

iterative:

(define (fi n)

  • (define (f-iter x y z m)
    • (if (= m n) (+ x y z)
      • (f-iter y z (+ x y z) (+ 1 m))))

    (if (< n 4) n

    • (f-iter 1 2 3 4))
    )
Posted by 89 at 2008-02-02 06:03:20 X

:)

Posted by 97-116-129-134 :\ at 2008-10-01 03:47:33 X

I think the process could be adjusted a little to reduce two unnecessary steps.(write common lisp)

(defun fsum (n)

  • (defun f-inner (a b c y)

    • (if (< y 3)

      • a (f-inner (+ a (* b 2) (* c 3)) a b (1- y))))

    (if (< n 3)

    • n (f-inner 2 1 0 n)))
Posted by 69 at 2008-10-02 21:43:35 X

Crude solution :) 

(define (f n)
  (f-iter 0 1 2 n))

(define (f-iter n1 n2 n3 count)
  (cond ((= (- count 2) 0) n3)
        ((= (- count 1) 0) n2)
        ((= count 0) n1)
        (else (f-iter
               (+ (* 3 n1) (* 2 n2) n3) (+ (* 3 n2) (* 2 n3) (+ (* 3 n1) (* 2 n2) n3)) (+ (* 3 n3) (* 2 (+ (* 3 n1) (* 2 n2) n3)) (+ (* 3 n2) (* 2 n3) (+ (* 3 n1) (* 2 n2) n3))) (- count 3)))))
Posted by SriramDevadas at 2009-03-09 23:37:17

this too, no optims etc.. (define (f3 n)

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

    (if (< n 3) n (f-iter 2 1 0 n)))

Posted by 81 at 2009-05-09 16:59:33 X

Common Lisp: 

(defun f3 (n &optional (iter 0) x1 x2 x3)
  (cond 
    ((< n 3) n)
    ((= iter n) (+ x1 x2 x3))
    ((= iter 0) (f3 n 3 2 1 0))
    (t (f3 n (+ 1 iter) (+ x1 x2 x3) x1 x2))))

I'm newbie in Lisp

Posted by gra at 2009-05-31 14:26:33 X

(define (f-iter a b c count)

  • (if (< count 3)

    • a (f-iter (+ a b c) a b (- count 1))))

(define (f n)

  • (f-iter 1 1 1 n))
Posted by 77 at 2009-11-06 08:14:15 X

I think in the iterative solution, the check for < 3 is unnecessary. The correct value gets pushed to 'c' by the time count gets to 0

(define (f2 x)

  • (define (f2-iter a b c count)
    • (cond ( (= 0 count) c)
      • (else (f2-iter (+ a (* 2 b) (* 3 c))
        • a b (- count 1)))))
    (f2-iter 2 1 0 x))
Posted by AbhijitRay at 2009-12-02 07:38:40

:) :)) :( ;) :\ |) X-( B) Markup

Exercise1-11 (last edited 2009-03-24 01:51:09 by FirstnameLastname)