递归是从函数本身出发逐次上溯调用其本身求解过程

1函数调用当一个函数调用另一个函数时，并不是将被调用函数的所有代码复制到内存中，而是共享代码。即都是调用同一个函数的代码，系统为每次调用开辟一组存储单元，存储这次调用的返回地址和被中断函数的参数值。这些单元以堆栈的形式存储。它们每次被调用时都会被推入堆栈一次，当它们被返回时，就会被弹出。保留在当前堆栈顶部的值被发送回相应的参数进行恢复，并根据堆栈顶部的返回地址从断点继续执行。

比如有一个简单的例子:(为了理解嵌套的复杂关系，故意把简单的问题复杂化)

操作效果:

调用堆栈情况:

2递归函数与递归调用递归函数或递归是通过一个判断选择(递归条件)不断调用自身，并能通过初始条件返回求值。这是函数嵌套调用的一个特例。大多数编程语言都支持递归操作，比如C\C++。

递归算法，简而言之就是一个函数调用自己来完成算法设计的方法。它是一个子问题，将一个问题转化为一个规模缩小的类似问题。然后递归调用函数(或过程)来表示问题的解。

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

递归之所以能够实现，是因为函数的每个执行过程在堆栈中都有自己的形参和局部变量的副本，而这些副本与函数的其他执行过程无关。这种机制是大多数编程语言实现子程序结构的基础，它使递归成为可能。假设一个调用函数调用一个被调用函数，然后假设被调用函数反过来调用调用函数。这第二次调用被称为调用函数的递归，因为它发生在调用函数的当前执行过程完成之前。而且由于原调用函数和当前被调用函数在栈的较低位置都有一组独立参数和独立变量，所以原参数和变量不会受到影响，所以递归可以正常工作。程序遍历这些函数的过程称为递归下降。

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

2.1递归I要满足的条件待解决的问题可以转化为一个或多个待解决的子问题，这些子问题的求解方法与原问题完全相同，只是数量和规模不同。也就是说，原问题可以层层分解成相似的子问题，子问题比原问题更小；

必须限制递归调用的次数；

三。必须有一个初始条件和一个递归条件。前一个条件用于终止递归和回滚；最小的子问题有直接解。

2.2可以应用递归的情况I定义是递归的，有很多数学公式、数列、概念的定义都是递归的，比如顺序是和n捆绑的！斐波那契数列等。

数据结构是递归的。比如单链表和二叉树的遍历；

问题III的解是递归的。比如法诺塔问题。

2.3递归调用工作堆栈递归进入层(i→i+1层)系统需要做三件事:

我保留这一层的参数和返回地址；

II .为被调用函数的局部变量分配存储区域，并为较低的参数赋值；

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

在从被调用函数返回到调用函数之前，递归后层(i←i+1层)系统还应该完成三项任务:

我保存调优函数的计算结果；

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

三。根据被调用函数保存的返回地址，将控制权转回调用函数。

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

每一层递归所需的信息构成一个工作记录，包括所有实参数、所有局部变量和前一层的返回地址。每一层的递归产生一个新的工作记录，并将其推到堆栈的顶部。退出每一层递归，从栈顶弹出一条工作记录。因此，当前执行层的工作记录必须是递归工作栈顶部的工作记录，称为活动记录，指示活动记录的顶部指针称为当前环境指针。这个递归的工作栈是系统管理的，用户不用担心，用递归编程非常方便。

2.4递归阶乘正整数的阶乘是所有小于等于该数的正整数的乘积，0的阶乘是1。自然数n的阶乘写成n！。1808年，Keyston Kaman引入了这个表达。

无符号长阶乘(无符号长数字)

如果(数字 lt=1);

reuturn 1；

其他

返回数字*阶乘(数字-1)；

调用堆栈情况:

从上面的过程可以看出，每次递归调用，都要推栈一次。每当遇到递归退出来完成这个执行时，就需要推栈一次，恢复参数值。当所有的执行完成后，堆栈应该是空。

所以递归调用主要分两步。第一步是分解过程，即“大问题”被递归体分解成“小问题”，直到递归退出(初始条件)，然后第二步是求值过程，即利用已知的“小问题”计算“大问题”。

2.2斐波那契函数的递归实现斐波那契兔子问题是意大利数学家斐波那契(l .)在其名著《算法之书》中提出的问题。从一对兔子开始，兔子生长两个月，变成大兔子。假设每对大兔子每个月能产一对兔子，一年后能育成多少对兔子？这个问题引出了著名的数列:1，1，2，3，5，8，13，21，34，55，89，144，…是线性递归数列。

中间纤维(中间纤维)

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

返回1；

其他

返回(fib(n-1)+fib(n-2))；

//因为一对兔子出生后两个月就可以繁殖，所以第n个月的兔子数就是上个月的兔子数加上品种数(脸品种数等于上个月的兔子数)。

递归算法的调用和回归关系可以用一棵递归树来表示，递归树是递归工作栈的模拟。

阶乘的递归是几个步骤调用后的几个步骤的回归求值。斐波那契的递归比较复杂，分解调用和回归求值交替进行，循环往复，直到得到最终值。

在递归函数的执行过程中，它的参数会随着递归调用而改变，但在每次调用后，它会返回到调用前的参数。递归函数的非引用参数的值称为状态(递归函数的引用类型参数在执行后会返回给实参，有时类似于全局变量，但不作为状态的一部分)。状态会在通话过程中发生变化，一次通话后会自动恢复到通话前的状态。

2.3递归结构也可以用迭代循环结构代替。一般是通过选择结构来实现的。不断地调用自己，就形成了一个循环。因此，如果要终止递归，就必须具备终止递归的初始条件，否则就会出现无限递归(即无限循环)。

尾递归是指递归调用语句只有一条，而且是在算法的末尾。尾部递归是单向递归的特例。阶乘的递归算法是尾递归。一般来说，尾部递归可以通过迭代(循环)来实现。比如计算1到n的和:

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

-结束-