优化-递归是用栈来实现的,栈里面具体都存放了什么数据?

问题描述

递归是用栈来实现的,栈里面具体都存放了什么数据?
同上,今天看到尾递归可以实现递归的优化,无论多深的递归栈都不会出现溢出(原文如此)。
我在想栈里不是会存放每次递归函数的地址吗?为什么无论多深栈都不会溢出?

解决方案

一个对自己本身的递归 尾调用,就叫做尾递归。这里尾调用的“尾”字,是指运行
时需要执行的最后一个动作。不是简单的语法字面上的最后一个语句。 尾递归实
际执行的是迭代的计算过程。
线性递归函数必须满足以下两个基本属性:
*必须清晰无误地解决基的情况。
*每一个递归的调用,必须包含更小的参数值。
而尾递归则不必满足这两个条件。
普通的线性递归比尾递归更加消耗资源 在实现上说 每次重复的过程调用都使得调
用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就不存在这样的问
题 因为它的状态完全由函数的参数保存. 并且,由于尾递归的函数调用出现在调用者
函数的尾部,因为是尾部,所以根本没有必要去保存任何局部变量的信息。
直接让被调用的函数返回时越过调用者,返回到调用者的调用者去。
尾调用优化不是什么很复杂的优化,实际上几乎所有的现代的高级语言编译器都支持
尾调用这个很基本的优化。 实现层面上,只需要把汇编代码call改成jmp 并放弃所有
局部变量压栈处理,就可以了。这样一来,堆栈根本就没有被占用,每次调用都是重
新使用调用者的堆栈。

解决方案二:
不是到,栈是会溢出的比如,vs默认栈大小是5M,超来就溢出了

解决方案三:
栈实现递归
阶乘的栈实现和递归实现

时间: 2024-11-17 08:13:49

优化-递归是用栈来实现的,栈里面具体都存放了什么数据?的相关文章

C/C++ 使用 memoization 优化递归 避免重复计算

C/C++ 使用 memoization 优化算法 以常见的斐波那契数列计算为例: #include <stdio.h>   #define COUNT_TIMES 10   int fib(int n) {     if (n == 0 || n == 1)     {         return 1;     }     else     {         return fib(n - 2) + fib(n - 1);     } }   int main() {     int i;

仅用递归函数和栈逆序一个栈

package stackAndQueue; import java.util.Stack; import org.junit.Test; /** * 仅用递归函数和栈逆序一个栈:ReverseStack[2] * * [一个栈依次压入1.2.3,将栈转置,使栈顶到栈底依次是1.2.3,只能用递归函数,不能借用额外的数据结构包括栈] * * 算法思想:两个递归函数(getAndRemoveBottom.reverse) * * @author xiaofan */ public class Re

包含min函数的栈和两个栈实现一个队列

题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素.要求函数min.push以及pop的时间复杂度都是O(1). 分析:这是google的一道面试题. 看到这道题目时,第一反应就是每次push一个新元素时,将栈里所有逆序元素排序.这样栈顶元素将是最小元素.但由于不能保证最后push进栈的元素最先出栈,这种思路设计的数据结构已经不是一个栈了.在栈里添加一个成员变量存放最小元素(或最小元素的位置).每次push一个新元素进栈的时候,如果该元素比当前的最小元素还要小,则更新最小元素.

c++ 链栈 出错-c++链栈问题,求大神,大一无力啊

问题描述 c++链栈问题,求大神,大一无力啊 程序运行的时候出错,自己弄了好久不知道怎么办,百度了也不行#include #include using namespace std; enum error_code{success,underflow,overflow}; //定义枚举 char opr[]={'+','-','*','/','(',')','#'}; struct node{ char data0; int data1; node *next; }; int comp[7][7]

栈界限-保护模式栈边界的问题

问题描述 保护模式栈边界的问题 X86汇编语言-从实模式到保护模式 有这样一道题:当前栈段描述符的B位是1,基地址为0X00700000,界限值为0XFFFE.那么,在32位模式下,该栈段的有效地址范围是0X00700000~( ).当ESP的内容为0XFFFFF002时,还能压入一个双字吗?为什么?当前栈段是向下扩展的.我的答案是0X00700000+0XFFFFE*0X1000+0XFFF=0X1006FEFFF去掉溢出位=0X006FEFFF不过看到第二问时候我就知道我错了.可是书上又说,

《深入解析sas:数据处理、分析优化与商业应用》一一2.3 通过IMPORT过程读取外部文件数据

2.3 通过IMPORT过程读取外部文件数据 除了可以通过DATA步读取外部文本文件数据外,SAS还提供了IMPORT过程,通过它可以从外部数据源读取数据并写入SAS数据集中.而且,如果使用SAS/ACCESS to PC Files,IMPORT过程除了可以导入带分隔符的文件外,还可以读取PC文件中的外部数据,包括Microsoft Access数据库文件.Miscrosft Excel工作簿.Lotus 1-2-3文件.dBase文件.JMP文件.SPSS文件.Stata文件.Paradox

一个新手站长的建站心得 不断摸索学习最重要

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 经过一阵子摸索,现在终于摸出了一些门道,其实以前在公司工作的时候很少听说过程序员玩网站,做站长,成天就"陶醉"在自己的程序里,天天面对一堆堆代码,根本就不晓得网站的真正意义,当然也有不少人都有自己的网站,但是有几个程序员懂得去优化seo网站呢,公司里做的网站很多都是动态读取数据的,会不会影响收录,这些根本不再考虑的范围,因

《数据结构与算法 C语言版》—— 3.3栈与递归实现

3.3栈与递归实现 3.3.1递归的定义 栈还有一个重要应用是在程序设计语言中实现递归.一个直接调用自己或通过一系列的调用语句间接调用自己的函数,称为递归函数.其中直接调用自己的函数称为直接递归.间接调用自己的函数称为间接递归. 递归是算法设计中最重要的手段.它通常把一个大型的复杂问题转化为一个与原问题相似的规模较小的问题来求解.下面是常见的使用递归的三种情况. (1)定义是递归的 现实中,有许多定义是递归定义的,以n!为例来说明,其定义如下: fact(n)=1n=0//递归终止条件 n*fa

数据结构C++栈的应用-递归

问题描述 数据结构C++栈的应用-递归 求n个正整数阶乘的递归算法(得体现出栈在函数调用中的作用),求源程序 解决方案 堆栈做法 #include <stack> #include <iostream> using namespace std; int f(int n) { stack<int> s; int r = 1; for (int i = 2; i <= n; i++) s.push(i); while (!s.empty()) { r *= s.top