1 函数调用

当一个函数调用另一个函数时，并不是去复制被调函数的全部代码到内存，而是采用代码共享的方式。也就是它们都是调用同一个函数的代码，而系统为每一次调用开辟一组存储单元，用来存放本次调用的返回地址以及被中断的函数的参数值。这些单元以栈的形式存放，每调用一次进栈一次，当返回时执行出栈操作，把当前栈顶保留的值送回相应的参数中进行恢复，并按栈顶中的返回地址，从断点继续执行。

如有以下一个简单实例：（为了解较嵌套的复杂关系，特意把简单问题复杂化了）

运行效果：

调用栈的情形：

2 递归函数和递归调用

递归函数（recursive function）或递归调用（recursion）是通一个判断选择（递归条件）不断调用自身、并能通过初始条件返回求值。是函数嵌套调用的一种特殊情形。大部分编程语言都支持递归操作，如C\C++。

递归算法，简而言之就是一种函数调用函数自身来完成算法设计的方法。是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。

递归这种函数实际上只知道如何解决最简单的情况，或者所谓的基本情况。如果函数为解决基本情况而调用，那么它将简单地返回一个结果。如果函数为解决较复杂的问题而调用，那么它通常会把问题分成两个概念性的部分：一部分是函数知道如何去做的，另一部分是函数不知道如何去做的。为了使递归可行，后一部分必须和原来的问题相类似，但是相对稍微简单一些或者稍微小一些。这个新问题看起来和原来的问题颇为相似，因为函数启动（调用）自己的一个全新副本用于解决这一问题－这就是递归调用，也称为递归步骤。

递归之所以能实现，是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝，这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础，是使得递归成为可能。假定某个调用函数调用了一个被调用函数，再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归，因为它发生在调用函数的当前执行过程运行完毕之前。而且，因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量，原先的参数和变量将不受影响，所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。

程序员需保证递归函数不会随意改变静态变量和全局变量的值，以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程，并且返回到顶层。

2.1 递归需满足的条件

I 需要解决的问题可以转化为一个或多个子问题来求解，而这些子问题的求解方法与原问题完全相同，只是在数量和规模上不同。也就是说，原问题可以层层分解为类似的子问题，且子问题比原问题的规模更小；

II 递归调用的次数必须是有限的；

III 必须有初始条件和递归条件，前一个条件用来终止递归，并回退；规模最小的子问题具有直接解。

2.2 可以适用递归的情形

I 定义是递归的，有许多数学公式、数列和概念的定义是递归的，如阶系着n!、斐波那契数列等；

II 数据结构是递归的。如单链表、二叉树的遍历等；

III 问题的求解方法是递归的。如梵诺塔问题。

2.3 递归调用工作栈

递归进层(i→i+1层)系统需要做三件事：

I 保留本层参数与返回地址；

II为被调用函数的局部变量分配存储区，给下层参数赋值；

III 将程序转换到被调用函数的入口；

而从被调用函数返回调用函数之前，递归退层(i←i+1层)系统也应完成三件工作：

I 保存被调函数的计算结果；

II 释放被调函数的数据区，恢复上层参数；

III 依照被调用函数保存的返回地址，将控制转换回调用函数。

当递归函数调用时，应按照“先调用后返回”的原则处理调用过程，因此上述函数之间的信息传递和控制转换必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，而当从一个函数退出时，就释放它的存储区，显然，当前正在运行的函数的数据区必在栈顶。

每层递归所需信息构成一个工作记录，包括所有的实在参数、所有的局部变量以及上一层的返回地址。每进一层递归，就产生一个新的工作记录压入栈顶。每退出一层递归，就从栈顶弹出一个工作记录。因此当前执行层的工作记录必为递归工作栈栈顶的工作记录，称这个记录为活动记录，并称指示活动记录的栈顶指针为当前环境指针。而这个递归工作栈是由系统来管理的，无须用户操心，所以用递归编制程序非常方便。

2.4 递归求阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。

unsigned long factorial(unsigned long number)

{

if(number<=1);

reuturn 1;

else

return number*factorial(number-1);

}

调用栈的情形：

从以上过程可以看出，每递归调用一次，就需进栈一次，每当遇到递归出口就完成本次执行时，需退栈一次，并恢复参数值，当全部执行完毕时，栈应为空。

所以，递归调用主要分两步走，第一步是分解过程，即用递归体将“大问题”分解成“小问题”，直到递归出口（初始条件）为止，然后进行第二步的求值过程，即用已知“小问题”来计算“大问题”。

2.2 Fibonacci函数的递归实现

斐波那契兔子问题 (Fibonacci rabbit problem)是意大利数学家斐波那契(Fi-bonacci , L.)在他的名著《算法之书》中提出的一个问题。由一对小兔子开始，小兔生长两个月就成为大兔，假定每对大兔每月能生产一对小兔，一年后可以繁殖成多少对兔子?这个问题导致了著名的数列:1,1,2,3,5,8,13,21,34,55,89,144,·…它是一个线性递归数列。

int fib(int n)

{

if (n==1 || n==2)

return 1;

else

return (fib(n-1)+fib(n-2));

}

//因为是一对小兔出生后两个月即可繁殖，所以第n个月兔子的数量是前一个月的兔子数量加上繁殖的数量（面繁殖的数量等于前一个月的前一个月的兔子数量）。

递归算法的调用、回归关系可以用一棵递归树来表示递归算法执行过程中的分解和求值过程，是对递归工作栈的模拟。

阶乘的递归是若干步骤的调用后有若干步骤的回归求值。斐波那契的递归较复杂，分解调用与回归求值交替进行，循环反复，直到求出最终值。

在递归函数的执行过程中，其形参会随着递归调用发生变化，但每次调用后恢复为调用前的形参，将递归函数的非引用型形参的取值称为状态（递归函数的引用类型形参在执行后会回传给实参，有时类似全局变量，不作为状态的一部分），在调用过程中状态会发生变化，而一次调用后会自动恢复为调用前的状态。

2.3 递归结构也可以用迭代循环结构来替代

递归一般用一个选择结构来实现，不断调用自身，就形成了一个循环，所以想结束递归，就必须有终止递归的初始条件部分，否则就会出现无限递归（即无限循环）。

尾递归是指递归调用语句只有一个，而且是处于算法的最后，尾递归是单向递归的特例。阶乘的递归算法就是尾递归。一般来说尾递归可以用迭代（循环）来实现的。如计算1到n之和：

不是尾递归的递归可以使用辅助栈来保存参数来模拟系统调用栈工作流程来消除递归。

－End－