2016-04-07-digui.md

layout	title	category	date
post	递归【总结】	算法	2016-04-07 19:45

专题：

定义：

一个函数自己直接或间接调用自己

递归满足三个条件

1.递归必须得有一个明确的终止条件 2.该函数所处理的数据规模必须在递减 3.这个转化必须是可解的

举列：

1. 求阶乘
2. 1+2+3+4+5+6+7+...1000的和
3. 汉诺塔
4. 走迷宫

###循环和递归

能用循环就不要用递归

递归：

1. 易于理解
2. 速度慢
3. 存储空间大

循环：

1. 不易理解
2. 速度快
3. 存储空间小

###代码：求阶乘

n这个规模的解决，可以借助于于n-1这个规模的解决。那么这个规模在递减。

//假定n的值是1或大于1的值
long f(long n)
{
    if(1 == n)
    {
        return 1;
    }
    else
    {
        return f(n-1) * n;
    }
}

###应用

树和森林就是以递归的方式定义的。

数和图的很多算法都是以递归来实现的。

很多数学公式就是以递归的方式定义的。

斐波那契数列：

1 2 3 5 8 13 21 34