递归是如何用栈来实现的？_递归 栈

前言

概念介绍

栈的基本概念和原理我们已在“文章链接”中做过具体说明，下面我们主要讲讲递归算法

1. 什么是递归？

• 百度百科上的解释如下：程序调用自身的编程技巧称为递归；
• 一般来说，递归需要有边界条件、递归前进段和递归返回段。
• 当边界条件满足时，递归返回；当递归条件不满足时，递归前进；
• 递归的目的通常是把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解

2. 递归的通俗解释

• 可能你看了递归的定义后还是不明白，那就举个例子说明下：孔夫子说“三十而立”，你看了可能就在想这个“立”是什么意思？那你就继续搜索“立”字的解释，你发现孔夫子又说过“立于礼”，“不知礼，无以立也”；那你又不知道“礼”是什么意思；那只好继续搜索“礼”字的含义，等你弄明白了什么是“礼”，那你就知道什么是“立”，自然而然你就知道什么是“三十而立”了
  

原理讲解

讲解递归的原理那我们首先要搞明白递归和栈的关系。我们以如下代码为例：

int Factorial(int n)
{
    if (0 == n)
    {
        return 1;
    }

    int value = n * Factorial(n-1);

    qDebug() << "n:" << n << " value:" << value;
    return value;
}

Factorial(5);
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归和栈的关系

递归过程分为两步“递”和“归”，对应着栈的两种操作“进栈”和“出栈”。

1. 当n=5时，满足递归条件，执行进栈操作，具体效果入下图
   
2. 当n=4时，满足递归条件，执行进栈操作，具体效果入下图
   
3. 当n=3时，满足递归条件，执行进栈操作，具体效果入下图
   
4. 当n=2时，满足递归条件，执行进栈操作，具体效果入下图
   
5. 当n=1时，满足递归条件，执行进栈操作，具体效果入下图
   
6. 当n=0时，不满足递归条件，开始执行第一次出栈操作，将Factorial(1)的结果1返回，具体效果入下图
   
7. 继续执行第二次出栈操作，将Factorial(2)的结果1*Factorial(1)=2返回，具体效果入下图
   
8. 继续执行第三次出栈操作，将Factorial(3)的结果3*Factorial(2)=6返回，具体效果入下图
   
9. 继续执行第四次出栈操作，将Factorial(4)的结果4*Factorial(3)=24返回，具体效果入下图
   
10. 继续执行第五次出栈操作，将Factorial(5)的结果5*Factorial(4)=120返回，具体效果入下图
    

---

至此Factorial(5)递归结束

递归的优缺点

• 优点
  • 代码简洁
  • 便于理解
• 缺点
  • 时间和空间消耗大
  • 可能存在栈溢出
  • 可能存在重复计算

递归的应用场景

• 问题的定义就是按照递归来定义的
  • 阶乘
  • Fibonacci函数
• 问题的解决方法是递归的
  • 汉诺塔问题
• 问题涉及的数据结构是递归的
  • 树的遍历
  • 树的深度

更多算法学习请关注我的公众号

说明

• 在公众号中回复“算法源码”即可获取十大经典算法源码
• 在公众号中回复“算法书籍”即可获取经典入门算法书籍
• 在公众号中回复“数据结构”即可获取数据结构相关源码