Topic: Mastering Recursion — From Basics to Advanced Applications

---

What is Recursion?

• Recursion is a technique where a function calls itself to solve smaller instances of a problem until reaching a base case.

---

Basic Structure

• Every recursive function needs:

* A base case to stop recursion.

* A recursive case that breaks the problem into smaller parts.

---

Simple Example: Fibonacci Numbers

def fibonacci(n):
    if n <= 1:
        return n  # base case
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # recursive case

---

Drawbacks of Naive Recursion

• Repeated calculations cause exponential time complexity.

• Can cause stack overflow on large inputs.

---

Improving Recursion: Memoization

• Store results of subproblems to avoid repeated work.

memo = {}
def fib_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

---

Advanced Concepts

• Tail Recursion: Recursive call is the last operation. Python does not optimize tail calls but understanding it is important.

• Divide and Conquer Algorithms: Recursion breaks problems into subproblems (e.g., Merge Sort, Quick Sort).

---

Example: Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

---

Exercise

• Implement a recursive function to solve the Tower of Hanoi problem for *n* disks and print the moves.

---

#Algorithms #Recursion #Memoization #DivideAndConquer #CodingExercise

https://t.iss.one/DataScience4