【数据结构】第3章栈和队列递归算法

淡淡的烟草味﹌ 2022-11-27 12:08 89阅读 0赞

【阶乘、斐波那契数列、链表递归、汉诺塔】

--------------------

> 对于复杂问题， 若能够分解成几个相对简单且解法相同或类似的子问题来求解， 便称作递归求解。  
> 例如， 计算 4！时先计算 3！然后再进一步分解进行求解，这种分解－求解的策略叫做 “分治法”。

“分治法” 求解递归问题算法的一般形式为：

void p(参数表)
    {
        
        if(递归结束条件成立)          //递归终止条件
            可直接求解;
        else p(较小的参数);          //递归步骤
    }

当递归结束条件成立，只执行return操作时，“分治法” 求解递归问题算 法的一般形式可以简化为：

void p(参数表)
    {
        
        if(递归结束条件不成立)       //递归终止条件
            p(较小的参数);          //递归步骤
    }

## 1、定义是递归的 ##

#### 1、阶乘 ####

//1、阶乘
    long Fact(long n)
    {
        
        if(n == 0)
            return 1;                       //递归终止条件
        else
            return n * Fact(n - 1);         //递归步骤
    }

#### 2、斐波那契数列 ####

//2、斐波那契数列
    long Fib(long n)
    {
        
        if(n == 1 || n == 2)
            return n;                       //递归终止条件
        else
            return Fib(n - 1) + Fib(n - 2); //递归步骤
    }

## 2、数据结构是递归的 ##

#### 1、链表递归遍历 ####

//1、链表递归遍历
    void TraverseList(LinkList p)
    {
        
        if(p == NULL)
            return;                 //递归中止
        else
        {
        
            cout<<p->data<<ends;     //输出当前数据域
            TraverseList(p->next);  //p指向后继结点继续递归
        }
    }

可化简为：

//1、链表递归遍历_简化
    void TraverseList(LinkList p)
    {
        
        if(p)                       //递归不中止
        {
        
            cout<<p->data<<ends;     //输出当前数据域
            TraverseList(p->next);  //p指向后继结点继续递归
        }
    }

（关于 endl ends flush [戳这篇！！！][Link 1]）

## 3、问题的解法是递归的 ##

#### 1、汉诺塔 ####

//1、汉诺塔
    #include<bits/stdc++.h>
    using namespace std;
    int m;
    void move(char A, int n, char C)
    {
        
        //m是搬动次数，n是圆盘序号，从A搬到C
        cout<<++m<<","<<n<<","<<A<<","<<C<<endl;
    }
    void Hanoi(int n, char A, char B, char C)
    {
        //将A上的n个圆盘按规则搬到C上，B做辅助
        if(n == 1)
            move(A, 1, C);
        else
        {
        
            Hanoi(n - 1, A, C, B);      //把前n-1个从A搬到B上，移动多个圆盘，需要递归
            move(A, n, C);              //把第n个从A搬到C上，只移动1个圆盘，不需要递归，此函数只记录搬运过程
            Hanoi(n - 1, B, A, C);      //把前n-1个从B搬到C上，移动多个圆盘，需要递归
        }
    }
    
    int main()
    {
        
        int n;
        char a = 'A', b = 'B', c = 'C'; //分别代表3根柱子
        while(cin>>n)                   //输入圆盘个数
        {
        
            m = 0;                      //搬动次数（最终m = 2^n - 1）
            Hanoi(n, a, b, c);          //将A柱上的所有圆盘移动到C柱上
        }
        return 0;
    }

![在这里插入图片描述][20200815123655363.png_pic_center]

#### 2、八皇后 ####

#### 3、迷宫 ####

[Link 1]: https://blog.csdn.net/qq_45878292/article/details/108020271
[20200815123655363.png_pic_center]: /images/20221124/ba65efb665104f1aacc5e15a678e3dca.png