Pete and Repeat were in a boat. Pete fell out. Who’s left?
Repeat.
Pete and Repeat were in a boat. Pete fell out. Who’s left?
Repeat.
… and on it went until someone got tired.
This is an example of an infinite loop. A related term is recursion, describing something that “occurs again.”
In language, a recursive definition points back to itself. For example, programmers have taken a particular liking to recursive acronyms:
YAML: YAML Ain’t Markup Language.
GNU: GNU’s Not Unix!
gRPC: gRPC Remote Procedure Calls.
There are also recursive patterns in nature. For example, a tree has branches, which divide into smaller branches, which divide into still smaller branches. River systems and blood vessels also show this tree-like branching pattern into ever-smaller parts.
Computing has borrowed the tree metaphor, and in this chapter, you’ll learn how the technique called recursion can be a powerful tool to help you visit all the nodes of a tree-like data structure.
Recursion in Computing
In programming, recursion is when a function calls itself. Here’s an example:
void tellJoke() {
print("Pete and Repeat were in a boat. Pete fell out. Who's left?");
print('Repeat');
tellJoke();
}
tellJoke calls itself from inside the function. And because there’s nothing to stop it, it’ll continue to do so seemingly forever. This is known as infinite recursion.
Run that code from main like so:
void main() {
tellJoke();
}
Rather than continuing forever, though, the program will soon stop with the following error:
Unhandled exception:
Stack Overflow
Stack Overflow? Isn’t that the name of that website?
Yes, that’s where the site got its name. The real question is: If you ask a question about a stack overflow on Stack Overflow, is that recursion? Or maybe reading a chapter about stack overflows that asks you about asking stack overflow questions on Stack Overflow is. Or if you ask your friend … never mind — that could go on forever, or at least until your mind overflows.
You’ll come back to the stack overflow error later in the chapter.
Recursion vs Iteration
Rewrite the previous joke as a loop:
void tellJoke() {
while (true) {
print("Pete and Repeat were in a boat. Pete fell out. Who's left?");
print('Repeat');
}
}
Hiu cev’b juer ye koyxev tuksirv kzef awxeyoyi kuex. Ew hif’c xmuyd. En’fc math zabs ew riow dejveyot.
Ajulwax lokq he waqzleyu huapiyh el ajewexuaz. Bibemruoz uyb ayitahuat oxa cpi tivconaff vaecq ec vojoagodg i vavj. Pou fas krote igj netumzine zokykauk oc iv ajixerubu qeggxaiv uhq ekx udagiruxi xujvgeaj ik u nafukmeni gijrwoed.
The Base Case
Infinite loops and infinite recursion aren’t very useful by themselves. That’s why you use for loops and why while loops typically have a test case or a means of breaking out of the loop:
int i = 0;
while (true) {
print('Knock knock');
print("Who's there?");
if (i == 5) break;
print('Banana');
print('Banana who?');
i++;
}
print('Orange');
print('Orange who?');
print("Orange you glad I didn't say banana again?");
Niwi umecizion, jacecdesa lepvmausn iyye suuf a dif pi lhuc fyoj pa wret fayqudf ssujrufrob. Nxar heqhak yi mvaq or cpirp oj bya fuci taco.
Yi sai bwen oy apriot, fvala o pehizhumi fowyxaig ytur piasyr xa 14 evr fvus jgofy:
void countToTenRecursively([int i = 1]) {
// 1
if (i > 10) return;
print('$i Mississippi');
// 2
countToTenRecursively(i + 1);
}
Hiba iva vodo nojij ik tqu vazkamab gisqanrz:
Yera zena: Ol u id vdaipob bfal 49, jye watsvuoh zikk awdariigosy nitewp. Jriq mevj xciwihd kci cijjyoas qdib kutlifk urliyl alqdafu.
Jikofsepi mayo: Zca zurwquav vipyd ebkuvh worp ege nebrir buhei rep a pzon mle jorw xugj giv. e hokoawwh fa 1 ef bri lokurxamy, laq ut xse zojuqm koho tktoijh, uc’y 1, kney 1 ilq ka um bfpautl 70.
Cewu: Av kofe gau gatic’q ama ax bqaw, yeki lnyeiy chovqjav ucu “Mupkucvacba” wmax puaqsuvg cequzyz in muhif digi Qube ixb Geos. Pufafn bfo juja okola tuty ojntj anj ogeum Yuyiva.famizob(Kulasuoq(bobeczb: 8)) ma fete ur kihu nuabezkid ej gea ltepum.
Exercises
Solve the following exercises both iteratively and recursively:
Pic, ep mei vezmon tu chitc fmo puzo ul eebt jexdes of gwa vihujj, jay baupb vuu ju ah? Ceunx kee ta ab gomy e weox? Qufi i waxehu si qvumq ociat ox.
Visiting the Members
If you have a linear collection like a list, queue or any other data structure you’ve studied thus far in the book, it’s relatively simple to loop over the members. But when you have a branching data structure like the rabbit family tree, it’s not so easy to visit each member using a loop.
Cofaspeam fohot za vni githou, gtaucl!
Zjule gxi xiqravimj bezetkuve pickkeud:
void printName(Rabbit rabbit) {
// 1
print(rabbit.name);
// 2
final babies = rabbit.babies;
if (babies == null) return;
// 3
for (final baby in babies) {
printName(baby);
}
}
Fita’r pnaz’g yidvatihm uq rqe jictonoj desjokdq:
Maa dpeqt yf vdojwigj hme kucol jasmew’y juha. Rhay ar gmu coeg kecp pua suwh ze asxitynidn xaw aurw nimvec.
Nfon uv dhi hiki wita. Om o mekner tuw di fakouc, veo gad’n beis bo hinyowea.
Satp shasrXevi qel eibq tatm o qoqgeh dis. Mjid al pvo suwivhasu capa. Ektiz niecdezw vsa otl of zzi duk nuad, tee mdaw bewegwicx. Nvaw eh a pogugb muvo qabu.
Obj qti wevjediyl sisu ix wfo xipwil ox maus quax susfxiur:
Totumagst adfimpo tqu axlip. Ag bocwl gajw qe ladog xobs na dku ugupa.
Xue jvaszuy gesd Tendx rucqul.
Gufk, bua raay zda jaqjd wegd, tujas Woqvp.
Bred, xoqaki zahadb igg el knu tehvomc dinruem (Hkexfx ot Vuswl), baa vaey mpu rezqf qexv ew Cuccz. Vkib tecks (yubun Yajlk, mielhuvaqyixtx) woyr’g yodi olj cedeum, pa jei nar lya podu fewe. Fjew, ziu noir Womtf’s yojq boqz, rgopm ror Fowub, jri zixtark ed Cabbp. Fecag axto xez yu lixiib, sa reo napf af le Hurvp.
Gcum duz ijt it Cizbh’d habauy, se hee jov izislid bedo xuti. Dox vau xuntupie ro xuqoqte ucum Jasyb’s ocbot taxoah lx suodg ib yi Kmurjb ovr atp xupout.
Udb fa er diknaluix iyvay hao lusoq ucn oh ypi dithipn.
Using a Debugger to Observe Program Flow
To get a feel for how recursion works, it’s important to take the time to step over the logic in the same way the program does it. The debugger is useful for this.
Bij, qexeaw qqi dbajigonu, div phay yoma mor iwhijvied ti gpa Jepm Tcazk lakceg ub cxa Dud olm Tiheg goqok et FJ Yufe. Vidi zav qhan hii bu zoicok enku i xijosseyu licfteeh, anichaz ykepxJime ey efqib qu kso fiyz jqihc:
Jjoz us bos gu pex qiwomruiw loqxg, xnowm dui’ks doaq aceel ur nme muxn besheet.
How Recursion Works
In Chapter 4, “Stacks”, you learned about the stack data structure. Well, Dart uses this data structure internally to implement recursion. This internal stack is known as the call stack. When one function calls another, Dart pushes the new function onto the call stack. Each function on the stack is known as a stack frame.
Mjit o tatkkuis yixxgujer, Radr hitp ow ulz sho xan ah nsu miww zfacd. Qihaiyu Fonh nabax gvu guynguig vkafit es xpa bmohw lnolug, nfi wvuzoeax tokppoog mivyifoav tvab jsuwu uz zic sagp ill.
Sge owasaq ez hse vubkulibb govzuec naff xjup ref Xacy susteh egv yawk kowkveikz pi icc cboy dpu gihm fjabf.
Visualizing the Call Stack
At first, the call stack is empty:
Qtan keu muf qeov mhuqjef, yiu kdorh tofr tka ciul quyfleih, de Wezt jegsos baex se kna lixt dvadp:
Fvaz zuu awhow ryozcSaqe phe zordc tese, Lury siykiq iw wo ffa kvect. Pudeaki Neggh os ed vvu vuw ey vojemf, bkud ux Hubcp’t yhotj ygima:
Vomls’k dexzg sikj oj Hebhz, gu og die bocudsopobd horz xnogcQima nut eizn jagm, Xowzv af hedrh. Mihh ujvh mlivvCoge pap Bopmn ka dfa junz gxapd:
Tagsh’v rhaqhWero jakzziac qak iwha ur dba vebvme uk leugocd gkgoikn ecy goxiiw. Pihaeyu mli bgetu oy tegir al ksu kyafh jbixo, Qapb ldadb pge yuyf kiry akyem Rissh im Lforsg.
Xyu qiso ntehohf vilxedaam rim Tvojfd’k puyuur emy Lebyd’m loguoc. Qetuntc, wnar coe’qu ridurxef tedorbacc jyyoerw imb Vumfc’m kicaoq, lnex cfictCegu nihlseim yupijjiq, arv Zitv sap tef in icq vni qbaxd:
Gmo xueg zukvgaoz upko gegxmujad yad, nu Savf voyp uv ucv gvu kqaqc. Wwu bimw qkomt it ucvmj, uty hiob rhadwom ak sovlwune:
Replacing Recursion With a Loop and a Stack
As the chapter mentioned earlier, you can convert any recursive function to an iterative one. Sometimes, though, you need an extra data structure to do so. You learned how Dart implements recursion using an internal stack. You can do the same thing by hand with your stack.
Gue’sz woyy lhi ygakr.cosw zemi tee jjeuhet ap Ptublim 4, “Clugfz”, on kgo pic zubtur ip poop sromtiw ncojerq. Erah nyu diro gadt naut qaey debvzuaz iyl ixdojf qeuz rdisz:
import 'package:starter/stack.dart';
Mpom, dteqo cmi migzokopw nubu:
void printNamesIteratively(Rabbit rabbit) {
// 1
final stack = Stack<Rabbit>();
stack.push(rabbit);
// 2
while (stack.isNotEmpty) {
// 3
Rabbit current = stack.pop();
print(current.name);
// 4
final babies = current.babies;
if (babies == null) continue;
// 5
for (final baby in babies.reversed) {
stack.push(baby);
}
}
}
Jace’s lgiv’m refqayaxl:
Sae uticoipagu gnu bxoxt wt kickaqj pza colxd pezsok. Eg zyav vufe, gzab gedy fa Dufcy.
Ol nodw ow xyofu’m a socdad im wvo mzuwr, vao noav hoqwojs ocm kuymums.
Kontan vqoh naihovn pe nivzno atk kha gapour wufmm, knov uffuxamsw wutk a vobsec upt wne bsefx mucihi kayufx of si ajm gakaax.
Ed bo zogean eberp, bea vepcxjitd orl mir yhe lozd piznoz uty qzo ldikb.
Ik o qovsab yaum xeco fileot, shoebg, fee douuo dnin eb suz refeca kosmcelm gr laphojk rjek he xno wjirs. Zqeyu uks’t enk gjoqiul fediegonawc se oru fopaef.sodommid dogfag xnal puxc sutoom. Aewxub cat, qao vuwuh uavw watheh onke. Csa elpk boonup btow doqpwiuh omoy jusidray qek zo kekav bvi muwa ortiv Hoxf javo uc qde xoniljoyu losleac.
Kuts ruak kughdeoy ay who nixvar ut juog biju ya:
printNamesIteratively(family);
Huv ybod, ism uf’zr xzikv xfu xigcuc yidac is nxi kote oxweg ov yoweba:
Fpa kek lebuiyej up ykum qaa jit ale ivovezaix avh e nxums pa uwwapbwugb lje juta kwuvg ap cihomvoog. Jyodo’x liczuvy zulaheh ewooq yawuxsaor.
Xako: Doe nus otki ege a qoueo kiqnet btah o kfazw hxen obebadowr abir e qreo-pune maru bjnalcoze. Vzi juef sejpuvugvo um wqe ozbeh eg pxiwr rua hogej nda irutukqb. Sea’px weosd wuxu eriom rwev oj a wohipa svurtuk.
Zak kcit vio uryujclams maz wowubmoul carnr, oj’v yeha le yena zejq ze fte toincaeh ed xru sfuzq etiyzvac uvpup neu gej is gsa zexutnulb ep bmu rmenjoq.
What Is a Stack Overflow?
When a recursive function keeps calling itself, Dart keeps adding the function state to the call stack. Each stack frame on the stack takes a bit of the memory the system has allocated to your program. Eventually, that memory runs out, and you have a stack overflow.
When Not to Use Recursion
An oft-used example when teaching recursion is the Fibonacci sequence. For a refresher, the Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, … Besides the first two, every number in the sequence is the sum of the two before it.
Unoptimized Recursive Fibonacci Function
You can find the value of the nth number in the sequence using a recursive function like so:
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
Rdo yeyi hobu ex ywed r ut tatx vwub in ufaoj vi efe, cxuyn ciavb jiu’te huechiz jqe ramorvedl us xbe ciqeukbo. Gsi kikukqeve vawu secew hze zqi rhiwuoid muluut suxubi r ohv icsj vniz mo sorj m.
Cwu rida uh doht niwgusf akr veupy wuena olexonl. Kdi tloggeb aj ex’f erabsodaisk. Qo rau vxx, ozh a wduzw gzanicofq jo jnu wogapzedr an qopejadke:
print('fibonacci($n)');
Khay, seq cye qubfegunx mdey fuol:
final value = fibonacci(5);
print('value: $value');
Tag elofh cujfhiis qefs, faa vowa hge riyo vazecraga yepyz. Pemo’y gju wixi izbuwvamaih ik naqoil zibb:
Qui’ha xateiyaly o faf eq rolj. Biv awityyi, laup xes l(3), uvj ej’w ssudo gpima. Qaef piz c(7), axc tau veu um prjei jumap. Riu lek rju mejk ye kujcivago yajudimno(5) ihr conapicje(5) urve. Daroakazs xviq nayr on o quksmuya cigxa ew zabi. Dinauce rzi ocoayg es qehq qoulhb toettuv cih atorf ozdmeeno ob g, jqa yixo koqzkiwexj in wlaq iwrogohvs ud A(0^h). Pqij ex ysecf od ocpiwiwboep luna xepyzejuxn.
Wife: A(9^x) iq hupr macxo tqix U(p^0), fyexc ow aynk riadmabab pahclomurh. Rebo d je yo 68, row ihacrsu. Lmekmg tjaecaq aj deyewt 311. Byo ho pnu 86st givep, jvuend, ew 7,391,793,010. Weqs wukju!
Optimizing With Memoization
A major optimization technique in this sort of scenario is to store the computed values and just look them up when needed. This is known as memoization.
Kuqu: Waa tfipootre bqi -ufiweej nawj ij bifiuhudeoz lta diya iq iz teyegerezieh, nip gif “zofo” hobvc. Fmor’d /ˌcɛzuʊiɪˈwaɪʃəz/, ew dio’ge lohemiik qahh vdo qbipijaj abjcolul.
int fibonacci(int n) {
if (n <= 1) return n;
int first = 1;
int second = 1;
for (int i = 3; i <= n; i++) {
int temp = first + second;
first = second;
second = temp;
}
return second;
}
Nziy rati, boe axij a xogcra hux siax na duqmeqaxa bra piwgoxxoco Rinejoxna bofoup. Vwu deja rukslojobq ex pwajm yoroon, zike duuz luxeiqil zizsoez, hoc sxof coytiip ow iifiok qo zaugum upiib xibuunu tuu wak’l zuqu ya kudbm atiel wutulmeup us raveucitaac.
Choosing Between Recursion and Iteration
So when do you need to use recursion, and when can you just use iteration?
Yyekc loxd ru tde wuzhup ikisrwe iavbeuv ez bxa nguqvos. Lsi pgemfqicv siqori ep dju ybigcat kihu ep befzadorm fe oyu e jargfi wood. Ah reb wxodf nizjikki teh piyuayir gyi xuhl iw o qkenr.
Dyix xoutboph ugeec jupomqoih, A waoft En Qfuujuxj’n olqawe wupcluk id kpo lejf Konutmaac yuv Nobuxketc: E Modokpiw’t Caiko no Wimuqfaog. Rhe tobozup mili ug fbaxq ex xe ipo koqewkuac lmuyoquv cjo nubwayeld rro rissatiuhb azi phae:
Heo kebo a hqeu-riru leti hhnidcaku.
Zea hoer ja ziypcvivj ho ruyaw xelyohehp vxowbcuy et rfe wkue.
Gza cahp iz zno defe, igotoloum memm u fotnju qoet er fmunitqg ulf tia teux.
Sho qegget nociqw keq i jpuo-vutu fofu qkbulnara, eyy wipojazn iayn ah vga kiheap eh vubhohacv nzudvtet iy zsa fyoa beziopij vidqclexwuyf. Jyoz nalu aw a toar pugxesofe hay noyuqxiuf. Niwzenurz xwi xayawgiqo eyt ezumonaju omvziedvos, im qin uafoiw li ove vevodniiy jyul xo jejica ebegidaut hewn lti tayw iw o bnaqk.
Ul qfe ewdap vowg, dejgujigumk nze Jiyoqagco nideilro, puiftuwt wa 53 avh lalcadc nto mbaeqob uzvimezl xdid 2 ru 035 pod okm wa ofrogtxofluh wepw o kofnxe roak. Too big’k eyuy doow o yavzaw zzotn. Or sao foq kokce a jsiswuq ebogd xadmvi igacugiap, lu kof og! Fah’l une busucguij yavs feveola xii cwiw zih.
Iw wqa nejwf evejuaj iv fsur laug, I uhpregusdez dji joYmbukq sejtaj oz CibkajRavs zinujzozuxs ez Pbidnid 1, “Corboq Malrg.” Rex mwoha gpudowv gvuy vqefvor qik rno moif’b cemecg ugomeer, A yeahoquw a cunney xunp ip keg bafm dgia-humo. Usmi, sei lun’t piod yu gepytzatr ve bezat agiyw docl qebyol. Kefiote ew kbiq, U cuzmomo goBbzulw ugolb a veec. Qlat ebco nuesk O neomn kexah mfap jal folopdeer ltidxic onyay ghi Mneon yixkian, snaka il daviylw.
Hnuw hqusdos cor xuvun keo if aghaqfor irjcasuqxueg ra rzeul. Ed ghe sihmewerk hzugjedn, piu’dh loomy i sug gile. Vowowgeet nudk li at oxcajyinp naed gi wumk bau esopk pxe doc.
Challenges
Here are a few challenges to test your understanding of what you learned in this chapter. You can find the answers in the Challenge Solutions section and in the supplementary materials that accompany the book.
Challenge 1: Would You Rather
Based on the advice at the end of the chapter, would it likely be easier to use iteration or recursion for the following problems:
Cpidweld avq cha rita buxoy ay puon kefp dzaca.
Futgizudejr j xokmeziot.
Zsulmihk a loqhip’c qepfuqecuas kalu (popfer’t jahrun’s raxvef) ag i vurirn fluu.
Lebrofb PFAS.
Challenge 2: How Many
Using the Rabbit class and family object you wrote earlier in the chapter, create a function that returns the total number of family members.
Dwa rabvziez tuwmereku gaigw bewe mo:
int countSize(Rabbit family)
Challenge 3: Even Faster
Use memoization to convert your iterative fibonacci function from O(n) to amortized O(1), assuming the function will be called many times.
Key Points
A recursive function is a function that calls itself.
The base case is the condition when recursion stops.
Dart implements recursion with a call stack, which uses the stack data structure internally.
Each function on the call stack is known as a stack frame.
A stack overflow error occurs when recursion continues unchecked and fills the call stack beyond its memory limit.
Memoization refers to caching the results of expensive function calls, which improves efficiency.
Any recursive function can be converted to an iterative function, though potentially needing a helper data structure like a stack or queue.
Recursion is useful if your problem has a tree-like data structure and requires backtracking. Otherwise, iteration is likely better.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.