欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

《编程机制探析》第十六章 树形递归

程序员文章站 2022-05-17 13:44:12
...
《编程机制探析》第十六章 树形递归

上一章我们讲解了线性递归,使用的是各种资料中用得最多、最为经典的例子——阶乘(Factorial)算法。
本章讲解递归结构中比较复杂的树形递归,同样使用各种资料中用得最多、最为经典的例子——斐波那契(Fibonacci)数列。
典型的斐波那契(Fibonacci)数列问题是这么描述的:有一种母牛,出生后第三年,开始生育,每年都生一头母牛(貌似单性生育,这里就没公牛什么事儿);生出来的小母牛也符合同样的规律,出生后第三年,开始生育,每年都生一头母牛;该种母牛是永生的,而且永远拥有生育能力,生命不止,生育不止,生生不息。第一年时,只有一头母牛。请问第n年时,共有母牛多少头?
第一年和第二年时,母牛A还没有进入生育期,只有一头。
第三年,母牛进入生育期,生了一头小母牛B,共有两头母牛。
第四年,母牛A稳定生育,又增加一头小母牛C。小母牛B还未进入生育期,没有生母牛。共有母牛三头。
第五年,母牛A稳定生育,又增加一头小母牛D。小母牛B进入生育期,又增加一头小母牛E。C还未进入生育期,没有生母牛。共有母牛五头。
第六年,小母牛C进入生育期。该母牛种群开始进入爆发式增长。共有母牛8头。
第七年,13头。
第八年,21头。
第九年,….
我们可以用一个母牛生育表,来记录每年的生育期母牛头数和非生育期母牛头数,并统计统计每年的母牛总头数。
这里面的规律是,从第三年起,每过一年,上一年生育期母牛会生出同样数量的未生育期母牛。同时,上一年的未生育期母牛全部变成生育期母牛。
即,每过一年。
生育期母牛的个数 = 上一年生育期母牛的个数 + 上一年未生育期母牛的个数。
未生育期母牛的个数 = 上一年生育期母牛的个数。
母牛总数 =生育期母牛的个数 + 未生育期母牛的个数
表格数据如下:
年数 生育期母牛 未生育期母牛 母牛总数
1 0 1 1
2 0 1 1
3 1 1 2
4 2 1 3
5 3 2 5
6 5 3 8
7 8 5 13
8 13 8 21
9 21 13 34
10 34 21 55
我们观察母牛总数那一列。1,1,2,3,5,8,13,,21,34, 55…
可以发现这样的规律,从第三个数字开始,每个数字都等于前两个数字的和。
注:这个规律可以直接看出来,也可以通过前面的算式推导出来。
用公式表达就是这样:
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2)
符合这种规律的数列,就叫做斐波那契(Fibonacci)数列。根据公式,我们很容易就得出递归算法。
int fibonacci(int n){
  if(n < 3)
return 1;

  return result = fibonacci(n - 1) + fibonacci(n - 2);
}
显然,这是一个树形递归。算法的空间和时间复杂度都很高,随着n的增大,呈指数增长。
递归调用的过程中,运行栈的伸缩次数是多次的,不断地压栈,出栈,再压栈,出栈。
很容易就可以看出,这个算法中充满了重复计算。
计算fibonacci(5)的时候,先计算 fibonacci(4),然后计算 fibonacci(3);
计算fibonacci(4) 的时候,先计算fibonacci(3),然后计算 fibonacci(2);….
fibonacci(4)完成了之后,fibonacci(5)再接着计算fibonacci(3),而全然不顾fibonacci(3)已经算过一遍的事实。
如果我们把这个算法转换成尾递归,就可以有效地消除重复计算的情况。如何转换呢?我们命令式首先想到的就是用循环实现fibonacci算法,然后,转换成尾递归。这种方法很有效。因为Fibonacci算法不复杂,可以比较容易地用循环来实现,只需要用一个数据结构来存放f(n-1)和f(n-2)的计算结果就行了。
这种思路对于命令式程序员来说,是驾轻就熟了。现在,既然我们将要学习和使用函数式编程。我们就试图采用函数式程序员的思路。我们直接从现有的递归算法转换。
上一章我们已经讲述过尾递归转换的通用思路:尾递归只是最后一步操作,所有的计算都在之前完成,然后,计算结果作为参数传递到最后的尾递归操作中。递归函数在入口处就需要根据传进来的参数(上一次计算的结果和当前步骤)来判断是否继续递归,还是直接返回结果。有了这样的思路之后,我们先来分析前面的递归算法,抽离出中间计算结果。
int fibonacci(int n){
  if(n < 3)
return 1;

  int result1 = fibonacci(n - 1);
  int result2 = fibonacci(n - 2);

  int result = result1 + result2;
  return result;
}
我们需要把计算结果result1和result2作为参数。算法改造如下:
int fibonacci(int i, int result1, int result2, int n){
  int result = result1 + result2; // f(i) = f(i-1) + f(i – 2)

  if(i >= n)  // i 表示当前步骤。
return result;

int j = i + 1;  // i = j -1
  nextResult1 = result; // f(j - 1) = f(i)
  nextResult2 = result1; // f(j - 2) = f(i – 1)
  return fibonacci(j, nextResult1, nextResult2, n);
}
这就是一个尾递归算法,消除了重复计算的问题。因为我们把前两步的计算结果保存了起来,并作为参数传到下一次递归。
这个尾递归的包装函数如下:
int neat_fibonacci(int n){
  if(n < 3)
return 1;

  return fibonacci(3, 1, 1, n);
}
在上述的尾递归算法中,我们引入了参数i来表示当前计算步骤,还特意声明了一个变量j来表示i的下一步(j = i + 1),这是为了使得代码更加清晰易读。实际上,同上一章的尾递归例子一样,参数i是可以省略的。写法如下:
int fibonacci(int result1, int result2, int n){
  int result = result1 + result2; // f(i) = f(i-1) + f(i – 2)

  if(n <= 3)  // i 表示当前步骤。
return result;

int j = i + 1;  // i = j -1
  int nextResult1 = result; // f(j - 1) = f(i)
  int nextResult2 = result1; // f(j - 2) = f(i – 1)
  return fibonacci(nextResult1, nextResult2, n);
}
其包装函数为:
int neat_fibonacci(int n){
  if(n < 3)
return 1;

  return fibonacci(1, 1, n);
}
这种尾递归虽然少了一个参数,但是可读性明显差了许多。
上述两种尾递归写法都可以转换成循环,由于第一种尾递归可读性明显更好,我们就根据它来改造。
尾递归改造成循环,和循环改造成尾递归的过程正好相反。我们需要把参数变成一个局部变量的存储结构,循环体使用这个存储结构来存放中间结果。代码如下:
int fibonacci(int n){
  if(n < 3)
return 1;

  int result1 = 1;
  int result2 = 1;
  int result = 0;
  for(int i = 3; i <= n; i++){
result = result1 + result2; // f(i) = f(i – 1) + f(i – 2)

// 以下的代码是为下一步准备的。假设 j = i + 1
result1 = result; // f(j -1) = f(i)
result2 = result1; // f(j – 2) = f(i -1)
  }
  return result;
}
以上就是Fibonacci常规问题的常规解法,常见于各种资料。本章只不过对这个问题进行了综合剖析和进一步发挥。下面,我将对Fibonacci常规问题进行扩展,并给出相应算法和对应的数据结构。
首先,我们回顾一下Fibonacci问题的常规描述:
1头母牛,出生后第3年,就开始每年生1头母牛,按此规律,第n年时有多少头母牛。
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2)
Fibonacci数列看起来是这样:1,1,2,3,5,8,13,,21,34........
现在,我们对该问题进行一个小小的条件改变,对母牛品种进行一个小小的改造。我们嫌母牛成长得太快了。现在,我们培育出一种新的变种母牛(姑且命名为变种A),这种母牛第四年才开始生育。这就产生了一个Fibonacci问题的变种,姑且称之为Fibonacci问题变种A。
Fibonacci问题变种A描述:
1头母牛,出生后第4年,就开始每年生1头母牛,按此规律,第n年时有多少头母牛。
f(1)=1
f(2)=1
f(3)=1
f(n)=f(n-1)+f(n-3)
Fibonacci变种A数列:1, 1, 1, 2, 3, 4, 6, 9,13,19,28........
变种A成功之后,我们受到鼓舞,又依次研究出其他的变种母牛。
变种B:第五年开始生育。
变种C:第六年开始生育。
……
最后,我们研制出所有的变种,可以任意控制母牛在几岁开始生育。这就得到了Fibonacci问题通用描述:
1头母牛,出生后第x年,就开始每年生1头母牛,按此规律,第n年时有多少头母牛。
令k = x - 1
f(1)=1

f(k)=1
f(n)=f(n-1)+f(n-k)
我们如何为这个Fibonacci问题通用版本编写算法。首先,树形递归算法最容易,也最简洁。
int fibonacci(int n, int k){
  if(n <= k)
return 1;

  int result = fibonacci(n - 1) + fibonacci(n – k);
}
那么,我们该如何把这个树形递归算法修改成尾递归算法和循环算法呢?我们遇到的主要问题就是缓存中间计算结果。这里,我们只保存前两步的计算结果,已经不够了。我们需要保存前k步的计算结果。这就是说,我们需要一个长度为k的存储结构,其中存放着前k步的计算结果。
假设当前计算步骤为i,那么,该存储结构内就存放了从f(i - k)一直到f(i – 1)的结果。当计算步骤向前推进时,存储结构的数据也向前推进。比如,当计算步骤推进到 j = i + 1时,存储结构内的数据就变成从 f(j – k) 到 f(j – 1)。
该存储结构的特征总结如下:其存储容量不定,由k参数定义;其存储内容跟随当前计算步骤而移动。
为了解决这个问题,我们引入一个叫做LinkedQueue的类。这个类是一个用链表结构实现的队列结构。关于队列结构,我们前面提到过,这是一种先入先出的数据结构,与栈结构相对。关于队列结构和链表结构的知识很简单,请读者自行补充。
LinkedQueue提供了如下方法:
LinkedQueue(int k)
int removeHead()
int getTail()
void addTail(int result)
构造函数LinkedQueue(int k)接受一个参数k,进行初始化,在内部生成一个长度为k的、元素类型为整数的链表结构,每个整数元素的值都是1。这代表着f(1)到f(k)的值。
removeHead方法直接取出头部元素(一个整数),队列长度减一。
getTail方法取出尾部元素的值(一个整数),并不取出元素本身,队列长度不变,内容不变。
addTail方法在尾部增加一个整数作为队列元素,队列长度加一。
这个数据结构的实现基于一种叫做双向链表的结构,即,每个结点都保留着前一个结点和后一个结点的引用。从而既可以在头部增删改,也可以在尾部增删改。
另外一种等价实现是一个长度为K的环形数组,这种实现在空间和时间效率上都很高。
这两种数据结构的实现都不难,不再赘述。
有了这个数据结构,我们就可以轻松写出通用fibonacci问题的尾递归算法。
int fibonacci(int i, LinkedQueue results, int n, int k){
  int resultK = results.removeHead();  // f(i – k)
  int result1 = results.getTail(); // f(i – 1)
  int result = result1 + resultK;  // f(i) = f(i-1) + f(i – k)
  if(i >= k)
return result;

  results.addTail(result);

  return fibonacci(i + 1, results, n, k);
}
其包装函数为:
int neat_fibonacci(int n, int k){
  if(n <= k)
return 1;

  LinkedQueue = new LinkedQueue(k);
  return fibonacci(k + 1, results, n, k);
}
下面我们把它改成循环。同样是把递归体变成循环体,参数变成循环体外的局部变量。
int fibonacci(int n, int k){
  if(n <= k)
return 1;

  LinkedQueue = new LinkedQueue(k);

  for(int i = k; i <= n; i++){
  int resultK = results.removeHead();  // f(i – k)
    int result1 = results.getTail(); // f(i – 1)
    int result = result1 + resultK;  // f(i) = f(i-1) + f(i – k)
    results.addTail(result);
  }

  return result;
}
这样,我们就完成了fibonacci通用问题的通用算法。当k = 2时,就是我们一开始遇到的常规fibonacci问题。
fibonacci问题虽然不是一个太难的算法,但毕竟还是浪费了我们一点脑细胞。有没有一种通用的方法来解决树形递归中的重复计算问题呢?
有。那就是使用缓存。如果你不在意内存的话。
比如,我们可以把前面的fibonacci常规问题的树形递归算法写成这样:
int neat_ fibonacci(int n){
  if(n < 3)
return 1;

  int[] resultTable = new int[n];
  for(i = 1; i <= n; i++){
    resultTable[i] = 0;
  }
 
  fibonacci(n, resultTable);
}

int fibonacci(int n, int[] resultTable){
  if(n < 3)
return 1;

  int cached = resultTable[n];
  if(cached != 0)
return cached;

  int result1 = fibonacci(n - 1);
  int result2 = fibonacci(n - 2);

  int result = result1 + result2;
  resultTable[n] = result;
  return result;
}
通用fibonacci问题的树形递归算法也可以这样写:
int neat_ fibonacci(int n, int k){
  if(n <= k)
     return 1;

  int[] resultTable = new int[n];
  for(i = 1; i <= n; i++){
    resultTable[i] = 0;
  }
 
  return fibonacci(n, resultTable);
}

int fibonacci(int n, int k, int[] resultTable){
  if(n <= k)
return 1;

  int cached = resultTable[n];
  if(cached != 0)
return cached;

  int result1 = fibonacci(n - 1);
  int resultK = fibonacci(n - k);

  int result = result1 + resultK;
  resultTable[n] = result;
  return result;
}