递归算法栈溢出JAVA

① java递归的优点缺点

递归好处：代码更简洁清晰，可读性更好
递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。

递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。

个人觉得：非必要时不递归

② java排序算法中，快速排序慢好多，还容易爆栈，求指教

• 代码没问题

• 我今天也遇到一样的问题

• 猜测是因为快排递归创建了很多栈，当数据量过大时就栈溢出

• 我的解决方法是自己也写了一个快速排序非递归的方法

• 但是实际耗费的时间仍然不如其他算法
  

③ 递归累加时，出java.lang.StackOverflowError了，怎么办

这么递归下去肯定会栈溢出。
如果单纯的想要1-10000的累加至于这么麻烦么？

累加的效率问题：
目前有下面两种方法：
方法一：
long sum = 0;
for(int i = 0;i < value;i++)
{
sum += i;
}

方法二：
long sum = 0;
sum = (value + 1) * value / 2;

当value值等于10000，使用方法一，运行10次有4次会产生15毫秒左右耗时，使用方法二，运行10次无耗时产生。
当value值等于100000，使用方法一，运行10次有5次会产生15毫秒左右耗时，使用方法二，运行10次无耗时产生。
当value值等于1000000，使用方法一，运行10次有10次会产生31毫秒左右耗时，使用方法二，运行10次无耗时产生。
......
以此类推，方法一累加计数的效率和方法二相比，随着value值的级数递增，效率相应下降。

测试代码：
public class SimpleArithmetic
{
public static void main(String[] args)
{
SimpleArithmetic sa = new SimpleArithmetic();
long sum = 0;
long time = 0;
long curTime = System.currentTimeMillis();
System.out.println("curTime=" + curTime);

//sum = sa.getSumCycle(1000000);
sum = sa.getSumNotCycle(1000000);
System.out.println(sum);

long endTime = System.currentTimeMillis();
System.out.println("endTime=" + endTime);

time = endTime - curTime;
System.out.println(time);
}

private long getSumCycle(long value)
{
long sum = 0;

for(long i = 1;i <= value;i++)
{
sum += i;
}

return sum;
}

private long getSumNotCycle(long value)
{
long sum = 0;
sum = (value + 1) * value / 2;
return sum;
}
}

④ JAVA中能够实现方法的递归调用吗如何实现

能 递归函数即自调用函数，在函数体内直接或间接的调用自己，即函数的嵌套是函数本身。递归调用又分为直接调用和间接调用
直接调用funca(){ ...... funca();};间接调用；funca(){ ...... funcb();}funcb(){ ..... funca(); .....} 汉诺塔源码public class HanoiY { void Move(char chSour,char chDest){ System.out.println("Move the top plate of "+chSour+"-->"+chDest); } void Hanoi(int n,char chA,char chB,char chC) { if(n==1) Move(chA,chC); else { Hanoi(n-1,chA,chC,chB); this.Move(chA,chC); Hanoi(n-1,chB,chA,chC); } } public static void main(String[] args) { int n=Integer.parseInt(args[0]); HanoiY han=new HanoiY(); han.Hanoi(n,'A','B','C'); } }

⑤ java中递归算法是什么怎么算的

一、递归算法基本思路：

Java递归算法是基于Java语言实现的递归算法。递归算法是一种直接或者间接调用自身函数或者方法的算法。递归算法实质是把问题分解成规模缩小的同类问题的子问题，然后递归调用方法表示问题的解。递归往往能给我们带来非常简洁非常直观的代码形式，从而使我们的编码大大简化，然而递归的思维确实跟我们的常规思维相逆的，通常都是从上而下的思维问题，而递归趋势从下往上的进行思维。

二、递归算法解决问题的特点：

【1】递归就是方法里调用自身。

【2】在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

【3】递归算法代码显得很简洁，但递归算法解题的运行效率较低。所以不提倡用递归设计程序。

【4】在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。

【5】在做递归算法的时候，一定把握出口，也就是做递归算法必须要有一个明确的递归结束条件。这一点是非常重要的。其实这个出口就是一个条件，当满足了这个条件的时候我们就不再递归了。

三、代码示例：

publicclassFactorial{

//thisisarecursivefunction

intfact(intn){

if(n==1)return1;

returnfact(n-1)*n;

}}

publicclassTestFactorial{publicstaticvoidmain(String[]args){

//TODOAuto-generatedmethodstub

Factorialfactorial=newFactorial();

System.out.println("factorial(5)="+factorial.fact(5));

}
}

代码执行流程图如下：

此程序中n=5就是程序的出口。

⑥ java栈内存溢出怎么解决

第一对所有的代码包括页面中的java代码都进行一遍彻底的回顾检查，
1.对那些静态(static)的对象要特别留神，特别是类型为Map,List,Set的，静态的变量会一直驻存在内存中，生命周期比较长，不会被垃圾器回收。
2．对于代码，要审查是否生成了大量的冗余的对象，还有一些逻辑业务处理的类，
算法是否过于复杂，调整算法，对于代码认真审查，再仔细重构一遍代码，能提高代码质量，提高程序运行稳定性。
3.Java中的内存溢出大都是因为栈中的变量太多了。其实内存有的是。建议不用的尽量设成null以便回收，多用局部变量，少用成员变量。
1），变量所包含的对象体积较大，占用内存较多。
2），变量所包含的对象生命周期较长。
3），变量所包含的对象数据稳定。
4），该类的对象实例有对该变量所包含的对象的共享需求。
4．在我的程序中对静态变量的优化后，使程序占用内存量至少提升了5k-10k。所以也不容忽视。
第二还有就是String类相关的东西：
1．字符串累加的时候一定要用StringBuffer的append方法，不要使用+操作符连接两个字符串。差别很大。而且在循环或某些重复执行的动作中不要去创建String对象，因为String对象是要用StringBuffer对象来处理的，一个String对象应该是产生了 3个对象（大概是这样：））。
2．字符串length()方法来取得字符串长度的时候不要把length放到循环中，可以在循环外面对其取值。(包括vector的size方法)。特别是循环次数多的时候，尽量把length放到循环外面。
int size = xmlVector.size();
for (int i = 2; i < size; i++) {
。。。
}
3 写代码的时候处理内存溢出
try{
//do sth
....
}catch (outofmemoryerror e){//可以用一个共通函数来执行.
system.out.print (“no memory! ”);
system.gc();
//do sth again
....
}
4.对于频繁申请内存和释放内存的操作,还是自己控制一下比较好,但是System.gc()的方法不一定适用，最好使用finallize强制执行或者写自己的finallize方法。 Java 中并不保证每次调用该方法就一定能够启动垃圾收集，它只不过会向JVM发出这样一个申请，到底是否真正执行垃圾收集，一切都是个未知数。

⑦ Java如何在不使用递归的情况下导致栈溢出

归 调用,在不断的压 栈 过程中,造成 栈 容量超过1m而 导致 溢出 .2,解决方案:方... 算法正确的情况下,使用过程中会出现堆 栈溢出 的话,可以通过修改PLUS函数,

⑧ Java-java产生StackOverflowError的原因是什么

栈溢出。Java里面每个线程都有独立的、固定大小的栈空间， Java在解释执行的时候采用的是栈式的架构。 方法调用、方法内的局部变量都是在栈空间申请的。 空间的大小依赖于JDK版本，JDK1.6应该是512K，超过了这个空间就会产生StackOverFlow。
死循环本身是不会StackOverflow的，只有无限递归的时候会出现。原则上循环嵌套次数本身是没有限制的，限制的是占用的栈空间，如果你的方法里定义了很多很多变量，栈空间就会用完得比较快。如果你的软件不是很庞大，那么你的程序中出现了无限的递归的情况可能产生这个错误。

⑨ 同样是调用递归算法，快速排序文件过大时栈溢出，而归并排序则不会，怎么解决

不知道你在哪里看到的快速排序，虽然写得这么纠结，但是结果还是对的。快速排序跟归并排序的最大区别是归并排序需要额外的空间，这个空间你是在堆里分配的，而快速递归不需要申请一个O(n)空间是因为通过函数栈保存了一些中间数据，正常来说当你元素很多时比如大于1M，函数栈肯定会溢出的，因为函数栈一般默认大小就是1M，函数栈大小是可以设置的，怎么设置函数栈大小你可以查网络。这些或许你都知道，不过你的递归算法也有点问题，因为你中间元素key就取了第一个元素，这会使得出现很多的递归浪费大量的栈空间，比如元素本来就有序的以你的算法时间复杂度为T(n) = T(n-1) + n，这个时间复杂度是O（n*n），递归次数为n，正常情况递归次数应该是log（n）次的，你递归了时间不说栈空间就需要很大，所以这也可能是你栈溢出的一个可能。快速排序的中间元素key不能去第一个元素就行了，即使随机取一个都比你取第一个好多了。这里有我之前写的一个快速排序
struct my_traits<T*>
{
typedef T value_type;
}
template<class BidirectIterator>
void IterSwap(BidirectIterator i,BidirectIterator j)
{
if(*i == *j) return;
typename my_traits<BidirectIterator>::value_type temp = *i;
*i = *j;
*j = temp;
}
template<class T>
void InsertSort(T *first,T *last)
{
for(T *i = first + 1;i < last;++i)
{
T value = *i;
T *j = 0;
for(j = i;j - 1 >= first&&*(j - 1) > value;--j)
*j = *(j - 1);
*j = value;
}
}
template<class T>
T Median3(T*first,T*last)
{
T * middle = first + (last - first) / 2;
last--;
if(*first > *middle)
IterSwap(first,middle);
if(*first > *last)
return *first;
if(*middle < *last)
return *middle;
return *last;

}
template<class T>
T* Partition(T *first,T *last,T pivot)
{
while(true)
{
while(*first < pivot) ++first;
--last;
while(*last > pivot) --last;

if(first > last) return first;
IterSwap(first,last);
++first;
}
}

template<class T>
void QuikSort(T *first,T *last)
{
if(last - first >= 4)
{
T *cut = Partition(first,last,Median3(first,last));
QuikSort(first,cut);
QuikSort(cut,last);
}
else
{
InsertSort(first,last);
}
}