递归

线性递归

我们都知道阶乘的定义是 $$ n! = n * (n-1) * (n-2)…3 * 2\ * 1，且1! = 1 $$ 那么实现阶乘最自然的方法就是按照定义展开即可

(define (fact n)
  (if (= n 1)
      1
      (* n (fact (- n 1)))))

以计算(fact 5)为例子，让我们展开这个计算过程

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 1)))))
(* 5 (* 4 (* 3 2)))
(* 5 (* 4 6))
(* 5 24)
120

下面以另一种方式实现阶乘

(define (fact2 n)
  (define (helper counter res n)
    (if (> counter n)
        res
        (helper (+ counter 1) (* res counter) n)))
  (helper 1 1 n))

同样一计算(fact2 5)为例，展开这个计算过程

(helper 1 1 5)
(helper 2 1 5)
(helper 3 2 5)
(helper 4 6 5)
(helper 5 24 5)
120

现在对比fact和fact2的展开，你会发现:

• 对于fact，在计算一个数时会先展开所有过程然后在收缩，每一过程都会占用额外的空间，并且这些过程链都有解释器维护。这种先展开推迟计算再收缩实际执行计算的过程称为递归计算过程，另外，对于阶乘来说过程链的长度增长和n成正比，这种递归过程线性递归过程。

• 对于fact2，在计算是没有展开和收缩，但在计算中我们需要额外的变量来存放上一步计算的结果，这种过程成为迭代计算过程。通俗的说，迭代计算过程就是那种状态可以用固定数目的*状态变量*描述的过程，同时还存在一套固定的规则用于描述计算过程中从一个状态到下一个状态转换时，这些变量的更新方式，另外还可能有计算过程的终止条件。对于阶乘来说，计算步骤随n线性增长，这种过程称为线性迭代过程。

注意：在描述计算过程是递归或迭代时指的是过程的展开方式，而过程是递归只是陈述语法形式上的事实。

树形递归

我们知道Fibonacci数的定义是 $$ Fib(n)=\left\{ \begin{array}{lcl} 0 & {n=0}\\ 1 & {n=1}\\ Fib(n-1) + Fib(n-2) & {n\ge1}\\ \end{array} \right. $$

同样，我们也可以按照定义直接写出实现

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

从实现可以看出，对大于1的数进行求值，没一个数都会有两个分支，因此计算过程的展开是一个树形结构 可以看到图中有很多重复的计算，虽然很直观但效率却很低。

在仔细观察定义后发现，我们可以使用两个数来保持上一次的计算结果，假设为a和b，它们的初始状态分别是\(fib(1) = 1\)和\(fib(0) = 0\)，并且之后反复使用下面的变换规则 $$ \begin{array}{lcl} a \longleftarrow a + b\\ b \longleftarrow a \end{array} $$ 在经过n次变换后\(a\)和\(b\)的值分别等于\(fib(n+1)\)和\(fib(n)\)。因此，我们可以以迭代的方式来计算，如下

(define (fib2 n)
  (define (helper a b counter)
    (if (= counter 0)
        b
        (helper (+ a b) a (- counter 1))))
  (helper 1 0 n))

递归计算过程和迭代计算过程

从上面的两个例子可以看到，递归计算过程的有点是十分直观，但效率相对较低，而迭代计算过程需要手动保存过程中的状态，但效率较高。

前面两个例子中手动保存状态的办法并不能对所有的递归计算过程生效，所以有时还需要CPS。

练习

函数\(f\)由如下的规则定义：如果\(n\)，那么\(f(n)=n\);如果\(n\geq3\)，那么\(f(n)=f(n-1)+2f(n-2)+3f(n-3)\)。请写一个采用递归计算过程计算\(f\)的过程，再写一个采用迭代计算过程计算\(f\)的过程。

递归计算过程:

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

迭代计算过程:

(define (iterative n)
  (define (helper a b c n)
    (if (< n 3)
        a
        (helper (+ a (* 2 b) (* 3 c)) a b (- n 1))))
  (helper 2 1 0 n))

由于递归过程的实现和问题的描述一致，十分地直观，所以没有必要进行解释。下面对迭代的实现进行解释。

和Fibonacci类似，这个函数写成迭代过程需要保存三个状态，分别是\(f(n-1)\)、\(2f(n-2)\)以及\(3f(n-3)\)。我们分别使用\(a\)、\(b\)和\(c\)来替代，我们尝试由初始条件展开\(f(4)\)的计算过程
$$ \begin{array}{lcl} f(4) = f(3) + 2f(2) + 3f(1)\\ f(3) = f(2) + 2f(1) + 3f(0)\\ \\ f(2) = 2 = a\\ f(1) = 1 = b\\ f(0) = 0 = c\\ \end{array} $$ 可以发现当\(n\geq3\)时新的\(a\)等于上一次的\(a + 2b + 3c\)，而\(n=4\)时\(b\)的值就是\(n=3\)时\(a\)的值，下一次\(n\)增长时\(c\)的值就是上一次\(b\)的值。所以，我们就得到了初始条件和状态的转换规则，使用C的伪代码来表达就是

a = 2;
b = 1;
c = 0;
while(n>=3) {
 tmp = a + 2 * b + 3 * c;
 c = b;
 b = a;
 a = tmp;
 --n;
}
return a;

同时，对比上面Scheme的迭代实现，你也发现C及其他一些语言中的while、for只不过是尾递归的语法糖！

下面数值模式称为帕斯卡三角形：

                    1
                  1   1
                 1  2  1
                1  3  3 1

三角形边界上的数都是1,内部的每个数是位于它上面的两个数之和。请写一个过程，它采用递归计算过程计算出帕斯卡三角形。（帕斯卡三角形的元素为第\(n\)行，\((x+y)^n\)的展开式的系数）

#lang racket

;; first version
(define (pascal-impl r c)
  (cond
    [(or (= c 0) (> c r)) 0]
    [(= c r) 1]
    [else (+ (pascal-impl (- r 1) (- c 1)) (pascal-impl (- r 1) c))]))

(pascal-impl 5 3)

;; second version
(define (pascal-impl2 r c)
  (define res 0)
  (define (impl r c)
    (cond
      [(or (= c 0) (> c r)) (set! res (+ res 0))]
      [(= c r) (set! res (+ res 1))]
      [else (impl (- r 1) (- c 1))
            (impl (- r 1) c)]))
  (impl r c)
  res)

(pascal-impl2 5 4)

第一个实现是很直白的翻译，第二个实现是第一个实现的迭代计算过程版本。简单解释如下：

第4行有4个元素，分别是 1 3 3 1
第一个1记为(r4, c1)，则按照定义(r4, c1) = (r3, c0) + (r3 c1) = 0 + 1
第二个3记为(r4, c2)，则按照定义(r4, c2) = (r3, c1) + (r3, c2) = 1 + 2
第三个3记为(r4, c3)，则按照定义(r4, c3) = (r3, c2) + (r3, c3) = 2 + 1
第四个1记为(r4, c4)，则按照定义(r4, c4) = (r3, c3) + (r3, c4) = 1 + 0
其中r表示row，c表示column，同理推导，可得出第一个版本的实现。

下面是第二个版本实现的C++翻译

#include <iostream>

void pascal(int& res, int r, int c)
{
  if(c == 0 || c > r)
  {
    res += 0;
  }
  else if(c == r)
  {
    res += 1;
  }
  else
  {
    pascal(res, r - 1, c - 1);
    pascal(res, r - 1, c);
  }
}

int main(int argc, char* argv[])
{
  if(argc != 2)
  {
    fprintf(stderr, "%s number\n", argv[0]);
    return 1;
  }
  int n = atoi(argv[1]);
  int res = 0;
  for(int r = 1; r <= n; ++r)
  {
    for(int i = r; i < n; ++i)
    {
      putchar(' ');
    }
    for(int c = 1; c <= r; ++c)
    {
      res = 0;
      pascal(res, r, c);
      printf("%d ", res);
    }
    putchar('\n');
  }
}

换句话说，scheme里面的迭代其实是指的tail call。真正的迭代反而是个动态规划:

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> pascal(int row)
{
  vector<vector<int>> res;
  if(row == 0)
  {
    return res;
  }

  res.push_back(vector<int>{1});
  for(int i = 1; i < row; ++i)
  {
    vector<int> tmp(i+1);
    for(int j = 0; j <= i; ++j)
    {
      if(j == 0)
      {
        tmp[j] = 1;
      }
      else if(j == i)
      {
        tmp[j] = 1;
      }
      else
      {
        tmp[j] = res[i-1][j-1] + res[i-1][j];
      }
    }
    res.push_back(tmp);
  }
  return res;
}

int main()
{
    auto r = pascal(5);
    for(auto& v: r)
    {
      for(auto i: v)
      {
        printf("%d ", i);
      }
      printf("\n");
    }
}