递归函数 - Justin知识库

　　编程语言中，我们习惯将函数（方法）调用自身的过程称为递归，调用自身的函数称为递归函数，用递归方式解决问题的算法称为递归算法。

调用方式

函数(方法)调用自身的实现方式有 2 种，分别是：

直接调用自身，例如:

int function(/*....*){
//......
//调用自身
function(/*...*);
//......
}

间接调用自身，例如:

int funciton1(/*...*/) {
 //......
//调用另一个函数
function2(/*...*/);
 //......
}
 int function2(/*...*/) {
 //......
 //调用function1()函数
 funciton1(/*...*/);
 //......
}

在上面程序中，function1() 函数内部调用了 function2() 函数，而 function2() 函数内部又调用了function1() 函数，也就是说 function1() 函数间接调用了自身。

具体示例

在设计递归函数时，我们要为它设置一个结束递归的“出口”，否则函数会一直调用自身(死循环)，直至运行崩溃。

接下来我们使用以“递归方式求n!”为例，来展示一个正确的递归函数。
首先要知道 n! 指的是求 1x2x3...n 的值，如下程序中的 factirial() 就是实现求 n! 的递归函数：

#include <iostream>
using namespace std;

int factorial(int n){
    //递归的出口
    if(n ==1 || n == 0){
       return 1;
    }
    //函数调用自身
    return n * factorial(n - 1);
}

int main()
{
   int n; 
   scanf("%d",&n);
   cout << n << "! = " << factorial(n) << endl;
   return 0;
}

注意：除非变量 n 的值为 1 或 0，否则 factorial() 函数会一直调用自身。

最后再假设输入 n 的值为 4，梳理一遍 factorial()（以下简称f(n)）函数的执行过程，

调用过程：

调用 f(4) 时，由于形参 n 的值为 4，不等于 0 或 1，所以执行 4 * f(3) 并返回它的值。为了求出这个表达式的值，必须先执行 f(3) 并得到它的返回值，所以编译器转而求 f(3) 的值，4 * f(3) 的求值被搁置，等待后续再计算；
调用 f(3) 时，由于形参 n 的值为 3，不等于 0 或 1，所以执行 3 * f(2) 并返回它的值。为了求出这个表达式的值，必须再执行 f(2) 并得到它的返回值，所以编译器转而求 f(2) 的值，3 * f(2) 的求值继续被搁置，等待后续再计算；
调用 f(2) 时，由于形参 n 的值为 2，不等于 0 或 1，即与上一致，则编译器转而求 f(1) 的值；
调用 f(1) 时，由于形参 n 的值为 1，函数的返回值为 1。

返回过程：

f(1) 的返回值为 1，先前被搁置的 2 * f(1) 的值就可以计算出来，因此 f(2) 的返回值为 2；
知道了 f(2) 的返回值为 2，被搁置的 3 * f(2) 的值也可计算出来，因此 f(3) 的返回值为 6；
同理可得到 f(4) 的返回值为 24，即 f(4) = 1 × 2 × 3 × 4 = 24。

关于递归

递归函数与循环有很多类似之处。可以认为循环和递归函数是能够相互转换的，但递归会随着调用次数过多从而增加内存空间开销，也就是重复的进行压栈，内存得不到释放，循环往复导致内存占满溢出。一般都会以空间换时间的方法，也可以借助堆栈来消除递归。