Recursion

• What is Recursion?
• Base Case & Recursive Case
• How Recursion Works
• Call Stack
• Examples
• When to Use Recursion?

1. 1Function Call

   The function is called with some input.

   fact(4)
2. 2Recursive Call

   The function calls itself with a smaller input.

   fact(3)
3. 3Base Case

   The function reaches the base case and returns.

   fact(1) = 1
4. 4Backtracking

   The control returns back, computing the result.

   Returns 24

Factorial of n (n!) = n × (n-1) × (n-2) × ... × 1. Base case: 0! = 1

1function factorial(n) {
2  // Base case
3  if (n === 0) {
4    return 1;
5  }
6
7  // Recursive case
8  return n * factorial(n - 1);
9}
10
11console.log(factorial(4));  // 24

Stack grows on calls and shrinks when the base case is reached.

• Every recursive solution must have a base case.
• Each recursive call moves closer to the base case.
• Recursion uses extra memory (call stack).
• Not all problems benefit from recursion.

Always define a base case, otherwise the recursion will run infinitely!