简析递归思想及其典型算法

布满荆棘的人生 2022-08-05 08:19 171阅读 0赞

递归：也就是在运行过程中自己调用自己

一个过程或[函数][Link 1]在其定义或说明中有直接或间接调用自身的一种方法。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算。它可以用有限的[语句][Link 2]来定义对象的[无限集合][Link 3]。一般来说，递归需要有边界条件、递归前进段和递归返回段。

当边界条件不满足时，递归前进-----递；当边界条件满足时，递归返回-----归。

考虑之前学过的数学方法，递归的思想就是归纳法，将问题转换为与原问题相似的子问题，而子问题又被转换为子问题的子问题，而且这些问题都有着相同的逻辑，即解决的思路是相同的。

构成递归的条件：

1.  子问题与原问题是同样的事，且更为简单
2.  不能无限次的调用自身，必须有递归结束的条件，也就是返回出口

[递归算法][Link 4]一般用于解决三类问题：  
(1)数据的定义是按递归定义的。（Fibonacci[函数][Link 1]）  
(2)问题解法按[递归算法][Link 4]实现。  
这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如Hanoi问题。  
(3)数据的结构形式是按递归定义的。  
如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。

递归算法的一般形式：     
    void   func( mode)\{     
          if(endCondition)\{     
                 constExpression       //基本项    
          \}     
          else

accumrateExpreesion /归纳项

mode=expression //步进表达式

func(mode) / /调用本身，递归

最典型的就是N！算法

void factorial(int N){
        if(N==0)
            return 1;
        else
            return N*factorial(N-1);
    }

\* 输入任意长度的字符串，逆序输出

思路分析：在此处，是无法用数组的，因为是任意长度的字符串；用动态链表是可以实现存储任意长度的字符串，但是逆序输出时间复杂度高。此处我们利用递归的思想就可以很容易地实现

代码如下：

void print()
    {
        char c;
        scanf("%c",&c);  //#表示输入结束
        if(c!='#')
        {
            print();
        }
        if(c!='#')
        {
            printf("%c",c);
        }
    }

然而，递归相对于迭代来说，效率低下， 在 [递归调用][Link 5] 的过程当中系统为每一层的返回点、局部量等开辟了栈来存储，增加了系统的开销。同时，递归次数过多容易造成 [栈溢出][Link 6] 等。如果可以用迭代实现的，就尽量不要用递归，但是在某些情况下，用递归的优越性就比较明显，就需要我们用递归去实现。

汉诺塔（Hanoi）问题：

思路：

1.  将n-1个圆盘从X借助Z移动到Y
2.  将1一个圆盘从X移动到Z
3.  将n-1个圆盘从Y借助X移动到Z

#include <stdio.h>
    
    //将 n 个圆盘从 x 借助 y 移动到 z
    void move(int n,char x,char y,char z)
    {
        if(n==1)
        {
            printf("%c--->%c\n",x,z);
        }else
        {
            move(n-1,x,z,y);
            printf("%c--->%c\n",x,z);
            move(n-1,y,x,z);
        }
    }
    int main()
    {
        int n;
        printf("请输入要移动的圆盘的个数:");
        scanf("%d",&n);
        move(n,'X','Y','Z');
        return 0;
    }

[Link 1]: http://baike.baidu.com/view/15061.htm
[Link 2]: http://baike.baidu.com/view/537751.htm
[Link 3]: http://baike.baidu.com/view/514048.htm
[Link 4]: http://baike.baidu.com/view/1733593.htm
[Link 5]: http://baike.baidu.com/view/1265506.htm
[Link 6]: http://baike.baidu.com/view/2061755.htm