初探递归

;; 递归版本
(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (+ (fib (- n 1))
           (fib (- n 2)))))

;; 递归优化
(define (fib n)
  (fib-iter 1 0 n))
(define (fib-iter a b n)
  (if (= n 0)
      b
      (fib-iter (+ a b) a (- n 1))))    ; 循环往左推

int fib_iter(int a, int b, int n) {
    if (n == 0) {
        return b;
    } else {
        b = a + b;
        return fib_iter(b, a, n - 1);
    }
}

int fib(int n) {
    return fib_iter(1, 0, n);
}

int fib(int n) {
    int a = 0;
    int b = 1;

    if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 1;
    }

    for (int i = 3; i <= n; i++) {
        int c = a;              // 保留之前的a
        a = b;                  // 让a推进一位
        b = b + c;
    }
}