-
2021-06-07 13:55:30
文章目录
什么是栈内存
在学习递归实现原理之前,我们先了解一下栈内存。
栈内存是计算机中的一种数据存储方式,是 Java 进程启动时候在内存中开辟的存储空间。- 栈内存的利用方式遵循 LIFO(后迚先出)原则
- Java 所有局部变量都在栈中分配(压入),方法的参数也是局部变量,局部变量在离开作用域时候回收,就是从栈中弹出(删除)。
- Java 中所有的局部变量都是在栈内存中分配的(包括方法中声明的变量、方法的参数)。
Java 方法调用使用栈实现, 递归调用就是栈实现的。递归时候要按照递归深度分配全部临时变量, 栈开销很大, 性能不好, 要注意不要超过栈的大小, 并且一定要给出结束条件, 否则会造成栈溢出错误。
演示方法递归调用过程
接下来我们通过递归计算 5+3+1 演示递归调用过程,代码如下所示:
public class RevDemo { public static void
更多相关内容 -
C语言函数的递归和调用实例分析
2021-01-20 06:16:42说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用。 2、可以应用这个转化过程使问题得到解决。 说明:使用其他的办法比较麻烦或很难解决 -
函数的递归调用
2021-08-16 22:44:58在调用一个函数的过程中又出现直接或间接的调用该函数本身,称为函数的递归调用。 直接:在调用函数f的过程中又要调用f函数。 (简单来说在一个函数定义里面又使用了该函数,而一般用到递归调用都包含一种类似...在调用一个函数的过程中又出现直接或间接的调用该函数本身,称为函数的递归调用。
直接:在调用函数f的过程中又要调用f函数。
间接:如果在调用f1函数的过程中要调用f2函数,而调用f2函数的过程中又要调用f1函数。
(简单来说在一个函数定义里面又使用了该函数,而一般用到递归调用都包含一种类似递增递乘的有规律的变化。)
就上来看,这两种递归调用都是无终止的自身调用,显然程序中不应出现这种无终止的递归调用,这就需要用if语句来控制,只有在某一条件成立时才继续执行递归调用,否则就不再继续。
下面我们用一个典型的函数递归调用的例子来说明:
用递归的方法求n!。
解题思路:
求n!可以用递归方法,即5!==4!*5,而4!==3!*4..........
可以用下面的递归公式表示
#include <stdio.h> //求n的阶乘 int fac(int n) { if (n == 0 || n == 1) { return 1; } else {int a; a=f(n - 1) * n; return a; // 递归调用 } } int main() { int a; printf("Input a number: "); scanf("%d", &a); printf("fac(%d) = %d\n", a, fac(a)); return 0; }
分析:
调用 fac() 后即进入函数体,只有当 n==0 或 n==1 时函数才会执行结束,否则就一直调用它自身。
由于每次调用的实参为 n-1,即把 n-1 的值赋给形参 n,所以每次递归实参的值都减 1,直到最后 n-1 的值为 1 时再作递归调用,形参 n 的值也为1,递归就终止了,会逐层退出。
要想理解递归函数,重点是理解它是如何逐层进入,又是如何逐层退出的,下面我们以 5! 为例进行讲解。
递归的进入
1) 求 5!,即调用 fac(5)。当进入 factorial() 函数体后,由于形参 n 的值为 5,不等于 0 或 1,所以执行
fac(n-1) * n
,也即执行fac(4) * 5
。为了求得这个表达式的结果,必须先调用 fac(4),并暂停其他操作。换句话说,在得到 factorial(4) 的结果之前,不能进行其他操作。这就是第一次递归。
2) 调用 fac(4) 时,实参为 4,形参 n 也为 4,不等于 0 或 1,会继续执行fac(n-1) * n
,也即执行fac(3) * 4
。为了求得这个表达式的结果,又必须先调用 fac(3)。这就是第二次递归。
3) 以此类推,进行四次递归调用后,实参的值为 1,会调用 fac(1)。此时能够直接得到常量 1 的值,并把结果 return,就不需要再次调用 fac() 函数了,递归就结束了。注意:递归结束时fac(1)满足if语句上半句,a被赋值为1,并且通过return语句将a=1返还给fac函数
即fac(1)=返还值(函数值)
递归的退出
当递归进入到最内层的时候,递归就结束了,就开始逐层退出了,也就是逐层执行 return 语句。
1) n 的值为 1 时达到最内层,此时 return 出去的结果为 1,也即 factorial(1) 的调用结果为 1。
2) 有了 fac(1) 的结果,就可以返回上一层计算fac(1) * 2
的值了。此时得到的值为 2,return 出去的结果也为 2,也即 fac(2) 的调用结果为 2。
3) 以此类推,当得到 fac(4) 的调用结果后,就可以返回最顶层。经计算,fac(4) 的结果为 24,那么表达式fac(4) * 5
的结果为 120,此时 return 得到的结果也为 120,也即 fac(5) 的调用结果为 120,这样就得到了 5! 的值。希望对于初学的你一些启示!
-
递归调用的理解&引申函数调用过程中栈指针的变化
2021-01-02 22:14:18以前将递归理解成调用自己,怎么都理解不了。 后来理解了,其实就把递归调用理解成普通调用好了,只不过调用的是和自己原来一样的函数,但是记得他是从头重新调用了一遍 在栈空间里有独立的位置。 一直到最后一层...以前将递归理解成调用自己,怎么都理解不了。
后来理解了,其实就把递归调用理解成普通调用好了,只不过调用的是和自己原来一样的函数,但是记得他是从头重新调用了一遍
在栈空间里有独立的位置。
一直到最后一层调用的时候才开始返回。
所以严格意义上,他不是调用自己,而是调用一个复制了一份的另外一个函数。但他是两个函数,只不过共用了一个函数体。
所以最外面一层该进行的所有运算还是得进行,省不了。
那么它和普通函数调用的区别就在这里,既要满足能够跳转,跳转出去的每个函数能够用,又要满足自己能够执行下去。
引申了解一下普通程序调用过程中的栈指针的变化过程:
https://www.cnblogs.com/zlcxbb/p/5759776.html
我们先来了解一个概念,栈帧(stack frame),机器用栈来传递过程参数,存储返回信息,保存寄存器用于以后恢复,以及本地存储。为单个过程(函数调用)分配的那部分栈称为栈帧。栈帧其实 是两个指针寄存器,寄存器%ebp为帧指针(指向该栈帧的最底部),而寄存器%esp为栈指针(指向该栈帧的最顶部),当程序运行时,栈指针可以移动(大多数的信息的访问都是通过帧指针的,换句话说,就是如果该栈存在,%ebp帧指针是不移动的,访问栈里面的元素可以用-4(%ebp)或者8(%ebp)访问%ebp指针下面或者上面的元素)。总之简单 一句话,栈帧的主要作用是用来控制和保存一个过程的所有信息的。栈帧结构如下所示:
此处注意:这里面有一个错误,即:“保存的寄存器、局部变量和临时值”处应该是ebp-4。
栈是从高地址向低地址存储。所以越是低的地址,越是靠后入栈。
如果你已经对这个图已经非常了解了,那么就没有必要再看下去了。因为下面的内容都是对这幅图的讲解。
假设过程P(调用者)调用过程Q(被调用者),则Q的参数放在P的栈帧中。另外,当P调用Q时,P中的返回地址被压入栈中,形成P的栈帧的末尾 (返回地址就是当程序从Q返回时应该继续执行的地方)。Q的栈帧从保存的帧指针的值开始,后面到新的栈指针之间就是该过程的部分了。
理论解说:
https://www.cnblogs.com/zhq--blog/p/7354056.html
一、栈
在说函数递归的时候,顺便说一下栈的概念。
栈是一个后进先出的压入(push)和弹出(pop)式数据结构。在程序运行时,系统每次向栈中压入一个对象,然后栈指针向下移动一个位置。当系统从栈中弹出一个对象时,最近进栈的对象将被弹出。然后栈指针向上移动一个位置。程序员经常利用栈这种数据结构来处理那些最适合用后进先出逻辑来描述的编程问题。这里讨论的程序中的栈在每个程序中都是存在的,它不需要程序员编写代码去维护,而是由运行是系统自动处理。所谓的系统自动维护,实际上就是编译器所产生的程序代码。尽管在源代码中看不到它们,但程序员应该对此有所了解。
再来看看程序中的栈是如何工作的。当一个函数(调用者)调用另一个函数(被调用者)时,运行时系统将把调用者的所有实参和返回地址压入到栈中,栈指针将移到合适的位置来容纳这些数据。最后进栈的是调用者的返回地址。当被调用者开始执行时,系统把被调用者的自变量压入到栈中,并把栈指针再向下移,以保证有足够的空间存储被调用者声明的所有自变量。当调用者把实参压入栈后,被调用者就在栈中以自变量的形式建立了形参。被调用者内部的其他自变量也是存放在栈中的。由于这些进栈操作,栈指针已经移动所有这些局部变量之下。但是被调用者记录了它刚开始执行时的初始栈指针,以他为参考,用正或负的偏移值来访问栈中的变量。当被调用者准备返回时,系统弹出栈中所有的自变量,这时栈指针移动了被调用者刚开始执行时的位置。接着被调用者返回,系统从栈中弹出返回地址,调用者就可以继续执行了。当调用者继续执行时,系统还将从栈中弹出调用者的实参,于是栈指针回到了调用发生前的位置。
可能刚开始学的人看不太懂上面的讲解,栈涉及到指针问题,具体可以看看一些数据结构的书。要想学好编程语言,数据结构是一定要学的。
二、递归
递归,是函数实现的一个很重要的环节,很多程序中都或多或少的使用了递归函数。递归的意思就是函数自己调用自己本身,或者在自己函数调用的下级函数中调用自己。
递归之所以能实现,是因为函数的每个执行过程都在栈中有自己的形参和局部变量的拷贝,这些拷贝和函数的其他执行过程毫不相干。这种机制是当代大多数程序设计语言实现子程序结构的基础,是使得递归成为可能。假定某个调用函数调用了一个被调用函数,再假定被调用函数又反过来调用了调用函数。这第二个调用就被称为调用函数的递归,因为它发生在调用函数的当前执行过程运行完毕之前。而且,因为这个原先的调用函数、现在的被调用函数在栈中较低的位置有它独立的一组参数和自变量,原先的参数和变量将不受影响,所以递归能正常工作。程序遍历执行这些函数的过程就被称为递归下降。
程序员需保证递归函数不会随意改变静态变量和全局变量的值,以避免在递归下降过程中的上层函数出错。程序员还必须确保有一个终止条件来结束递归下降过程,并且返回到顶层。递归的基本原理:
https://blog.csdn.net/ysuncn/article/details/17938961 每一次函数调用都会有一次返回.当程序流执行到某一级递归的结尾处时,它会转移到前一级递归继续执行.
2 递归函数中,位于递归调用前的语句和各级被调函数具有相同的顺序.如打印语句 #1 位于递归调用语句前,它按照递
归调用的顺序被执行了 4 次.3 每一级的函数调用都有自己的私有变量.
4 递归函数中,位于递归调用语句后的语句的执行顺序和各个被调用函数的顺序相反.
5 虽然每一级递归有自己的变量,但是函数代码并不会得到复制.
6 递归函数中必须包含可以终止递归调用的语句.
-
c语言允许函数的递归调用吗
2021-05-22 04:21:16c语言允许函数的递归调用吗允许。...2、每次递归调用之后越来越接近这个限制条件。二、经典的递归题目-求第n个斐波那契数#include #include int fibonacci(int n){if(n <= 2){return 1;}else{return fibonacc...c语言允许函数的递归调用吗
允许。C语言中的函数直接或间接调用自己的过程叫递归。
一、递归的两个必要条件
1、存在限制条件,当满足这个条件时,递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。
二、经典的递归题目-求第n个斐波那契数#include
#include
int fibonacci(int n)
{
if(n <= 2)
{
return 1;
}
else
{
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
int main()
{
int n;
printf("请输入你想输出第几项的斐波那契数:\n");
scanf("%d", &n);
printf("%d\n", fibonacci(n));
system("pause");
return 0;
}
更多C语言及相关编程教程,请关注PHP中文网!
-
函数递归调用
2021-05-26 16:33:42微信公众号搜索【程序媛小庄】,...函数递归就是函数的递归调用,是函数嵌套调用的一种特殊形式,具体就是指在调用一个函数的过程中直接或者间接的调用到本身,递归的本质就是循环做重复的事情。 在调用func的过程中. -
Java中的递归调用机制
2021-08-03 20:31:55首先递归算法我们可以总结为:是方法自己调用自己,每次调用时传入不同的变量。递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。 我们所使用的程序如下: public class RecursionTest { public static ... -
函数递归调用时变量的变化情况
2020-01-17 16:59:36题目大意:求从根节点到叶节点权值和等于给定数S的所有路径,输出权值。所有的路径按非递增输出。路径a小于路径b表示a输出的权值序列小于b(以第一个不同的值计算)。...3.使用DFS算法,每次递归... -
C语言函数的递归调用
2022-04-24 21:28:16文章目录一、什么是递归 一、什么是递归 程序调用自身的编程技巧称为递归( recursion) 。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用...每次递归调用之后越来越接近这 -
C语言丨函数的递归调用和递归函数
2021-12-21 16:29:49在日常生活中,字典就是一个递归问题的典型实例,字典中的任何一个词汇都是由“其他词汇”解释或定义的,但是“其他词汇”在被定义或解释时又会间接或直接地用到那些由它们定义的词。在数学中,数学归纳法也是递归的... -
C语言递归函数(递归调用)详解[带实例演示]
2021-12-23 22:04:26一个函数在它的函数体内调用它自身称为递归调用,这种函数称为递归函数。执行递归函数将反复调用其自身,每调用一次就进入新的一层,当最内层的函数执行完毕后,再一层一层地由里到外退出。 递归函数不是C语言的... -
递归详细过程
2021-06-01 21:55:18前言:讲述递归之前,我们先来了解一下函数嵌套,...2.举个不断递归过程化的例子: 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是什么呢?“从前有座山,山里有座庙,庙里有个老和尚,正在给 -
C++算法篇 递归调用(函数调用自身)
2020-08-02 18:52:45要理解运用递归要学习理解下面几个问题: ...在数学与计算机科学中,递归是指在函数的定义中调用函数自身的方法。实际上递归其包含了两个意思:递 和 归,这正是递归思想的精华所在。 大师 L. Peter... -
【函数递归调用】递归调用经典问题—汉诺塔问题
2020-07-20 10:58:571.函数的递归调用 函数可以直接或者间接的调用...因此递归过程都可以用以下两个阶段概括。 Step1:递推。所谓递推就是将原有的问题不断拆解为新的子问题,其子问题就是原有问题的弱化(或者说更少层)的问题,这样,逐 -
C语言递归调用_使用递归函数调用方式,将输入的五个字符,以相反的顺序打印
2018-07-20 15:42:29//使用递归函数调用方式,将输入的五个字符,以相反的顺序打印 int main() { int i = 5; void palin(int n); printf("请输入五个字符:"); palin(i); printf("\n"); return 0... -
数据结构19:递归调用的实现
2020-09-08 14:36:09每次调用时,压入的现场数据称为栈帧。当函数返回时,要从调用栈的栈顶取得返回地址,恢复现场,弹出栈帧,按地址返回。 二、python中的递归深度限制 在调试递归算法深度限制的时候,经常会碰到这样的错误:... -
递归过程的详解(普通递归以及二叉搜索树的遍历递归)
2018-07-31 16:01:19有去:是指把问题分解成无数的小问题,一层一层地解决,最终到达临界点之后,即解决完最后一个需要调用自身函数处理的问题之后,有回:将解决的结果原路返回到原点,原问题解决。 递归的基本思想,是把规模较大... -
C++函数二(函数的嵌套调用和递归调用)
2021-03-05 17:53:15虽然C++不能嵌套定义函数,但可以嵌套调用函数,也就是说,在调用一个函数的过程中,又调用另一个函数 所谓嵌套调用,是在调用一个函数并执行该函数的过程中,又调用另一个函数的情况。如在main()函数中调用了a函数,而... -
递归方法调用和参数传递
2019-09-18 08:15:20递归方法调用和参数传递 开发工具与关键技术:C# 作者:李宥良 撰写时间:2019年9月18日 一个方法可以自我调用。这就是所谓的 递归。下面的实例使用递归函数计算一个数的阶乘: using System; namespace ... -
递归和栈帧的调用原理
2018-07-26 09:31:22递归函数:一个函数在内部ji进行自身调用的函数。 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示为:n x fact(n-1),只有n=1时需要特殊处理。 fact(n)用递归的方式写: def fact(n): ... -
Java方法递归调用基本使用
2022-03-13 11:52:32递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂问题,同时可以让代码变得简洁 递归能解决什么问题 递归举例: recursion 打印问题 package chapter7; public class Recursion... -
什么是递归调用-自已调自己 什么是递归算法
2019-05-31 09:48:02/* * 递归:方法自已调用自己 * 递归的分类:2种 * 1.直接递归称为方法自身调用自己 * 2.间接递归可以使用A方法调用B方法,B方法调用C方法,C方法再调用A方法 ...在递归虽然有限定条件,但是递归次数不... -
简单的递归算法(函数的自身调用)附有例题
2021-07-14 02:18:48递归分为递和归两个过程,递的过程即为函数逐层调用的过程,归即为函数逐层退出的过程,所以说递归是一种自上而下的算法。 这样说还是很抽象,还是直接上代码讲解吧。 教学用简单代码讲解 这大概是最简单的递归函数... -
图解递归的调用栈流程_求整数的N次方(java)
2019-03-13 22:03:07读题 递归,就是运行时候自己调用自己,最近写到一个递归算法时,想...递归函数在实现的过程中,是一个调用栈的过程。栈是一种后进后出式的数据结构,数据在表的同一端压入(PUSH)或者弹出(POP)。函数在调用另一... -
使用递归调用实现N的阶乘
2020-08-07 09:16:12一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算... -
c语言中递归函数的运行过程?
2021-05-21 03:19:41匿名用户1级2010-12-11 回答递归(recursion)就是子程序(或函数)直接调用自己或通过一系列调用语句间接调用自己,是一种描述问题和解决问题的基本方法。递归通常用来解决结构自相似的问题。所谓结构自相似,是指构成... -
有关函数的递归调用经典例题
2019-04-13 18:34:13操作规则:每次只能移动一个盘子,并且在移动过程中三根杆上都始终保持大盘在下,小盘在上,操作过程中盘子可以置于A、B、C任一杆上。(摘自百度百科)。 分析: 对于n层盘子汉诺塔的移动,先将n-1层盘子... -
Vue组件自我调用,实现递归展示
2021-11-17 18:01:10更多文章可关注我的个人博客:https://seven777777.github.io/myblog/ 相信大家开发过程中都曾遇到过以下这种类型的数据: dataList:[ { name:'名称1', children:[ { name:'名称1-1' children:[ { name:.