---

⭐ Recursion in Python

Recursion is a programming technique where a function calls itself to solve a problem.

A recursive function breaks a large problem into smaller sub-problems and calls itself repeatedly until the problem becomes simple enough to solve directly.

---

🔹 Definition

Recursion is a method where a function calls itself directly or indirectly.
It works by dividing a problem into smaller instances of the same problem.

---

🔹 How Recursion Works

Every recursive function has two parts:

1. Base Case
   → Condition where the recursion stops
2. Recursive Case
   → Function calls itself with a smaller input

---

⭐ General Syntax of Recursion

def function_name(params):
    if base_condition:
        return result     # base case
    else:
        return function_name(modified_params)   # recursive call

---

🔥 Example 1: Simple Recursive Function

def countdown(n):
    if n == 0:      # base case
        print("Stop!")
    else:
        print(n)
        countdown(n-1)    # recursive call

countdown(5)

---

⭐ Example 2: Factorial Using Recursion

n! = n × (n−1)!

def factorial(n):
    if n == 0 or n == 1:  # base case
        return 1
    else:
        return n * factorial(n-1)   # recursive call

print(factorial(5))

Output:

120

---

⭐ Example 3: Fibonacci Series Using Recursion

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))

---

⭐ Example 4: Sum of digits using recursion

def sum_digits(n):
    if n == 0:
        return 0
    return (n % 10) + sum_digits(n // 10)

---

⭐ Example 5: Reverse a string using recursion

def reverse(s):
    if len(s) == 0:
        return ""
    return reverse(s[1:]) + s[0]

print(reverse("Python"))

---

🔹 Types of Recursion

1. Direct Recursion
   Function calls itself. def f(): f()
2. Indirect Recursion
   Function A calls B, and B calls A. def A(): B() def B(): A()

---

🔹 How Recursion Works Internally

Recursion uses a call stack:

1. Each recursive call adds a new entry to the stack
2. Base case stops further calls
3. Return values are passed back down the stack

---

⭐ Advantages of Recursion

✔ Code is cleaner and easier to understand
✔ Problems like factorial, Fibonacci, tree traversal are easier
✔ Reduces complex loops

---

⭐ Disadvantages of Recursion

❌ Slower than loops
❌ More memory usage due to call stack
❌ Risk of stack overflow if no proper base case
❌ Python has a recursion limit (default: 1000 calls)

---

🔹 Changing Recursion Limit (optional)

import sys
sys.setrecursionlimit(2000)

---

⭐ When to Use Recursion?

Use recursion when the problem:

✔ can be defined in terms of smaller subproblems
✔ involves repeated substructure
✔ suits tree-like or mathematical patterns

Examples:

• Factorial
• Fibonacci
• Tree traversals
• Searching (DFS)
• Divide and conquer algorithms

---

📌 Exam-Ready Summary

• Recursion = function calling itself
• Two parts: Base Case + Recursive Case
• Uses call stack
• Good for mathematical & tree problems
• Needs stopping condition to avoid infinite loop
• Less efficient than loops but more elegant

---