[数据结构与算法]递归算法

1.递归的概念
若一个对象部分的包含它自己或用它自己给自己定义，则称这个对象是递归的。若一个过程直接或间接地调用自己，则称这个过程是递归过程。
2.什么时候使用递归
1）问题的定义是递归的
如求n的阶乘等，问题的求解过程可以将其递归定义直接转换为对应的递归算法。
2）数据结构是递归的
如单链表等
3）问题的求解方法是递归的
如：是在有序数组中查找一个数据元素是否存在的折半查找算法
3.递归算法的特点
将问题分解成为形式上更加简单的子问题来进行求解。

递归的步骤：
递归算法解题通常有三个步骤：
1）分析问题、寻找递归：找出大规模问题与小规模问题的关系，这样通过递归使问题的规模逐渐变小。
2）设置边界、控制递归：找出停止条件，即算法可解的最小规模问题。
3）设计函数、确定参数：设计函数体中的操作及相关参数。

递归求解过程

自上而下将问题分解、求解，再自下而上引用、合并，求出最后的答案。是一种分而治之的算法设计方法。

例如下类代码

int fact(int n)
{ int x,y;
if (n<0) return -1;
if(n==0) return 1;
else { x=n-1; y=fact(x); return n*y; }
}
void main()
{ int fn;
fn=fact(3);
}