Data Structures Algorithms 简明教程
Recursion Algorithms
Recursion
一些计算机编程语言允许模块或函数调用自身。这种技术称为递归。在递归中，一个函数 α 要么直接调用自身，要么调用一个函数 β 而该函数反过来又调用了原来的函数 α 。函数 α 称为递归函数。
Some computer programming languages allow a module or function to call itself. This technique is known as recursion. In recursion, a function α either calls itself directly or calls a function β that in turn calls the original function α. The function α is called recursive function.
Example − 一个调用自身的函数。
Example − a function calling itself.
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}Example − 一个调用另一个函数（而该函数反过来又调用自身）的函数。
Example − a function that calls another function which in turn calls it again.
int function1(int value1) {
if(value1 < 1)
return;
function2(value1 - 1);
printf("%d ",value1);
}
int function2(int value2) {
function1(value2);
}Properties
一个递归函数可以像循环一样无限运行。为了避免递归函数无限运行，递归函数必须具有以下两个特性：
A recursive function can go infinite like a loop. To avoid infinite running of recursive function, there are two properties that a recursive function must have −
-
Base criteria − There must be at least one base criteria or condition, such that, when this condition is met the function stops calling itself recursively.
-
Progressive approach − The recursive calls should progress in such a way that each time a recursive call is made it comes closer to the base criteria.
Implementation
许多编程语言通过 stacks 实现递归。通常，每当一个函数 ( caller ) 调用另一个函数 ( callee ) 或自身作为被调用方时，调用方函数会将执行控制权转移到被调用方。这个转移过程还可能涉及将一些数据从调用方传递到被调用方。
Many programming languages implement recursion by means of stacks. Generally, whenever a function (caller) calls another function (callee) or itself as callee, the caller function transfers execution control to the callee. This transfer process may also involve some data to be passed from the caller to the callee.
这意味着，调用方函数必须暂时挂起其执行，并在执行控制权从被调用方函数返回时继续执行。在这里，调用方函数需要从它暂停执行时的执行点准确地开始。它还需要它当时正在处理的确切相同的数据值。为此，将会为调用方函数创建一个激活记录（或堆栈帧）。
This implies, the caller function has to suspend its execution temporarily and resume later when the execution control returns from the callee function. Here, the caller function needs to start exactly from the point of execution where it puts itself on hold. It also needs the exact same data values it was working on. For this purpose, an activation record (or stack frame) is created for the caller function.
这个激活记录保存有关局部变量、形式参数、返回地址和传递给调用方函数的所有信息。
This activation record keeps the information about local variables, formal parameters, return address and all information passed to the caller function.
Analysis of Recursion
有人可能会争论为何使用递归，因为相同的任务可以用迭代来完成。第一个原因是，递归使程序更具有可读性，并且由于采用了最新的增强型 CPU 系统，因此递归比迭代更有效。
One may argue why to use recursion, as the same task can be done with iteration. The first reason is, recursion makes a program more readable and because of latest enhanced CPU systems, recursion is more efficient than iterations.
Time Complexity
对于迭代，我们采用迭代次数来计算时间复杂度。同样，对于递归，假设一切都是常数，我们尝试找出进行递归调用的次数。对函数进行一次调用为 Ο(1)，因此递归调用 (n) 次将使递归函数 Ο(n)。
In case of iterations, we take number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).
Space Complexity
空间复杂度是指模块执行所需的额外空间量。对于迭代，编译器几乎不需要任何额外空间。编译器不断更新在迭代中使用的变量值。但是在递归的情况下，系统需要在进行每次递归调用时存储激活记录。因此，人们认为递归函数的空间复杂度可能高于具有迭代的函数。
Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation record each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.