jonnifyelixir
F2 / F2.04 / shape

F2.04 · part 1 of 3

The shape of recursion

Every recursive function has the same skeleton: at least one base case that returns a value outright, and at least one recursive case that does a little work and calls itself on a smaller input. Get those two parts right and the function terminates with the answer.

The base case is where the recursion stops; the recursive case is where it shrinks the problem. Miss the base case and the calls never stop; fail to shrink the input and they never reach it. Below: tell the two cases apart, then watch a call unfold into a full expression and collapse back to a number.

Two cases Unfold and collapse Worked examples

Base case or recursive case

A function definition is split into clauses by the shape of its argument. One clause matches the smallest input and answers it directly — the base case. Another matches a larger input, peels a piece off, and recurses on the rest. Reading a clause, ask: does it call itself?

Inspect each clause.

base case
an input answered with no recursive call; where the recursion stops.
recursive case
does a little work, then calls itself on a smaller input.
decomposition
splitting a problem into a small step plus a smaller version of itself.
termination
reaching the base case after finitely many steps.

Does this clause recurse?

def factorial(0), do: 1 base case
base case · an input small enough to answer outright — 0! is 1, no recursion

F1.06 · induction

Base case and inductive step — the proof structure and the code structure are the same.

Elixir

Clauses pattern-match the argument’s shape: 0 or [] for the base, a larger shape for the step.

If a clause calls the function again on a smaller input, it is the recursive case; if it answers without calling, it is the base case.

Unfold and collapse

Following F1.02’s substitution model, a recursive call expands by replacing each call with its definition. factorial(4) unfolds into a tower of multiplications until it hits the base case, then collapses back to a single number. Watch it grow, then shrink.

Step through the expansion.

factorial(4) · substitution, both ways

1 / 10
EXPANDING factorial(4) 


      
step 1 · start with factorial(4)

    

    

      

        
F1.02 · substitution

        
Replace each call by its definition; the expression grows until the base case.

      

      
      

        
the stack

        
Each nested multiplication waiting to finish is one frame on the call stack.

      

    

    
The work happens on the way back: nothing multiplies until the base case supplies the
      innermost value. The deeper the input, the taller the expression — and the stack.