A recursion tree draws every call a recursive function makes: each node is one call, and its children are the calls it makes itself. Once you can draw one, you can see how many calls there will be, how deep the recursion goes, how much work happens at each level, and whether the same subproblem is solved repeatedly. That gives you the time and space complexity and the hint for fixing slow code.<\/p>\n
Below you will draw trees for factorial, Fibonacci and merge sort, get Python to print them for you, and learn the questions to ask of any tree.<\/p>\n
fib(3)<\/code>.<\/li>\n- Children:<\/strong> the calls made directly by that call.<\/li>\n
- Leaves:<\/strong> calls that hit a base case and stop recursing.<\/li>\n
- Depth (height):<\/strong> the longest path from the root to a leaf. This is how many calls are waiting on the call stack at once, so it sets the space<\/em> used by the stack.<\/li>\n
- Total nodes:<\/strong> the number of calls, which together with the work per call gives the time<\/em>.<\/li>\n<\/ul>\n
The call stack and the tree are related but not the same: the tree shows every call that ever happens, the stack holds only the path from the root to the call currently running.<\/p>\n
Linear recursion: factorial<\/h2>\ndef factorial(n):\n if n <= 1:\n return 1\n return n * factorial(n - 1)<\/code><\/pre>\nEach call makes one call, so the “tree” is a single chain. Add a depth argument and print on the way in and out to see it:<\/p>\n
def fact(n, depth=0):\n print(\" \" * depth + f\"fact({n})\")\n r = 1 if n <= 1 else n * fact(n - 1, depth + 1)\n print(\" \" * depth + f\"-> {r}\")\n return r\n\nfact(4)<\/code><\/pre>\nfact(4)\n fact(3)\n fact(2)\n fact(1)\n -> 1\n -> 2\n -> 6\n-> 24<\/code><\/pre>\nFour nodes, depth four, constant work per call (one multiplication). So the time is O(n), and since the stack holds n frames at the deepest point, the extra space is O(n) too. This also shows where the answer is built: results flow back up the chain on the way out.<\/p>\n
Branching recursion: Fibonacci<\/h2>\n
Now each call makes two calls. This function prints its own tree, indenting each level:<\/p>\n
def fib(n, depth=0):\n print(\" \" * depth + f\"fib({n})\")\n if n <= 1:\n return n\n return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)\n\nprint(fib(5))<\/code><\/pre>\nfib(5)\n fib(4)\n fib(3)\n fib(2)\n fib(1)\n fib(0)\n fib(1)\n fib(2)\n fib(1)\n fib(0)\n fib(3)\n fib(2)\n fib(1)\n fib(0)\n fib(1)\n5<\/code><\/pre>\nRead it top to bottom as a depth-first walk: the program goes down the leftmost path (fib(4)<\/code>, fib(3)<\/code>, fib(2)<\/code>, fib(1)<\/code>), returns, then takes the next branch. Look at what the tree shows:<\/p>\n\nfib(3)<\/code> appears twice and fib(2)<\/code> three times. Those are repeated subproblems.<\/li>\n- The tree has 15 nodes for n = 5, although only six distinct values (0 to 5) are needed.<\/li>\n
- The depth is n, so the stack space is O(n).<\/li>\n<\/ol>\n
Counting calls shows how fast it grows:<\/p>\n
n = 5 15 calls\nn = 10 177 calls\nn = 20 21,891 calls\nn = 30 2,692,537 calls<\/code><\/pre>\nEach added step multiplies the work by about 1.6, so the time is exponential: O(2^n) is the usual simple upper bound, and the tight bound is about 1.618^n. This is the picture to have in mind when someone says “naive recursive Fibonacci is exponential”.<\/p>\n
Fixing the repeats with memoization<\/h3>\n
Memoization stores each result the first time you compute it. Here is the tree with cache hits marked:<\/p>\n
def fib_memo(n, memo=None, depth=0):\n if memo is None:\n memo = {}\n tag = \" \" * depth + f\"fib({n})\"\n if n in memo:\n print(tag + \" <- cached\")\n return memo[n]\n print(tag)\n if n <= 1:\n return n\n memo[n] = fib_memo(n - 1, memo, depth + 1) + fib_memo(n - 2, memo, depth + 1)\n return memo[n]\n\nprint(fib_memo(5))<\/code><\/pre>\nfib(5)\n fib(4)\n fib(3)\n fib(2)\n fib(1)\n fib(0)\n fib(1)\n fib(2) <- cached\n fib(3) <- cached\n5<\/code><\/pre>\nThe cached nodes are leaves: they return at once without branching. Only the leftmost chain is expanded fully, and each value is computed once, so the work is O(n) calls and the depth is still n. With functools.lru_cache<\/code>, fib(30)<\/code> runs the function body 31 times instead of 2.7 million.<\/p>\nOne Python trap: do not write def f(n, memo={})<\/code>. A default dictionary is created once and shared across all calls, so it persists between calls (which may look like a feature but surprises people). The None<\/code> default above creates a fresh one per top-level call.<\/p>\nDivide and conquer: merge sort<\/h2>\n
Merge sort splits the list in half, sorts each half recursively, and merges. For eight elements the tree is a balanced binary tree: 1 node of size 8, 2 of size 4, 4 of size 2 and 8 of size 1, which is 15 calls in total.<\/p>\n
\n- The depth is about log2<\/sub> n (3 splits for n = 8).<\/li>\n
- At every level the sizes add up to n, and the merging at that level costs about n.<\/li>\n
- So the total time is n work per level times log n levels, O(n log n).<\/li>\n<\/ul>\n
This level-by-level addition is the standard technique for analyzing recursive algorithms with a recurrence like T(n) = 2T(n\/2) + n. Add up the work at each level, then sum the levels. The Master Theorem is a shortcut that formalizes the three typical cases: the work is dominated by the root, by the leaves, or is balanced across the levels (which gives the extra log n factor here).<\/p>\n
Contrast this with Fibonacci, where the subproblems are only slightly smaller (n – 1 and n – 2) and overlap. Halving the problem gives a shallow tree; shrinking by one gives a deep one.<\/p>\n
Questions to ask of any recursion tree<\/h2>\n\n- How many children does each node have?<\/strong> One means a chain (O(n) calls, typically); two or more means growth that may be exponential.<\/li>\n
- By how much does the input shrink?<\/strong> By a constant (n – 1) gives depth n; by a factor (n \/ 2) gives depth log n.<\/li>\n
- How much work does each node do besides recursing?<\/strong> Multiply by the nodes per level and add the levels.<\/li>\n
- Do any subtrees repeat?<\/strong> If so, memoization or dynamic programming can collapse them.<\/li>\n
- How deep is it?<\/strong> That is your stack space, and the risk of stack overflow.<\/li>\n<\/ol>\n
On the last point, Python limits recursion depth, 1000 by default. A chain of 5000 calls raises RecursionError: maximum recursion depth exceeded<\/code>. A balanced tree like merge sort’s never gets close, since its depth is log n, but a chain on a long input does. In such cases rewrite it as a loop, or use an explicit stack. See our article on recursive versus iterative algorithms<\/a>.<\/p>\nUsing trees to debug recursion<\/h2>\n\n- Missing or wrong base case:<\/strong> the tree has no leaves, so it never ends (
RecursionError<\/code> in Python).<\/li>\n- Not making progress:<\/strong> an argument that does not shrink (for example
f(n)<\/code> calling f(n)<\/code>) shows up as identical nodes down a chain.<\/li>\n- Off-by-one at the base case:<\/strong> draw the tree for the smallest inputs (0, 1, 2) and check each leaf’s value by hand.<\/li>\n
- Wrong results:<\/strong> print the tree with arguments and return values, like
fact<\/code> above, and find the first node that returns something you did not expect. A debugger’s call stack shows the same information for one path at a time.<\/li>\n<\/ul>\nDrawing trees<\/h2>\n
For interviews, draw by hand: write the call at the top, write the children underneath, stop at base cases, and annotate the size or work per level. A tree for input size 3 or 4 is usually enough to see the pattern. For visual tools, Graphviz (with the graphviz<\/code> Python package) can render a tree if you record the parent-child pairs while the function runs. Also, Python Tutor<\/a> animates the call stack step by step for short programs.<\/p>\nPractice<\/h2>\n\n- Draw the tree for
subsets<\/code> of a list of 3 items (each element is either included or not). How many leaves does it have, and what does that say about the complexity?<\/li>\n- Draw the Tower of Hanoi tree for 3 disks. Count the nodes and find the pattern.<\/li>\n
- Draw binary search’s tree. Why is it a chain, and why is its depth only log n?<\/li>\n
- Take any recursive function you wrote, add a depth argument, and print its tree.<\/li>\n<\/ol>\n
If you are new to recursion itself, the lessons on recursion<\/a> and recursive Fibonacci<\/a> in AlgoCademy’s Python course are a good start, and the post on coding exercises for mastering recursion<\/a> has more problems to draw.<\/p>\n","protected":false},"excerpt":{"rendered":"Learn to draw a recursion tree, count calls and depth, read time and space complexity from it, and spot repeated work, with Python code that prints the tree.<\/p>\n","protected":false},"author":1,"featured_media":6928,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[23],"tags":[],"class_list":["post-6929","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-problem-solving"],"_links":{"self":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6929"}],"collection":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/comments?post=6929"}],"version-history":[{"count":1,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6929\/revisions"}],"predecessor-version":[{"id":8716,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/posts\/6929\/revisions\/8716"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media\/6928"}],"wp:attachment":[{"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/media?parent=6929"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/categories?post=6929"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/algocademy.com\/blog\/wp-json\/wp\/v2\/tags?post=6929"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}