1.递归算法深入学习第一天

致年轻的我们

先来一个简单的递归算法，这是递归算法求阶乘：

#include <stdio.h>

long fun(int n)
{ 
        if(n == 0)        return 1;
        else        return(n*fun(n-1));
}

int main()
{
        //5*4*3*2*1=120
        printf("%d\n",fun(5));
        return 0;
}

对于能不用递归解决的问题，不建议使用递归解决。而有些问题只能通过递归算法解决（例如汉诺塔），而有些问题，递归算法效率更高（全排列问题）。
上述例子图解
           | 5x
           |            | 4x
fun(5) |            |            | 3x
           | fun(4) |            |            | 2x
                        | fun(3) |            |            | 1x
                                     | fun(2) |            |
                                                  | fun(1) |
                                                               | fun(0) == 1
*********************************分割线*********************************
契波那契数列是计算机学科中一个重要的数列，它的值如下
0 1 1 2 3 5 8 13 21 34 55 ......
数列规律是后一项是前两项之和
实现代码如下：

#include <stdio.h>

int Finonacci(int n)
{
        if(n == 0)        return 0;
        else if(n == 1)        return 1;
        else return(Finonacci(n-1) + Finonacci(n-2));
}

int main()
{
        //0 1 2 3 4 5 6 7  8  9  10 
        //0 1 1 2 3 5 8 13 21 34 55
        printf("%d\n",Finonacci(10));
        return 0;
}

简易图解：
F(5) |
       | F(4) |
       |        | F(3) |
       |        |        | F(2) |
       |        |        |        | F(1) ==1
       |        |        |   +   |    +
       |        |   +   |        | F(0) ==0
       |   +   |        |   
       |        |        | F(1) == 1
       |        |   
       |        | F(2) |
       |                 | F(1) ==1
       |                 |    +
       |                 | F(0) ==0
       | F(3) (注：这个就不展开了)
数学形式如下
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
*********************************分割线*********************************
汉诺塔问题
汉诺塔：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在第一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门借助第二根柱子把圆盘从下面开始按大小顺序重新摆放在第三根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
这是一个典型的只能用递归，而不能使用其他方法解决的问题。

解决问题思路：
1.首先借助第3根柱子把63个圆盘放到第2根柱子
2.把第64个盘子直接从第1根柱子放到第3根柱子
3.借助第1根柱子把第2根柱子的63个圆盘放到第3根柱子
以上只不过是大致的步骤，1 3步骤还需要细分
按照此思路代码实现

#include <stdio.h>

//n是需要移动的盘子数目 
void hanoi(int n,char start,char temp,char finish)
{
        if(n == 1)
        {
                printf("%c -> %c\n",start,finish);//如果只有一个盘子，当然是直接从start到finish 
        }
        else
        {
                hanoi(n-1,start,finish,temp);//这是上述的第一步，把n-1个盘子借助finish移动到temp 
                printf("%c -> %c\n",start,finish);//这是第二步，把第n个盘子直接从start移动到finish
                hanoi(n-1,temp,start,finish);//这是第三步。借助start把temp上的n-1个圆盘放到finish上 
        }
}

int main()
{
        printf("start\n");
        //3个盘子时 
        hanoi(3,'1','2','3');
        printf("end\n");
        return 0;
}

今天就到这里明天继续。
欢迎加入编程爱好者交流群：518384767，期待您的加入。

致年轻的我们

一楼备用