二级C++函数：递归函数

简介
在调用函数的过程中，函数本身被直接或间接地称为递归调用。对于初学者来说，递归函数很难理解。现在的程序设计教材对于递归都比较简单，例子从一开始就很难理解。况且，如果不知道函数调用在计算机中的实现过程，理解递归调用就更难了。本文从初学者的角度给出了一些关于递归的解释。

从一道简单的数学题开始
有一个等差数列，第一项为3，容差为2，求第五项a5。我觉得这是所有高中生都会做的题。就像知道通式an=a1+(n-1)k(其中k为容差)被代入一样简单。大家都知道通项是由递推公式推导出来的，直接体现在数学语言中。a3 = a2+2；a4 = a3+2；A5=a4+2。如果知道a5=11，经过五次计算就可以得到a5的值。如果计算机也不知道通式，现在如果我们要计算第一百项，或者第一万项，需要a2=a1+2吗？A3=a2+2......a10000=a9999+2。当然不是，我们可以用递归函数，a2 = a1+2；A3 = A2+2的过程...A10000 = A9999+2是一个递归过程，但是计算机没有我们高中生聪明，不知道怎么直接求解，呵呵。

在计算机中的实现
要明确递归函数的实现，必须知道函数在程序中嵌套调用在计算机中的实现过程。我们来看下面这个函数的调用，这里我们用的是类似C语言的函数形式:
f ()
{...//其他代码
g(a)；//用参数a
return调用函数G()...//函数的返回值
}
/ -。//用参数b调用函数f()
}
主函数在执行过程中调用函数f()，f()本身调用另一个函数g()。那么这种嵌套调用是如何在计算机中实现的呢？在函数执行期间，系统使用堆栈存储器。栈是一种数据结构，即具有特定数据访问模式的容器。堆栈使用的存取方式称为LIFO(后进先出)，即放在后面的数据先离开堆栈，放在前面的数据最后离开。你可以把栈想象成一个和盘子一样大小的水槽，放进去的盘子只能从上面依次拿。不行，只有把上盘拿走了，下盘才能拿出来。堆栈是计算机中非常重要的数据结构，其后进先出的性质也直接关系到函数在计算机中嵌套调用的实现。
当一个函数执行过程中需要调用另一个函数时，需要保留场景，也就是说系统保存所有已有的数据，放入堆栈内存中。这叫推栈。然后，它转到要调用的函数并执行它，并将参数传递给它。当被调用的函数完成后，系统会把刚刚推入堆栈内存的数据全部取出，这个堆栈叫做pop stack。并且会把他调用的函数的返回值返回给原函数。如果在被调用的函数中必须调用其他函数，系统也按照上述方法保存和检索数据。堆栈的性质可以很好地应用于这个过程。
递归函数方面，根据介绍中的意思，上面过程中调用的函数就是调用函数本身。它的实现过程是一样的。是不是很简单？

再看一些例子
在文章的开头，等差数列的例子写成了一个函数(为了方便起见，所有的值都设为整数):
int葛覃(int n，int a1) //需要第n项，a1是已知的第一项
{
If(n = = 1)[/br//如果n=1，返回a1的值，这是递归结束的关键
else
返回葛覃(n-1//不等于1，那么再次调用自己找到第n-1项，返回的结果加上公差2

///。//设置第一项
int a5 =葛覃(5，3)；//递归求解第5项a5
printf(d%，a5)；//Output
}
递归函数调用本身就是一个连续的循环过程，就像循环语句需要条件来阻止它循环，否则就会陷入无限循环，后果不堪设想...哦，我的天啊！因此，if (n = 1)返回a1；是停止递归的条件。
我们来仔细看看a5是怎么找到的。不要太啰嗦。来:
一、当主函数执行到int a5 =葛覃(5，3)时；开始求a5的值。
n=5>1于是gatan()函数再次调用自己，将参数5-1=4和3传递给下一个函数，于是执行葛覃(4，3)；
n = 4 > 1 gatan()函数再次调用自身，并将参数3和3传递给下一个函数，于是执行葛覃(3，3)；
n=3>1执行葛覃(2，3)；
n=2>1执行葛覃(1，3)；
最后，n=1，现在葛覃(1，3)的返回值是3。
葛覃(2，3)；返回值是3+2=5。
葛覃(3，3)；7.
葛覃(4，3)；9.
最后的葛覃(5，3)；返回11，变量a5=11，结果就出来了。
理论上，我们把函数反复自称的过程称为递归过程，每个函数的返回称为一次回推。递归过程把复杂的问题一步步分解，直到出现最简单的情况，就像已知a1=3一样。最简单情况的解得到后，复杂问题的原答案就可以反推了。这里说明一下，我们认为函数的使用者永远是正确的，不会输入-1，0，5.2等不合理的术语。作为参数，所以没有错误检查。