递归序列(中学结论高中数学)原始数据结构与算法2020-08-10 10:19:13

什么是递归？

在讲递归之前，我们先来看看递归。递归就是在运行的过程中调用自己。

递归的条件如下:1。子问题必须与原问题相同，且更简单；2.你不能无限期地称呼自己。必须有出口，简化为非递归条件处理。

递归语言的例子

让我们用两个故事来解释什么是递归。

1.从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事！有什么故事？“从前，有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事！有什么故事？从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事！有什么故事？……'”

2.大雄在自己房间里，用时光电视看往事。当时在电视画面中，他在自己的房间里，看着过去的时光电视。当时的电视屏幕出现在电视屏幕上，他正在自己的房间里，看着时间电视上过去的情形…

递归模板

我们知道递归必须有两个条件，一个是调用自身，一个是有终止条件。这两个条件必须同时满足，一个都不能少。并且终止条件必须在递归的开始，如下。

publicvoidrecursion(参数0){if(终止条件){return;}recursion(参数1);}

你不能把终止条件写在递归的末尾。下面的写法不对。

publicvoidrecursion(参数0){recursion(参数1);if(终止条件){return;}}

在这种情况下，递归永远不会后退，并且会发生StackOverflowError。

但实际上递归可能不止一次调用自己，很多递归在调用之前或之后都会有一些逻辑处理，比如下面。

publicvoidrecursion(参数0){if(终止条件){return;}可能有一些逻辑运算recursion(参数1)可能有一些逻辑运算recursion(参数2)……recursion(参数n)可能有一些逻辑运算}

实例分析

我对递归的理解是一层一层往下传，满足终止条件就会反弹，最终会反弹到调用的地方。我们拿五个最常见的例子来分析一下。

1，阶乘

我们先来看看最简单的递归调用——阶乘。代码如下所示

publicintrecursion(intn){if(n==1)return1;returnn*recursion(n–1);5}

这种递归太熟悉了。第2-3行是终止条件，第4行是给自己打电话。我们来画一个n = 5时的图，看看递归是怎么调用的。

如果看不清楚，点击放大图片。

这种递归还是很简单的。当我们找到f(5)时，我们只需要找到f(4)。如果我们找到f(4)，我们将要求f (3)…，层层调用。当n=1时，我们会直接返回1，然后逐层返回，直到返回f(5)。

递归的目的是将一个大问题细分成更小的子问题。我们只需要知道递归函数的作用，不要一层一层的去想递归。如果同时调用几次，很可能会陷入循环，出不来。比如上面问题中需要f(5)，我们只需要计算f(4)，即F(5)= 5 * F(4)；至于f(4)是怎么算出来的，先不说了。因为我们知道f(n)中的n可以表示任意正整数，所以只需要传入4就可以计算f(4)。

2.斐波那契数列

我们再来看另一个经典的递归问题，就是斐波那契数列。该序列的前几项如下

[1,1,2,3,5,8,13……]

我们参考递归模板把它写下来。第一个终止条件是当n等于1或2时返回1，即序列的前两个值为1。代码如下所示

publicintfibonacci(intn){if(n==1||n==2)return1;这里是递归调用；}

递归的两个条件，一个是终止条件，我们已经找到了。另一种是给自己打电话。我们知道斐波那契数列的当前值是前两个值之和，也就是

斐波那契(n)=斐波那契(n – 1) +斐波那契(n – 2)

所以代码很容易写。

//1,1,2,3,5,8,13……publicintfibonacci(intn){if(n==1||n==2)return1;returnfibonacci(n–1)+fibonacci(n–2);}

3.河内塔

通过对前两个例子的分析，我们对递归有了一个大致的了解。再来看另一个例子——河内塔。其实这个之前已经提过了。有兴趣的可以去河内塔362看看。

这里简单说一下汉诺塔的原理，就是有A、B、c三根柱子，A盘在柱子上从上到下从小到大排列。通过B列将A列上的磁盘全部移动到C列，移动的过程永远是小盘在上，大盘在下。让我们递归地解决这个问题。我们先定义一个函数。

Public void Hanoi (int n，char a，char b，char c)他的意思是在b的帮助下成功地将n个磁盘从A移动到C。

我们先来回顾一下递归的条件。一个是终止条件，一个是给自己打电话。我们先来看递归的终止条件，即当n等于1时，也就是A列只有一个磁盘时，我们可以直接把A列的磁盘移到c列。

//表示的是把n个圆盘借助柱子B成功的从A移动到Cpublicstaticvoidhanoi(intn,charA,charB,charC){if(n==1){//如果只有一个，直接从A移动到C即可System.out.println(“从”+A+“移动到”+C);return;}这里是递归调用}

我们再来看看递归调用。如果n不等于1，我们就要把它分成3步。

1.首先，n-1个磁盘在C的帮助下成功地从A移动到B2，然后第n个磁盘从A移动到C3，最后，n-1个磁盘在A的帮助下成功地从B移动到C

那么如何编写代码呢？我们知道这个函数。

Hanoi(n，’ A ‘，’ B ‘，’ C ‘)表示N个圆盘通过B成功地从A移动到C。

所以hanoi(n-1，’ A ‘，’ C ‘，’ B ‘)的意思是n-1个磁盘在C的帮助下成功地从A移动到B。

Hanoi(n-1，’ B ‘，’ A ‘，’ C ‘)表示n-1个磁盘通过A成功地从B移动到C。

所以上面的三个步骤可以用这样的代码来表达。

1，hanoi(n-1，’ A ‘，’ C ‘，’ B’)2，System.out.println(“从”+A+”移动到”+C “)；3，河内(n-1，“B”，“A”，“C”)

所以最终完整的代码如下

1//表示的是把n个圆盘借助柱子B成功的从A移动到C2publicstaticvoidhanoi(intn,charA,charB,charC){3if(n==1){4//如果只有一个，直接从A移动到C即可5System.out.println(“从”+A+“移动到”+C);6return;7}8这里是递归调用9}//表示的是把n个圆盘借助柱子B成功的从A移动到Cpublicstaticvoidhanoi(intn,charA,charB,charC){if(n==1){//如果只有一个，直接从A移动到C即可System.out.println(“从”+A+“移动到”+C);return;}//表示先把n-1个圆盘成功从A移动到Bhanoi(n–1,A,C,B);//把第n个圆盘从A移动到CSystem.out.println(“从”+A+“移动到”+C);//表示把n-1个圆盘再成功从B移动到Chanoi(n–1,B,A,C);}

通过上面的分析，你是不是觉得递归很简单？所以我们写递归的时候，完全可以套用上面的模板，先写终止条件，再写递归的逻辑调用。还有一点很重要，就是一定要理解递归函数中每个参数的含义，这样在逻辑处理和函数调用时才能得心应手。一定不能一步一步把函数调用拆开来想，这样很有可能你会崩溃。

4、二叉树的遍历

我们来看最后一个常见的例子，就是二叉树的遍历。前面说了，有兴趣的话可以看看373，数据结构-6，还有树。我们主要看二叉树的前、中、后三种遍历方法。

1.我们来看一下前导遍历(根节点的开始)。他的命令是

节点→左子树→右子树

让我们应用模板来看看。

publicvoidpreOrder(TreeNodenode){if(终止条件)//(必须要有)return;逻辑处理//（不是必须的）递归调用//(必须要有)}

终止条件是节点等于空，通过逻辑处理可以直接打印出当前节点的值。递归调用是先打印左子树，再打印右子树。让我们来看看。

publicstaticvoidpreOrder(TreeNodenode){if(node==null)return;System.out.printf(node.val+“”);preOrder(node.left);preOrder(node.right);}

直接看中序遍历和后续遍历。

2.中序遍历(根节点在中间)

左子树→根节点→右子树

publicstaticvoidinOrder(TreeNodenode){if(node==null)return;inOrder(node.left);System.out.println(node.val);inOrder(node.right);}

3.按逆序遍历(根节点在末尾)

左子树→右子树→根节点

publicstaticvoidpostOrder(TreeNodetree){if(tree==null)return;postOrder(tree.left);postOrder(tree.right);System.out.println(tree.val);}

5.链表的反向打印

这个我就不说了，看看就知道了。

publicvoidprintRevers(ListNoderoot){//（终止条件）if(root==null)return;//（递归调用）先打印下一个printRevers(root.next);//（逻辑处理）把后面的都打印完了在打印当前节点System.out.println(root.val);}

支流污染问题

通过上面的分析，我们对递归有了更深的理解。但是总觉得少了点什么。其实我们可以用另一种方式来认识递归，那就是N树。在递归中，如果我们只调用自己一次，我们可以把它看成一棵二叉树(这是我对自己的看法，我们可以把它看成一棵只有一个子节点的树)。如果我们称自己两次，我们可以把它想象成一棵二叉树。如果我们叫自己N次，我们可以把它想成一棵N叉树。就像下面这样，到了叶子节点就开始反弹。

如果递归处理不当，可能会导致分支污染和结果错误。为什么会这样？我先解释一下，因为除了基本类型是值传递，其他很多类型基本都是引用传递。看一下上图。比如我开始调用的时候传入了一个list对象，调用第一个分支后，修改了列表中的数据，所以后续的所有分支都可以感知到，实际上对后续的分支造成了污染。

我们先来看一个例子。

给定数组nums = [2，3，5]，固定值target=8。找出数组sums中能使数字之和成为目标的所有组合。我们画张图看看吧。

图中的红色表示组合成功。这里只画了选择2的分支。因为图形太大，所以没有画出选择3和选择5的分支。仔细一看，这不就是3-tree吗？好，我们用递归。我们先来看看函数的定义。

privatevoidcombinationSum(Listcur,intsums[],inttarget){}

取出递归模板。

privatevoidcombinationSum(Listcur,intsums[],inttarget){if(终止条件){return;}//逻辑处理//因为是3叉树，所以这里要调用3次//递归调用//递归调用//递归调用//逻辑处理}

这种解决方案不太灵活。如果nums的长度是3，我们递归调用它3次。如果nums的长度是n，那么我们要调用它n次…所以我们可以直接把它写成for循环的形式，如下

privatevoidcombinationSum(Listcur,intsums[],inttarget){//终止条件必须要有if(终止条件){return;}//逻辑处理(可有可无，是情况而定)for(inti=0;i

我们一步一步来看。

1.终止条件是什么？

当target等于0时，说明我们找到了一组组合，我们会把它们打印出来，这样终止条件就好写了。代码如下所示

if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}

2、逻辑处理和递归调用

当我们逐个选择时，如果要选择的值大于目标值，我们就不选择它。如果它没有比target大，我们会将其添加到列表中，表明我们已经选择了他。如果我们选择了他，那么在递归调用时，我们将从目标值中减去选择的值。代码如下所示

//逻辑处理//如果当前值大于target我们就不要选了if(target

终止条件和递归调用已经写出。感觉代码很简单。让我们结合起来看看完整的代码。

privatevoidcombinationSum(Listcur,intsums[],inttarget){//终止条件必须要有if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}for(inti=0;i

我们也使用上述数据进行打印和测试。

publicstaticvoidmain(String[]args){newRecursion().combinationSum(newArrayList(),newint[]{2,3,5},8);}

运行结果如下

我们的思路没有出问题，这难道不是一个惊喜吗？为什么结果是错的？事实上，这是一个典型的分支污染。我们再来看一下图。

当我们选择2时，它是一个分支，当我们选择3时，它是另一个分支。这两个分支的数据应该是互不干扰的，但实际上当我们往下走选择2的分支时，选择2的分支的数据会被携带在列表中。当我们再次选择选择3的分支时，这些数据仍然存在于列表中，所以污染了选择3的分支。一种解决方案是为每个分支创建一个新的列表，如下所示，这样任何一个分支的修改都不会影响到其他分支。

让我们再看一下代码。

privatevoidcombinationSum(Listcur,intsums[],inttarget){//终止条件必须要有if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}for(inti=0;ilist=newArrayList(cur);//把数据加入到集合中list.add(sums[i]);//递归调用combinationSum(list,sums,target–sums[i]);}}

我们看到第13行重新创建了一个列表。我们再打印一次，看看结果。结果完全正确。每组数据的总和是8。

上述每个分支都创建了一个新的列表，所以任何分支修改都只会影响当前分支，而不会影响其他分支。也算是一种解决办法吧。但是每次都是重新创建数据，运行效率很差。我们知道，当执行分支1时，分支1的数据将被带入列表。当执行分支2时，我们实际上并不需要分支1的数据，所以有一种方法是在从分支1执行到分支2时，删除分支1的数据。这就是经常提到的回溯算法。让我们来看看。

privatevoidcombinationSum(Listcur,intsums[],inttarget){//终止条件必须要有if(target==0){System.out.println(Arrays.toString(cur.toArray()));return;}for(inti=0;i

让我们再看一下打印的结果。他们绝对正确。

递归分支污染对结果的影响

分支污染通常会给结果带来致命的误差，但这不是绝对的。我们再举一个例子。生成一个长度为2 n的数组，数组的取值范围为0到(2 n)-1。例如，如果n是3，则生成

[0,0,0][0,0,1][0,1,0][0,1,1][1,0,0][1,0,1][1,1,0][1,1,1]

我们画张图看看吧。

这不是二叉树吗？我们已经讲了很多关于递归的内容。我们直接看代码。

privatevoidbinary(int[]array,intindex){if(index==array.length){System.out.println(Arrays.toString(array));}else{inttemp=array[index];array[index]=0;binary(array,index+1);array[index]=1;binary(array,index+1);array[index]=temp;}}

上面的代码很容易理解。首先是终止条件，然后是递归调用。在调用之前，数组[index]的值将被保存并最终恢复。我们来测试一下。

newRecursion().binary(newint[]{0,0,0},0);

看看打印结果。

结果绝对正确。我们再改一下代码。

privatevoidbinary(int[]array,intindex){if(index==array.length){System.out.println(Arrays.toString(array));}else{array[index]=0;binary(array,index+1);array[index]=1;binary(array,index+1);}}

我们再来看看打印结果。

结果和上面一模一样。一开始没有保存array[index]的值，最后也没有恢复，但是结果一点都不差。原因是上面代码第5行的array[index]=0。这是因为，即使数组[index]在前一个分支执行时被污染，在下一个分支中也会被再次修改。即使改成任何数字，也不会影响最后的结果。例如，当最后一个分支完成时，我们将其更改为100。你在努力。

privatevoidbinary(int[]array,intindex){if(index==array.length){System.out.println(Arrays.toString(array));}else{array[index]=0;binary(array,index+1);array[index]=1;binary(array,index+1);//注意，这里改成100了array[index]=100;}}

当我们看到第10行的时候，我们把数组[index]改成100，最终打印出来的结果不会改变，所以这个分支污染不会造成最终的结果误差。

如果你喜欢这篇文章，也可以关注微信微信官方账号《数据结构与算法》，看更多算法问题。

了解更多信息