Back to course

Lesson 14: Introduction to Recursion (The Concept)

Algorithms: From Zero to Hero (A Beginner's Guide)

14. Introduction to Recursion

Recursion is a technique where a function calls itself, either directly or indirectly.

It is essential for certain algorithms (like tree traversals, Quick Sort, and Merge Sort).

Two Essential Rules of Recursion

  1. Base Case: A condition that stops the recursion. Without a base case, the function will call itself infinitely, resulting in a Stack Overflow error.
  2. Recursive Step: The part where the function calls itself, usually on a smaller or simpler version of the original problem.

Example: Calculating Factorial

The factorial of 5 (5!) is 5 * 4 * 3 * 2 * 1. Notice that 5! = 5 * (4!). This self-reference defines the recursive step.

python def factorial(n): # 1. Base Case: Stops when n is 0 or 1 if n <= 1: return 1 # 2. Recursive Step: Calls itself with a smaller input return n * factorial(n - 1)