AlgoPlus//structures / recursion
Read the theory

Recursion · Call Tree

Every recursive call branches into more calls until a base case.

Function
fib(5)
Total calls
0
Legend
Active call
Returned value
Not yet called
AI Tutor Workspace
—
In a nutshell
Recursion solves a problem by having a function call itself on smaller pieces and then combine the answers, stopping at a base case it can answer outright. It reads cleanly, but plain recursion can redo the same small problem many times — naive Fibonacci recomputes its lower terms over and over, which is why it balloons to exponential work.
Ready
Press play to begin the cinematic walkthrough.
A function that calls itself splits a problem into smaller copies — but naive recursion recomputes the same subproblems again and again.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Recursion · Call Tree.
Code Simulator
▼
1
def bst(root, val):
2
    # insert / search / traverse
3
    if root is None:
4
        return Node(val)  # Inserted/Found
5
    if val < root.val:
6
        root.left = bst(root.left, val)
7
    else:
8
        root.right = bst(root.right, val)
9
    # traversal order
10
    visit(root.val)  # Visit
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.