递归算法（具体问题具体分析）

1.递归概念

程序调用自身的编程技巧称为递归（recursion）。递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中由直接或间接调用自身的一种方法，他通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归就是在运行的过程中调用自己。

function recursion（参数）{

.........

recursion(参数); //函数调用自身，

........

}

recursion(参数)

2.构成递归需具备的条件：

1.子问题须与原始问题为同样的事，且更为简单。

2.不能无限制地调用本身，须有个出口，化简为非递归状况处理。

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其他基本情况。

递归关系就是实体自己和自己建立关系。

3.递归应用

递归算法一般用于解决三类问题：

1.数据的定义是按递归定义的。（斐波纳契（Fibonacci）函数）

2.问题解法按递归算法实现

这类问题虽则本身没有明显的递归结构，单用递归求解比迭代求解更简单，如Hanoi问题

3.数据的结构形式是按递归定义的

如二叉树、广义表等，由于结构本身固有的递归特性，则他们的操作可递归地描述。

4.递归的缺点：

递归算法解题相对常用的算法如普通循环等，运行效率较低。因此应该尽量避免使用递归，除非没有更好的算法或者某种特定情况，递归更为适合的时候。在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。