C++递归算法经典实例详解 |21xrx.com

C++递归算法经典实例详解

2023-07-03 14:29:13 深夜i -- --

C++ 递归算法经典实例详解

递归是一种常用的算法思想，是指在程序执行过程中，调用自身的函数。C++语言中也可以使用递归算法来解决一些问题。本文将详解C++递归算法的经典实例。

1. 阶乘问题

求 n 的阶乘可以使用递归算法进行解决。阶乘（factorial）的定义为：0!=1，n!=n×(n-1)！（n>0）。可以使用以下程序实现阶乘的递归算法：


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

该程序使用了if-else逻辑语句来进行判断，当参数n等于0时函数返回1，否则函数返回n乘以n-1的阶乘。该递归算法的时间复杂度是O(n)，空间复杂度是O(n)，因为每调用一次函数都需要占用一个新的栈帧。

2. 斐波那契数列问题

斐波那契数列（Fibonacci sequence）是指从1,1开始，后面每一项是前面两项之和的数列。可以使用以下递归算法实现斐波那契数列的求解：


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);
}

当n等于1或2时，函数返回1，否则函数返回n-1和n-2的斐波那契数列值之和。该递归算法的时间复杂度是O(2^n)，空间复杂度是O(n)，因为每调用一次函数都需要维护一个新的栈帧。

3. 汉诺塔问题

汉诺塔问题（Tower of Hanoi）是一道经典的递归问题。该问题有三个柱子和n个大小不等的圆盘，初始状态下所有的圆盘都放在第一个柱子上，现在需要将所有的圆盘移动到第三个柱子上，且在移动的过程中保证大的圆盘在小的圆盘上面。可以使用以下递归算法实现汉诺塔问题的求解：


void hanoi(int n,char a,char b,char c)
{
  if(n==1)
  
    cout<<a<<"->"<<c<<endl;
    return;
  
  else
  {
    hanoi(n-1,a,c,b);
    cout<<a<<"->"<<c<<endl;
    hanoi(n-1,b,a,c);
  }
}

当有n个圆盘需要移动时，首先需要将n-1个圆盘从第一根柱子移动到第二根柱子，然后将第n个圆盘从第一根柱子移动到第三根柱子，最后将n-1个圆盘从第二根柱子移动到第三根柱子。该递归算法的时间复杂度是O(2^n)，空间复杂度是O(n)，因为每调用一次函数都需要维护一个新的栈帧。

总结

递归算法是一种常见并且强大的算法思想，可以解决许多计算机科学问题。但是，在使用递归算法时需要注意，因为递归算法的时间复杂度和空间复杂度都很高，容易导致程序出现栈溢出等问题。因此，在实际编程中需要掌握递归算法的特点和优缺点，选择合适的算法进行求解。

上一篇: idea打包java可执行jar包

下一篇: 推荐什么软件学习c++入门？

评论区

()

相似文章