Skip to main content

DSAPath8 mincore

Recursion

Recursion solves a problem by reducing it to smaller instances of the same problem. Correct recursion needs a base case, progress toward that base case, and a clear combination step.

Why This Matters

Many structures are recursive: trees contain subtrees, graphs have recursive traversals, divide-and-conquer splits into smaller instances, and dynamic programming often starts as a recursive recurrence.

Core Idea

A recursive function must define:

  1. a base case
  2. a smaller subproblem
  3. a way to combine the result

Worked example: factorial uses fact(0) = 1 and fact(n) = n * fact(n - 1). Each call moves toward zero.

Common Mistakes

  • Missing the base case.
  • Recursing without making the input smaller.
  • Forgetting that each call uses stack memory.
  • Recomputing the same subproblem many times; that is often a signal for dynamic programming.

Exercises

  • Trace the call stack for fact(4).
  • Write a recursive tree-size function.
  • Identify the repeated work in naive recursive Fibonacci.

Next Topics

References

  • Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 2, 4.
  • MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020.