【数据结构day09--递归及其应用】

文章目录

• • 递归
  • • 递归的定义
    • 递归的应用
    • • 递归求累加和
      • Fibonacci数列
      • Hanoi问题
    • 总结

递归 递归的定义

递归即在运行的过程中调用自己

构成递归需具备的条件：

• 子问题需与原问题为同样的事，且更为简单
• 不能无限制地调用本身，需有一个出口，化简为非递归状况处理

递归的应用

递归算法一般用于解决以下问题：

• 数据的定义是符合递归规律（如Fibonacci数列）
• 问题解法符合递归规律，即逐层求解（如Hanoi问题）

以下列举了部分经典递归问题：

递归求累加和

该问题较为简单，就不过多赘述，代码如下：

#include 

int add(int Number)
{
    if (Number <= 0)
    {
        return 0;
    }else{
        return add(Number - 1) + Number;
    }
}

void addTest()
{
    int sum,n;
    printf("--------求和测试--------\n");
    n = 5;
    sum = add(n);
    printf("从0加到%d的结果是%d\n",n,sum);
    n = 10;
    sum = add(n);
    printf("从0加到%d的结果是%d\n",n,sum);
    n = 1;
    sum = add(n);
    printf("从0加到%d的结果是%d\n",n,sum);
}

int main()
{
    addTest();
}

运行结果：

--------求和测试--------
从0加到5的结果是15
从0加到10的结果是55
从0加到1的结果是1

**注：**该算法不可运算小于0的累加和

Fibonacci数列

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

**思路：**由Fibonacci数列定义，F(0) = 0，F(1) = F(2) = 1，从第三项开始其值等于前两项之和，即当n >= 3时F(n) = F(n - 1) + F(n - 2)。代码如下：

#include 

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

void fibTest()
{
    printf("--------斐波那契数列测试--------\n");
    int n,F_n;
    n = 2;
    F_n = fib(n);
    printf("F(%d)项的值是%d\n",n,F_n);
    n = 3;
    F_n = fib(n);
    printf("F(%d)项的值是%d\n",n,F_n);
    n = 4;
    F_n = fib(n);
    printf("F(%d)项的值是%d\n",n,F_n);
}

int main()
{
    fibTest();
}

运行结果：

--------斐波那契数列测试--------
F(2)项的值是1
F(3)项的值是2
F(4)项的值是3

Hanoi问题

汉诺塔由三根柱子（分别用A、B、C表示）和n个大小互不相同的空心盘子组成。一开始n个盘子都摞在柱子A上，大的在下面，小的在上面，形成了一个塔状的锥形体。对汉诺塔的一次合法的 *** 作是指：从一根柱子的最上层拿一个盘子放到另一根柱子的最上层，同时要保证被移动的盘子一定放在比它更大的盘子上面（如果移动到空柱子上就不需要满足这个要求）。

思路：

• 将n个盘子分为两部分，即第n个盘子和剩下的n-1个。
• 将n-1个盘子看为一个整体，要将n个盘子从A柱移动到C柱需要三步，即将n-1个盘子从A经过C移动到B，再将第n个盘子从A柱移动到C柱，最后将n-1个盘子从B柱经过A柱移动到C柱。
• 递归结束条件，为当盘子个数为1时，即只需要将其从A柱移动到B柱。

如图所示：

当n <= 2时

当n > 2时

代码如下：

#include 

int Hanoi(int Number, char startColumn, char passColumn, char endColumn)
{
    if (Number == 1)
    {
        printf("从%c柱移动到%c柱子\n",startColumn,endColumn);
        return 0;
    }else{
        Hanoi(Number-1,startColumn,endColumn,passColumn);
        printf("从%c柱移动到%c柱子\n",startColumn,endColumn);
        Hanoi(Number-1,passColumn,startColumn,endColumn);
    }
    
}

void hanoiTest()
{
    printf("--------汉诺塔测试--------\n\n");
    printf("--------测试1--------\n");
    Hanoi(1,'A','B','C');
    printf("--------测试2--------\n");
    Hanoi(2,'A','B','C');
    printf("--------测试3--------\n");
    Hanoi(3,'A','B','C');
}

int main()
{
    hanoiTest();
}

运行结果：

--------汉诺塔测试--------

--------测试1--------
从A柱移动到C柱子
--------测试2--------
从A柱移动到B柱子
从A柱移动到C柱子
从B柱移动到C柱子
--------测试3--------
从A柱移动到C柱子
从A柱移动到B柱子
从C柱移动到B柱子
从A柱移动到C柱子
从B柱移动到A柱子
从B柱移动到C柱子
从A柱移动到C柱子

总结

• 递归在对于解决数据的定义是符合递归规律（如Fibonacci数列）、问题解法符合递归规律，即逐层求解（如Hanoi问题）等问题时极其适用。
• 但递归也有其缺点：
  • 相对普通循环等，运行效率较低
  • 在递归调用过程中，系统为每一层的返回点、局部变量等都开辟了栈来储存，因此递归次数过多容易造成栈溢出等问题。
• 因此，在常用的算法如普通循环等能解决问题的情况下，应该尽量避免使用递归。