关于计算机专业

运行结果:」

Exception in thread "main" java.lang.StackOverflowError at recursion.RecursionTest.sum(RecursionTest.java:13)

怎么解决这个栈溢出问题?首先需要「优化一下你的递归」，真的需要递归调用这么多次嘛?如果真的需要，先稍微「调大JVM的栈空间内存」，如果还是不行，那就需要弃用递归，「优化为其他方案」咯~

重复计算，导致程序效率低下

我们再来看一道经典的青蛙跳阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

绝大多数读者朋友，很容易就想到以下递归代码去解决
 

归存在的问题

• 递归调用层级太多，导致栈溢出问题
• 递归重复计算，导致效率低下

栈溢出问题

• 每一次函数调用在内存栈中分配空间，而每个进程的栈容量是有限的。
• 当递归调用的层级太多时，就会超出栈的容量，从而导致调用栈溢出。
• 其实，我们在前面小节也讨论了，递归过程类似于出栈入栈，如果递归次数过多，栈的深度就需要越深，最后栈容量真的不够咯

「代码例子如下：」
 

• 计算sum(5)时，先sum(5)入栈，然后原问题sum(5)拆分为子问题sum(4)，再入栈，直到终止条件sum(n=1)=1，就开始出栈。
• sum(1)出栈后，sum(2)开始出栈，接着sum(3)。
• 最后呢,sum(1)就是后进先出，sum(5)是先进后出，因此递归过程可以理解为栈出入过程啦~

递归的经典应用场景

哪些问题我们可以考虑使用递归来解决呢?即递归的应用场景一般有哪些呢?

• 阶乘问题
• 二叉树深度
• 汉诺塔问题
• 斐波那契数列
• 快速排序、归并排序(分治算法体现递归)
• 遍历文件，解析xml文件

递归解题思路

解决递归问题一般就三步曲，分别是：

• 第一步，定义函数功能
• 第二步，寻找递归终止条件
• 第二步，递推函数的等价关系式

这个递归解题三板斧理解起来有点抽象，我们拿阶乘递归例子来喵喵吧~

1.定义函数功能

定义函数功能，就是说，你这个函数是干嘛的，做什么事情，换句话说，你要知道递归原问题是什么呀?比如你需要解决阶乘问题，定义的函数功能就是n的阶乘，如下：

（编辑：伊春站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!