程序笔记   发布时间:2022-07-21  发布网站:大佬教程  code.js-code.com
大佬教程收集整理的这篇文章主要介绍了递归函数底层原理浅析大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。

一、递归函数

  看如下递归函数:

1 int f(int n){
2     if(n == @H_607_20@1){
3         return @H_607_20@1;
4     }
5     return f(n - @H_607_20@1) + @H_607_20@1;
6 }

  客户端调用该递归函数时传入n = 5, 返回的函数值为5。那么它的调用堆栈(call stack)是怎么样的?又是如何计算结果等于5呢?

二、函数调用栈

  函数调用栈:

The function call stack (often referred to just as the call stack or the stack) is responsible for maintaining the local variables and parameters during function execution.

  通过vs2019的call stack窗口,@R_673_6380@上面递归函数的递归调用栈:

      

递归函数底层原理浅析

 

 

     

递归函数底层原理浅析

 

  结果确实是5,那么是怎么计算的呢?这个就需要了解栈帧了。我们在Visual studio上也可以看到:

      

递归函数底层原理浅析

三、栈帧

  概念:

  

递归函数底层原理浅析

 

  栈帧的框架包含内容:

  

递归函数底层原理浅析

 

  • 函数局部变量
  • 需要返回的被子程序修改的寄存器副本信息
  • 函数的形式参数
  • 返回启调函数调用被调函数的地址

   通过对上面栈帧的简单了解,我们可以绘制上面函数的递归调用栈信息:

  在传入的形式参数没有满足递归退出条件前,函数会被断地压入栈中;除去主函数的栈帧外,

  递归函数被压入了5个栈帧,每个栈帧保存的形参都是不同的,分别为:5, 4, 3, 2, 1(从下到上)。

        

递归函数底层原理浅析

   当满足递归函数返回的条件后,开始退栈操作,如下:

  

递归函数底层原理浅析

  

递归函数底层原理浅析

 

   

递归函数底层原理浅析

  

递归函数底层原理浅析

  

递归函数底层原理浅析

 

   其实上面绘图中的main栈帧少了一个局部变量sum,最后递归函数返回的值5赋值给sum,即sum=5。

  通过上面图形并茂的方式,大家是不是对递归调用有了深入的认识,递归将问题不断地分解成很小的问题,最终解决大的问题。

 四、递归函数使用问题

  递归函数可以有效减少代码逻辑,但是也会出现很多其他问题:

  1. 递归函数一定要有递归出口,否则栈内存耗尽而导致程序崩溃
  2. 递归函数尽可能小,局部变量尽可能少,递归层次可控范围。否则可能因为栈内存耗尽而崩溃
  3. 尽量将递归函数替换成循环体
  4. @H_618_180@

      我使用Visual studio默认的递归栈大小是1M,如果需要提供递归栈大小,可以参MSDN文档进行修改。我们一般在测试的时候将栈大小改小,方便发现递归函数的bug。

    https://cs.gmu.edu/~kauffman/cs222/stack-demo.html

    https://www.techopedia.com/definition/22304/stack-frame

    大佬总结

    以上是大佬教程为你收集整理的递归函数底层原理浅析全部内容,希望文章能够帮你解决递归函数底层原理浅析所遇到的程序开发问题。

    如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。

    本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
    如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。