关于笔算递归的通用算法——迭代

递归是是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象。

在我的印象中，我第一次接触递归是在C语言书中，让求n！的解，记得程序如下：

<span style="font-size: 18px;">int fun(int n){
	if(n==1){
		return 1;
	}else{
		return fun(n-1);
	}
}</span>

函数的调用对应着入栈，调用的结束对应着出栈，如上面的过程，假如传入的参数为3，程序run的时候，会先将fun(3)入栈，接着会将fun(2)入栈，最后会将fun(1)入栈，计算结束之后，会按照fun(1),fun(2),fun(3)依次出栈。从上面的过程我们可以看出，在每次计算的时候，该项的结果都会依附前一项，前一项的结果依附前一项的前一项，以此类推，知道递归的终止条件。这是计算机在遇到递归的时候的做法。

假如我们现在在进行人生很重要的一次笔试，笔试题中给出了一个递归函数，给了你一个参数，你还要像计算机一样子，从外到内一层一层计算吗？如果从外到内计算的话，最后的结果很可能是你自己把自己给绕进去了。

下面提供一种比较通用的人算递归的解法：

从递归终止的条件开始，一项项的向后推，如果递归函数的参数有一个，则建立一个一维数组，如果参数有n个，则建立一个n维数组。还用上面的例子，首先建立一个数组，长度为3(因为给定的参数为3，而且在函数中，不会出现比参数更大的值)，先计算fun(1),结果为1，再计算fun(2)，fun(2)依附fun(1)，fun(1)的结果在前面已经算出来了，存放在一维数组中，所以可以直接用，不用再算，以此类推，最后可以很容易算出fun(3)。

如果要给上面的算法归类，它应该是迭代算法。迭代算法是只根据迭代公式（递推公式），从起始项（递归终止项）开始，一步步计算，直到得到想要的结果。

下面再看一个例子，ackerman递归的求解算法，该算法出现在过一家大公司的笔试题中，当时直接就被搞晕了，结束之后，就总结一下人解递归的方法，于是就有了这篇博客。

ackerman算法程序如下：

<span style="font-size: 18px;">int ack(int m,int n){
	if(m==0){
		return n+1;
	}else if(n==0){
		return ack(m-1,1);
	}else{
		return ack(m-1,ack(m,n-1));
	}
}</span>

给定的参数为m=3，n=3，即让求解ack(3,3)的值，当时一看到题，就直接从外到内一层一层的算，没算几步，就把自己给绕进去了。如果用动态规划的话，首先建立一个二位数组，大小应该3*3的，如果不够还需要增加大小。
其实在写程序的时候，应该尽量避免使用递归，将递归转换成迭代算法，可以减少很多运算，因为使用递归的时候，有些值已经在前面算出来过了，在后面还需要再算一次，迭代可以很好解决这一弊端。或许有人该问了，既然递归可以用迭代代替，为什么还有递归？个人觉得，递归是一种思想，可以利用这种思想解决问题，在实现的时候，可以转换成迭代。