java - 为什么BigInteger会在19635年的Fibonacci序列中的整数处以Java中的StackOverflowError结尾

Question

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

我的问题是这里到底发生了什么？我的计算机是否完全耗尽了内存或分配给线程的内存？如果是这样，为什么它专门停在这个数字上？

另外:我将如何计算斐波那契数列的其他数字？

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-大量。

1326878955489024661813666359786489363862597596267841591984718441133687207625589984392446472136708362660021932584888435387175864913621007686907449488726146555339634440057581462744837894455258320181715917058010972459381316662624912515730463333990641248252946263758273263733494371408111666799248602654348374354575665103468235220997087827622833404218721529679546971496790702917758525593195304109707419091078545322602997139876040898483317207843245418460519839008799415039506028557215025158316547186838949994567284348168594751558774303437749976614353207719266172152800399335999724653093452545671783394362809521746195418258628847670756075496906506408478219476651845888891029108480100775783181552094778774012075581174246291938776732162276663007926660261885810696159684398850766130466749892237961368978537350659503384887184590728029938940346029664854098332325276075803004668683973663911965166244655623288976669353392684493773256538286461459851109985316594218567036331110620166503752002858960345948009368720912 9483990019109169869972202653624366647857999434391094762018179263283077871019031113939615673588007412539751140896660550555242286410356957225761374959188921428971568986925032771140869722035908453941369766279904773927026581100216330293759284523441759616193424464255776920179198282898929651696084392141850582592994281421363929270876943636066323962007120387628464011461761740762357314279995093415406703654359369624210821189574276573351209405725688095531085757790385956457905674653179873849894181307352153521970444549381840418885602398030186861851646982941912175759123009610414712538463790168381115394585031993406508479251708300413089091046202402547272127194856959912336070123054000971528209301706716799967865863566308741161048855000242554594776051450015602530130830632799865916436910426907366815701787618197467431739535541208421734061411825946504001994253317591124427008430838958355344794310454651478239057184460401880272193690440447468818908709573559416973460476456159514222828127654757419791409169485455 4413589159098499442131625356509906287285672050080215052926747681492642423016441535060701812422382650607369780485598683879561606185899006941448935168420562235626599835745827700295226714246314734017810402964725369860652473776199131459371207950362024398152881453713163784066208042563543662925682842776015262230520391615679652089970517416773429690840845145299626705629719042357249513002595223367277901469344821405379464226668034873875307681491568655204909774495913318375555411759980733171712799322946052444470529341466911138600782570876081467456539333314140771233788511026610245435362670217650351862005123494882440312897401664665221934387408681977959790208001158782272459157216112763316198348542078709999150647564964914134863576486661123746003816160948281150545905672098416477331230622651937768742259299137290941586718911557287342694235083529941819644830145463692894576389371194864252193944417249897576680296390036537160332193922853706900504472769773990832173851162215971909022315739548513111748800103501 0770959822271311614904002754731071143329127520116109925804900365113570423880772195955015954683664323073573758800063285346161098584230363709170767300665124111908136212219882256188015145743813833566993241136920947969709074494693708400490165266626524438095822913197901853424142552914665703325721588414339753286621643113380168519173704794299920070190363642592959509902815769095947607009395818564394761404808083068108231669038621271175725129657162933085831476237663497229542220441135404939843524604551125465551727771898390053083332018851141421114669809053522545352296654101220414382424845364910057872482868831034816012362120945852895104734425583332803841289316437938705590169080297273992811432751620915492434343381305821590387308774845623139514680881624670510462853843145158840488067973557869621802645999603731851364427155579976322158436721846089173289826579664038171218473867618979447795005708240732801965744843651457112159188844806487240388585027463071736206026836829079695983829205181777389176553032133 810001531766217479373389669686595-9054686337516427263532942648787865802396994723787388617964385931023490

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
    }
}