为什么BigInteger最终在Java中的StackOverflowError处于第19635位Fibonacci Sequence中的整数

Question

我使用以下代码计算斐波那契序列到任意大数字.代码按预期工作,直到我要求它调用函数4,000,000次(之前我只做了几百次)并且计算机运行了一段时间,然后Eclipse中的控制台生成了我粘贴在代码下面的异常.

我的问题是这里发生了什么？我的电脑是否完全没有内存或分配给该线程的内存？如果是这样,为什么它特意停在这个数字？

附加:如何计算Fibonacci序列的更多数字？

import java.math.BigInteger;

public class fibonacci2 {

public static void main(String[] args) {

    calculate(p,q);

}
static long i = 0;
static BigInteger p = BigInteger.valueOf(0);
static BigInteger q = BigInteger.valueOf(1);
static BigInteger temp = BigInteger.valueOf(1);

public static void calculate(BigInteger s,BigInteger t){
    while(i<4000000){       
        System.out.printf("%d\t%d\n", p, i);
        temp = p;
        p = p.add(q);
        q = temp;
        i++;
        calculate(p,q);
        }
    }

}

例外:

Exception in thread "main" java.lang.StackOverflowError
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4502)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4500)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4500)
    at java.util.regex.Pattern$BranchConn.match(Pattern.java:4466)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:4177)
    at java.util.regex.Pattern$Curly.match(Pattern.java:4132)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4502)
    at java.util.regex.Pattern$Branch.match(Pattern.java:4500)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715)
    at java.util.regex.Pattern$Start.match(Pattern.java:3408)
    at java.util.regex.Matcher.search(Matcher.java:1199)
    at java.util.regex.Matcher.find(Matcher.java:618)
    at java.util.Formatter.parse(Formatter.java:2517)
    at java.util.Formatter.format(Formatter.java:2469)
    at java.io.PrintStream.format(PrintStream.java:970)
    at java.io.PrintStream.printf(PrintStream.java:871)
    at fibonacci2.calculate(fibonacci2.java:19)
    at fibonacci2.calculate(fibonacci2.java:24)

最后生成的数字:19635 - 相当多.

132687895548902466181366635978648936386259759626784159198471844113368720762558998439244647213670836266002193258488843538717586491362100768690744948872614655533963444005758146274483789445525832018171591705801097245938131666262491251573046333399064124825294626375827326373349437140811166679924860265434837435457566510346823522099708782762283340421872152967954697149679070291775852559319530410970741909107854532260299713987604089848331720784324541846051983900879941503950602855721502515831654718683894999456728434816859475155877430343774997661435320771926617215280039933599972465309345254567178339436280952174619541825862884767075607549690650640847821947665184588889102910848010077578318155209477877401207558117424629193877673216227666300792666026188581069615968439885076613046674989223796136897853735065950338488718459072802993894034602966485409833232527607580300466868397366391196516624465562328897666935339268449377325653828646145985110998531659421856703633111062016650375200285896034594800936872091294839900191091698699722026536243666478579994343910947620181792632830778710190311139396156735880074125397511408966605505552422864103569572257613749591889214289715689869250327711408697220359084539413697662799047739270265811002163302937592845234417596161934244642557769201791982828989296516960843921418505825929942814213639292708769436360663239620071203876284640114617617407623573142799950934154067036543593696242108211895742765733512094057256880955310857577903859564579056746531798738498941813073521535219704445493818404188856023980301868618516469829419121757591230096104147125384637901683811153945850319934065084792517083004130890910462024025472721271948569599123360701230540009715282093017067167999678658635663087411610488550002425545947760514500156025301308306327998659164369104269073668157017876181974674317395355412084217340614118259465040019942533175911244270084308389583553447943104546514782390571844604018802721936904404474688189087095735594169734604764561595142228281276547574197914091694854554413589159098499442131625356509906287285672050080215052926747681492642423016441535060701812422382650607369780485598683879561606185899006941448935168420562235626599835745827700295226714246314734017810402964725369860652473776199131459371207950362024398152881453713163784066208042563543662925682842776015262230520391615679652089970517416773429690840845145299626705629719042357249513002595223367277901469344821405379464226668034873875307681491568655204909774495913318375555411759980733171712799322946052444470529341466911138600782570876081467456539333314140771233788511026610245435362670217650351862005123494882440312897401664665221934387408681977959790208001158782272459157216112763316198348542078709999150647564964914134863576486661123746003816160948281150545905672098416477331230622651937768742259299137290941586718911557287342694235083529941819644830145463692894576389371194864252193944417249897576680296390036537160332193922853706900504472769773990832173851162215971909022315739548513111748800103501077095982227131161490400275473107114332912752011610992580490036511357042388077219595501595468366432307357375880006328534616109858423036370917076730066512411190813621221988225618801514574381383356699324113692094796970907449469370840049016526662652443809582291319790185342414255291466570332572158841433975328662164311338016851917370479429992007019036364259295950990281576909594760700939581856439476140480808306810823166903862127117572512965716293308583147623766349722954222044113540493984352460455112546555172777189839005308333201885114142111466980905352254535229665410122041438242484536491005787248286883103481601236212094585289510473442558333280384128931643793870559016908029727399281143275162091549243434338130582159038730877484562313951468088162467051046285384314515884048806797355786962180264599960373185136442715557997632215843672184608917328982657966403817121847386761897944779500570824073280196574484365145711215918884480648724038858502746307173620602683682907969598382920518177738917655303213381000153176621747937338966968659109054686337516427263532942648787865802396994723787388617964385931023490

Answer 1

这与此无关BigInteger,这种情况正在发生,因为您的calculate()方法正在调用自身.一旦你的调用堆栈足够深,你的内存就会耗尽而JVM会抛出StackOverflowError.

您的方法中没有任何终止条件calculate().每次进入while循环时,您都会启动另一个呼叫.

事实上,似乎你试图同时迭代地和递归地解决这个问题.

您不应该在代码中同时需要while循环和递归调用.在我看来,如果您只是取消对calculate()您的程序的调用将工作得很好:

public static void calculate(BigInteger s, BigInteger t) {
    while (i < 4000000) {
        System.out.printf("%d\t%d\n", p, i);
        temp = p;
        p = p.add(q);
        q = temp;
        i++;
        // calculate(p, q); // you don't need this
    }
}