Problem Solving

Recursion

Students open wooden boxes nested inside one another.

Recursion definition

Recursion defines or solves a problem using smaller or simpler instances of the same problem.

In Spanish
recursión
Topic
Algorithms and problem-solving

Recursion in a picture

Recursion diagramA recursive sum of 1 through n uses the sum through n − 1.Base: S(0) = 0The empty sum is knownStep: S(n) = n + S(n − 1)Use the same rule on a smaller inputS(3) = 3 + 2 + 1 + 0The calls reach the base case
A recursive sum of 1 through n uses the sum through n − 1.

How it works

A recursive procedure handles a base case directly. In other cases it calls itself on inputs closer to a base case and combines the returned results as needed. The reduction and the base case together allow the procedure to finish.

Worked examples

Evaluate F(3) if F(0) = 1 and F(n) = 2F(n − 1).

F(1) = 2, F(2) = 4, and F(3) = 8.

Why is the base case needed?

It gives a direct answer and ends that chain of calls.

Does calling the same rule with the same input guarantee progress?

No. A terminating design needs a path to a base case.

Common mistake

Make sure every recursive call progresses toward a base case. A recursive formula alone can leave a value undetermined.

Quick check

What kind of problem instance does a recursive step use?

Can recursion have two base cases?

Show answer

Yes.

What stops a recursive chain?

Show answer

A base case that returns without another recursive call.

Sources

Flashcard

Recursion

Reveal the definition

Recursion defines or solves a problem using smaller or simpler instances of the same problem.

Effortless Math. “Recursion.” Math Dictionary.