栈是如何实现递归的

递归与栈一些不得不说的事
服务器君一共花费了665.317 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

在高级语言中,调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称做递归函数。

  • 当然,写递归程序最怕的就是陷入永不结束的无穷递归中,所以,毎个递归定义必须至少有一个条件,满足时递归不再进行,即不再引用自身而是返回值退出。比如刚才的例子,总有一次递归会使得i < 2的,这样就可以执行return i的语句而不用继续递归了。

对比了两种实现斐波那契的代码。迭代和递归的区别是:迭代使用的是循环结构,递归使用的是选择结构。

  • 递归能使程序的结构更清晰、更简洁、更容易让人理解,从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本,会耗费大量的时间和内存。
  • 迭代则不需要反复调用函数和占用额外的内存。因此我们应该视不同 情况选择不同的代码实现方式。

那么我们讲了这么多递归的内容,和栈有什么关系呢?这得从计算机系统的内部说起。

  • 前面我们已经看到递归是如何执行它的前行和退回阶段的。递归过程退回的顺序是它前行顺序的逆序。在退回过程中,可能要执行某些动作,包括恢复在前行过程中存储起来的某些数据。

这种存储某些数据,并在后面又以存储的逆序恢复这些数据,以提供之后使用的需求,显然很符合这样的数据结构,因此,编译器使用栈实现递归就没什么好惊讶的了。

简单的说,就是在前行阶段,对于每一层递归,函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段,位于栈顶的局部变量、参数值和返回地址被弹出,用于返回调用层次中执行代码的其余部分,也就是恢复了调用的状态。

  • 递归调用其实就是栈,栈有先进后出的特点,递归调用的实质也就是循环调用,我写一个简单的例子吧:
#include "stdio.h"

int main()
{
    int n;
    int f(int m);
    printf("请输入一个大于1的数:");
    scanf("%d",&n);
    printf("%d\n",f(n));
    return 0;
}

int f(int m)
{
    if(m==1)
        return 1;
    else
    {
        printf("m=%d\n",m);
        //每当m!=1的时候就不断地调用int f(int m),直到m==1为止
        return f(m-1);
    }
}

程序执行结果:

请输入一个大于1的数:5
m=5
m=4
m=3
m=2
1
  • 这个程序是这样执行的,首先你先随便输入一个整数n,对于每个整数把n的值传给m,这样就实现了函数的第一次调用。然后调用了f(n),紧接着执行int f(int m),当m不等于1的时候就执行了else语句,return f(m-1),这样f(m-1)又一次调用了int f(int m),直到m=1为止。最终返回了f(n)的值,递归调用也到此为止。

下面附上动画演示:

当然,对于现在的髙级语言,这样的递归问题是不需要用户来管理这个栈的,一切都由系统代劳了。

延伸阅读

此文章所在专题列表如下:

  1. 栈的定义与大概理解
  2. 栈的抽象数据类型ADT
  3. 顺序栈:栈的顺序存储结构
  4. 顺序栈的进栈操作
  5. 顺序栈的出栈操作
  6. 获取顺序栈的栈顶元素
  7. 链栈:栈的链式存储结构
  8. 链栈的进栈操作
  9. 链栈的初始化与遍历
  10. 链栈的出栈操作
  11. 链栈的置空操作与判断链栈是否为空
  12. 为什么要使用栈这种数据结构
  13. 递归,栈的重要应用之一
  14. 栈是如何实现递归的
  15. 接触后缀表达式(逆波兰表示法)
  16. 图解后缀表达式的计算过程
  17. 将中缀表达式转化为后缀表达式
  18. 开始学习队列这个数据结构
  19. 队列的抽象数据类型ADT
  20. 顺序队列:队列的顺序存储结构
  21. 顺序队列的入队操作
  22. 顺序队列的出队操作
  23. 顺序队列置空与判断操作
  24. 队列顺序存储结构的不足
  25. 关于循环队列的一些讲解
  26. 链队列:队列的链式存储结构
  27. 链队列的初始化操作
  28. 链队列的入队操作
  29. 链队列的出队操作
  30. 补完链队列的其它常见操作
  31. 循环队列与链队列的优劣势

本文地址:http://www.nowamagic.net/librarys/veda/detail/2300,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2300

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《编译原理(第2版)》 Alfred V. Aho (作者), Monica S.Lam (作者), 赵建华 (译者), 郑滔 (译者), 戴新宇 (译者)

《编译原理(第2版)》全面、深入地探讨了编译器设计方面的重要主题,包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术,并在相关章节中给出大量的实例。与上一版相比,《编译原理(第2版)》进行了全面的修订,涵盖了编译器开发方面的最新进展。每章中都提供了大量的系统及参考文献。《编译原理(第2版)》是编译原理课程方面的经典教材,内容丰富,适合作为高等院校计算机及相关专业本科生及研究生的编译原理课程的教材,也是广大技术人员的极佳参考读物。

更多计算机宝库...