很多编程语言(比如 C、C++、Java、Python 等)都支持函数(方法、模块)调用自身,这种解决问题的方法称为递归。
以 C 语言为例,函数调用自身的方式有 2 种,分别为:
1) 函数直接调用自身,例如:
int funciton(int value) {//递归出口if (value < 1) {return 0;}//调用自身function(value-1);}
2) 函数间接调用自身,例如:
int funciton1(int value) {//递归出口if (value < 1) {return 0;}//调用另一个函数function2(value-1);}int function2(int value) {//调用function1()函数funciton1(value);}
为了防止函数无限地调用自身(死循环),递归函数(方法、模块)必须具备以下 2 个特征:
递归函数(模块、方法)内至少具备 1 个结束递归调用的限制条件,该条件满足时,函数停止调用自身;
函数调用自身的过程,应不断朝着满足限制条件的方向发展。
递归的底层实现
每当一个函数(称为调用者)调用另一个函数或者它自身(称为被调用者)时,调用者需要将执行代码的权利移交给被调用者,传输过程中还可能涉及一些数据的传递。这也就意味着,调用者必须暂停执行,直至被调用者执行完成,它才能继续执行。
为了确保调用者能够从暂停状态继续执行,当发生递归调用(或者函数调用)时,多数编程语言都使用栈结构保存调用者的状态信息,包括暂停时局部变量的值、形式参数的值等等。
图 1 给您描述了栈结构实现递归调用的过程:
图 1 递归调用的底层实现
图 1 中,F(n) 调用了 F(n-1),所以 F(n) 会暂停执行,同时暂停时的状态信息也会入栈保存;同样,F(n-1) 调用了 F(n-2),所以 F(n-1) 暂停执行并入栈;F(n-2) 调用了更深层的函数,所以 F(n-2) 暂停执行并入栈......直到递归过程满足限制条件,每次都会取栈中最顶端的函数出栈并继续执行,直至 F(n) 出栈,整个递归过程才算完成。
递归算法的应用场景很广泛,例如解决斐波那契数列问题、求 n! 等。此外很多算法都需要借助递归实现,例如分治算法、回溯算法等。