[复杂的递归如何理解]如何理解递归算法

迭代、递推都涉及到循环，而递归则是通过条件判断、递归函数参数值不断向递归的基准条件靠拢，并不断return实现多次递推、回归。

一、递归

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

递归算法的两个前提：

1 原问题可以层层分解为类似的子问题，且子问题比原问题的规模更小；

2 规模最小的子问题具有直接解；

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

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

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

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

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

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

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

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

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

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

递归的消除：循环迭代代替或使用辅助栈来保存参数来模拟系统调用栈工作流程。

优点：代码更简洁清晰，可读性更好递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。

缺点：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能会造成栈溢出。

二、递代

1 利用变量的原值推算出变量的一个新值。如果递归是自己调用自己的话，迭代就是A不停的调用B

2 优点：

1）迭代效率高，运行时间只因循环次数增加而增加；

2）没什么额外开销，空间上也没有什么增加；

3 缺点：

1） 不容易理解；

2） 代码不如递归简洁；

3） 编写复杂问题时困难。

注意： 能用迭代的不用递归，递归调用函数，浪费空间，并且递归太深容易造成堆栈的溢出。

三、迭推

1 递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。递推算法分为顺推和逆推两种。

2 相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。

－End－