Overview of Recursion

<aside> <img src="/icons/table_red.svg" alt="/icons/table_red.svg" width="40px" /> Table of Contents

</aside>

<aside> 💡

1. Concept of recursion </aside>

<aside> 💡

1. Inefficient Recursion </aside>

<aside> 💡

1. Tail Call Elimination </aside>

<aside> 💡

1. Analysis of Recursion </aside>

Concept of recursion

1. Concept of recursion

   1. Recursion is a fundamental concept in computer science, providing an elegant way to solve problems by dividing them into smaller, more manageable subproblems. It involves a function calling itself directly or indirectly.

   2. Definition

      1. Recursion is a programming technique where a function calls itself to solve smaller instances of a problem until it reaches a base case, which terminates the recursive process.

   3. Characteristics of Recursion

      1. Base Case: The condition that stops further recursive calls.
      2. Recursive Case: The part of the function where it calls itself with a smaller problem.
      3. Call Stack: A stack data structure used to manage function calls during recursion.

   4. How Recursion Works

      1. When a recursive function is called:
         1. The current function execution is paused, and the function call is pushed onto the call stack.
         2. The function processes the base case or makes further recursive calls.
         3. Once the base case is reached, the function starts returning values and resolves the stacked calls.

   5. Simple Example

      1. Factorial Calculation Using Recursion: The factorial of $n$ is defined as:

         $$ n! = n \times (n-1)! $$

         Code:

         def factorial(n):
             if n == 0 or n == 1:  # Base case
                 return 1
             else:
                 return n * factorial(n - 1)  # Recursive case
         
         print(factorial(5))  # Output: 120
         

   6. Applications of Recursion

      1. Mathematical Problems: Factorial, Fibonacci, Tower of Hanoi.
      2. Data Structures: Traversal of trees (inorder, preorder, postorder).
      3. Backtracking: Solving puzzles like N-Queens, Sudoku.
      4. Divide and Conquer Algorithms: Merge Sort, Quick Sort.