Data Structures Algorithms 简明教程
Recursion Algorithms
Recursion
一些计算机编程语言允许模块或函数调用自身。这种技术称为递归。在递归中，一个函数 α 要么直接调用自身，要么调用一个函数 β 而该函数反过来又调用了原来的函数 α 。函数 α 称为递归函数。
Example − 一个调用自身的函数。
int function(int value) {
if(value < 1)
return;
function(value - 1);
printf("%d ",value);
}Example − 一个调用另一个函数（而该函数反过来又调用自身）的函数。
int function1(int value1) {
if(value1 < 1)
return;
function2(value1 - 1);
printf("%d ",value1);
}
int function2(int value2) {
function1(value2);
}Properties
一个递归函数可以像循环一样无限运行。为了避免递归函数无限运行，递归函数必须具有以下两个特性：
-
Base criteria − 必须至少有一个基本标准或条件，即满足此条件时，函数停止递归调用自身。
-
Progressive approach − 递归调用应该逐步进行，即每次进行递归调用时，它都更接近基本标准。
Implementation
许多编程语言通过 stacks 实现递归。通常，每当一个函数 ( caller ) 调用另一个函数 ( callee ) 或自身作为被调用方时，调用方函数会将执行控制权转移到被调用方。这个转移过程还可能涉及将一些数据从调用方传递到被调用方。
这意味着，调用方函数必须暂时挂起其执行，并在执行控制权从被调用方函数返回时继续执行。在这里，调用方函数需要从它暂停执行时的执行点准确地开始。它还需要它当时正在处理的确切相同的数据值。为此，将会为调用方函数创建一个激活记录（或堆栈帧）。
这个激活记录保存有关局部变量、形式参数、返回地址和传递给调用方函数的所有信息。
Analysis of Recursion
有人可能会争论为何使用递归，因为相同的任务可以用迭代来完成。第一个原因是，递归使程序更具有可读性，并且由于采用了最新的增强型 CPU 系统，因此递归比迭代更有效。
Time Complexity
对于迭代，我们采用迭代次数来计算时间复杂度。同样，对于递归，假设一切都是常数，我们尝试找出进行递归调用的次数。对函数进行一次调用为 Ο(1)，因此递归调用 (n) 次将使递归函数 Ο(n)。