再帰的プロセスと反復的プロセス

無職の間にSICPも読んでみる。目標は焦らずしっかりと最後まで読む。

Scheme と C で再帰的プロセスと反復的プロセスの手続きをそれぞれ書く。

フィボナッチ数 : 再帰的プロセス

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

int fib(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

フィボナッチ数 : 反復的プロセス

(define (fib n)
    (define (fib-iter a b counter)
        (if (> counter n)
            b
            (fib-iter (+ a b) a (+ counter 1))))
    (fib-iter 1 0 1))

int fib(int n)
{
    int a, b, tmp;
    a = 1, b = 0;
    while (n--) {
        tmp = a;
        a  += b;
        b   = tmp;
    }
    return b;
}

pow : 再帰的プロセス

(define (pow base n)
    (if (= n 0)
        1
        (* base (pow base (- n 1)))))

int pow(int base, int n)
{
    if (n == 1)
        return base;
    else
        return base * pow(base, n - 1);
}

pow : 反復的プロセス

(define (pow base n)
    (define (pow-iter x counter)
        (if (> counter n)
            x
            (pow-iter (* base x) (+ counter 1))))
    (pow-iter 1 1))

int pow(int base, int n)
{
    int x = 1;
    while (n--)
        x *= base;
    return x;
}