如何简单的理解递归

递归"/>

如何简单的理解递归

递归这玩意不知道有多折磨人，我折腾了快1天了也没有搞懂，直到看到这篇文章：《Linux C编程》才恍然大悟，理解递归其实也就是不要尝试理解它，你只要越理解你就会越糊涂，就绕进去出不来。

事实上，我们并不是每个函数都需要跟进去看执行结果的，比如我们在自己的函数中调用printf函数时，并没有钻进去看它是怎么打印的，因为我们相信它能完成打印工作。

如果你相信你正在写的递归函数是正确的，并调用它，然后在此基础上写完这个递归函数，那么它就会是正确的，从而值得你相信它正确。

以上两句话就是要明白一个道理：不要把自己放进递归函数中，放进一些简单的递归如阶乘，可能你还能理解，但是换个求全排列这样复杂点的递归函数你可能就懵逼了。你要站在一个上帝视角去看待问题，就像走迷宫，你不知道正确的路线就往里面走，那么你一定会迷路的，但是如果我站在高处的地方把正确的路线找到了，那我走迷宫的时候就不会迷路了。所以不要主观的看待，客观的把它当做一个人，你交给他的任务他一定能够完成的，你也千万别替他安排任务该如何去完成。

一般来说求递归要有递归边界和递归方程式，其中递归方程式可能就有抽象的那种，如全排列，这种你就按照一般的程序思维去写代码，对于有递归方程式的那种最简单了。下面我举两个例子：

#include<iostream>
using namespace std;
void show(int a[],int i)
{if(i==0){ cout<<a[i]<<" ";return;}//cout<<a[i]<<" ";    ///1show(a,i-1);cout<<endl;//cout<<a[i]<<" ";   ///2
}
int main()
{int a[7]={1,2,3,4,5,6,7};show(a,6);return 0;
}

这个简单的例子是用递归输出数组元素。这该如何理解呢？show(a,i-1)前面被注释的///1这一行如若打开，将会打印7 6 5 4 3 2 1.这可以用一般递归思维的方法去理解还是可以理解的先递再归。但是用上面描述得方法去理解就是：打印a[6]然后在show(a,5),也就是a[5],不要去想为什么，只要明白show(a,5)能够打印出a[5]就行了，然后最终的结果是7 6 5 4 3 2 1；

show(a,i-1)前面被注释的///2这一行如若打开///1这行注释掉。那就要这样理解了：本来a[7]={1 ,2,3,4,5,6,7};但是主函数中show（a,6）表示从后往前的。在回到递归函数的///2这一行来，其中show（a，i-1）在cout前，我们可以这样理解，我相信show（）这个函数，它可以吧show(a,5)也就是a[5]这个给显示出来，然后才打印a[6],也就是6 7；同理也就可以表示打印1 2 3 4 5 6 7了；

在说下全排列的例子：

#include<cstdio>
const int maxn=11;
int n,P[maxn],hashTable[maxn]={false};//hashTable记录其是否在P中void generateP(int index){if(index==n+1)//边界条件 ,已经处理完排列的1-n位 {for(int i=1;i<=n;i++){printf("%d",P[i]); }printf("\n");return;}for(int x=1;x<=n;x++)///枚举1-n将x填入P[index]{if(hashTable[x]==false)//如果x不在P[1]-P[index]中时{P[index]=x;hashTable[x]=true;generateP(index+1);//处理第index+1号位，只有处理完了下一个才能表示上一个处理完全了； hashTable[x]=false;//处理完了p[index]为x的子问题将其还原 } } }int main(){n=3;generateP(1);return 0;} 

这个例子按照一般的常规的理解法去理解是很难理解的，但是按照上面说的不要去想它是怎么实现的，只要相信他，就能很好的解出来了，就按照一般的程序去写，忘记他是递归，当运行到递归那行的时候，知道他是个函数调用就行了也就是调用了这个函数我就能完成下一步了，而我不需要去理解怎么实现的。如果去走一遍那么会走进去出不来的。

这样说可能有点佛性，但理解这种想法了就会恍然大悟的。