computer-science/recursion-why-fib-30-makes-2-7-million-calls-and-how-a-notebook-fixes.md

Recursion: why fib(30) makes 2.7 million calls, and how a notebook fixes it

Computer science · 5 min read ·

A function that calls itself sounds like an endless loop, but it works when every call gets a smaller problem and one case is simple enough to answer directly.

Step through the calls of a Fibonacci function, see why computing fib(30) takes 2,692,537 calls, and watch a simple notebook of remembered answers cut that to 59.

A tree of circles showing every recursive call to fib(5), with repeated calls highlighted in orange

$ ls computer-science/

see all →
computer-science/hash-tables-how-python-finds-a-key-without-searching-for-it.md Hash tables: how Python finds a key without searching for it You type `ages["cat"]` and Python answers instantly, even with a million entries. It does not search. It calculates where "cat" must be… 4 min read · 5 Oct computer-science/what-is-an-algorithm-watch-two-recipes-race-to-sort-six-bars.md What Is an Algorithm? Watch Two Recipes Race to Sort Six Bars An algorithm is a recipe so precise that someone who doesn't understand the goal could still follow it and get the right answer. Computers… 10 min read · 1 Oct computer-science/linear-vs-binary-search-why-30-guesses-can-beat-a-billion.md Linear vs binary search: why 30 guesses can beat a billion Need to find one item in a list? You can check every item in turn (linear search), or, if the list is sorted, look at the middle and throw… 10 min read · 1 Oct