基础算法之二:递归

基础算法之二:递归

递归用处很广,可以将复杂问题简单化。

很多问题都可以使用递归算法或结合递归算法得到解决。

那么,设计递归算法的关键是什么? 其关键之处在于,正确分析出2种类型的节点:出口节点和入口节点

一 算法关键: 出口节点 , 入口节点

递归问题可看做是由各个节点构成,而所有节点只能分为出口节点、入口节点两类。

1)出口节点: 可直接计算此节点的值,不需借助其他节点

那什么情况下,不必再递归了呢?

确定结果了,自然就不用继续递归了,这也是递归的出口, 递归的根基。 所以这个根基必须判断好,这是递归是否成功的一个关键之处。

因此,第一个的关键是:确定哪些节点是出口节点。

2)入口节点: 无法直接计算此节点的值,但此节点的值可根据后续节点的值计算。

入口节点与后续节点的数学或逻辑关系, 且如何用递归方式表示这个关系,则是递归算法的第二个关键。

二 什么问题可以用递归来处理?

递归的过程,就是搜索的过程,搜索一个个的节点,找到出口节点。

若问题满足下面条件,则可递归解决:

      A)  问题可看做为在很多节点中进行搜索
      B)  这些节点或者为出口节点 或者为入口节点
      C)  入口节点和后续节点间的关系 可用递归方式描述
      D)  出口节点在入口节点的后续路径中

下面举几个例子:

1 递增

第5个人的年龄比第4个的年龄大2岁,第4个人的年龄比第3个的年龄大2岁,第3个人的年龄比第2个的年龄大2岁,第2个人的年龄比第1个的年龄大2岁,第1个的年龄10岁.

int age(int n)
{ 
    int c;
     
    //是否为出口节点,若是,则不需继续递归
    if(n==1)
        c=10;
    else // 入口节点与后续节点的关系
        c=age(n-1)+2;
    return c;
}

2 阶乘

5的阶乘是4的阶乘*5,4的阶乘是3的阶乘*4,3的阶乘是2的阶乘*3,2的阶乘是1的阶乘*2,1的阶乘是1的时候。

 
int fac(int n)
{ 
    int c;
    if(n==1) c=1;
    else c=fac(n-1)*n;  // 将前n-1个看做一个处理单元
    return c;
}

3 斐波那契数列

第一个和第二个数分别为1和1,从第三个数开始,每个数等于其前两个数之和(1,1,2,3,5,8,13…………)

 
int rabbitNum(int n)
{
    if (n==1||n==2) // 不需递归 找到出口
    {
        return n;
    }else{
                  
        return rabbitNum(n-1)+rabbitNum(n-2);
    }
}

4 汉诺塔

 
void  Hannoi(int n,TCHAR a,TCHAR b,TCHAR c)
{
 
    // 已经确定答案了,不需递归的情况
    if (n==1)
    {
        Move(1,a,c);
    }else{ //需要继续递归的情况, 在这种情况下,关键是看:如何将问题划分为子问题处理单元,然后处理各个单元间的关系
        // 本例:  将n个盘子 分成两个单元: 前n-1个盘子为一单元 、最后一个盘子为一单元
        
        Hannoi(n-1,a,c,b);// 将第一个单元 从 a 移动到 b
        Move(n,a,c);      // 将第二个单元 从 a 移动到 c
        Hannoi(n-1,b,a,c);// 将第一个单元 从 b 移动到 c
    }
}

5 将输入的字符以相反顺序打印出来

 
#include <stdio.h> 
#include <string.h> 
void strv(TCHAR* p){ 
    if(!*p)  // 不需继续递归  递归出口
        return; 
    // 当p+1(包括p+1)之后的作为一个处理单元 
    strv(p + 1); 
    // 处理完毕 第一个单元后,输出本单元*p
    putchar(*p); 
}; 
int main(){ 
    TCHAR* p = _T("ABCDEFGHIJK"); 
    strv(p); 
    return 0; 
};