Recursion in Python:-

Python Recursion — Complete Guide with Examples

Recursion is a programming technique where **a function calls itself** to solve smaller sub-problems of the original task. Every loop or repetitive task can also be rewritten using recursion.

Formal Definition: A function is considered recursive when it calls itself inside its own function body.

def xyz():
    xyz()   # recursive call

This creates an infinite recursion unless a base condition is used.

---

Why Recursion?

• To break complex problems into smaller subproblems
• Used in tree traversal, graphs, mathematics, searching, sorting, dynamic programming
• Makes code shorter and cleaner

But recursion must always include a BASE CONDITION:

if some_condition:
    return value

---

Example 1 — Simple Recursive Function

def xyz(num):
    print("number =", num)
    if num > 10:       # base condition
        return
    xyz(num + 1)       # recursive call

xyz(1)

This program will print numbers from 1 to 11.

---

Recursion Flow Diagram (Simplified)

xyz(1)
 └── xyz(2)
      └── xyz(3)
           └── ...
                └── xyz(11) → stops (base condition)

---

Example 2 — Sum of Numbers (1 to n) Using Recursion

def fun(num):
    if num == 0:          # base condition
        return 0
    else:
        return num + fun(num - 1)

x = fun(5)
print(x)

Output:

15

---

Deep Explanation — How Recursion Works Internally?

Whenever a recursive call is made, Python stores the current state in a stack (called the call stack).

For sum(5)

fun(5)
 → 5 + fun(4)
        → 4 + fun(3)
               → 3 + fun(2)
                      → 2 + fun(1)
                             → 1 + fun(0)
                                     → returns 0

Then Python begins returning values backward (unwinding phase):

fun(1) = 1 + 0 = 1  
fun(2) = 2 + 1 = 3  
fun(3) = 3 + 3 = 6  
fun(4) = 4 + 6 = 10  
fun(5) = 5 + 10 = 15

---

Advantages of Recursion

• Simplifies complex logic (tree, graphs, DFS, BFS)
• Code is shorter and cleaner
• Useful for mathematical formulas: factorial, Fibonacci, power, etc.

Disadvantages of Recursion

• Consumes more memory (stack frames)
• Slower than loops in many cases
• Can cause RecursionError if base condition missing or too deep

---

Most Common Use Cases of Recursion

• Factorial
• Fibonacci series
• Tree traversal (pre, post, in-order)
• Graph traversal (DFS)
• Searching and sorting (merge sort, quick sort)
• Mathematical sequences

---

Assignments with Extended Depth

1) WAP to calculate factorial using recursion

def fact(n):
    if n == 0 or n == 1:     # base condition
        return 1
    return n * fact(n - 1)

print(fact(5))

Flow:

fact(5)
 → 5 * fact(4)
 → 4 * fact(3)
 → 3 * fact(2)
 → 2 * fact(1)
 → returns 1

---

2) WAP to display Fibonacci series using recursion

Fibonacci series: 0, 1, 1, 2, 3, 5, 8, 13 ...

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

num = 10
for i in range(num):
    print(fib(i), end=" ")

Important Note:

Recursive Fibonacci has exponential time complexity O(2ⁿ). Better version uses memoization.

---

3) WAP to calculate sum of even and odd numbers from 1 to 50 using recursion

def sumEvenOdd(n, evenSum=0, oddSum=0):

    if n == 0:
        return evenSum, oddSum

    if n % 2 == 0:
        evenSum += n
    else:
        oddSum += n

    return sumEvenOdd(n-1, evenSum, oddSum)

even, odd = sumEvenOdd(50)
print("Even Sum =", even)
print("Odd Sum  =", odd)

Output:

Even Sum = 650
Odd Sum  = 625

---

Bonus Deep Explanation — When Should You Prefer Recursion?

Use Recursion When:

• The problem is naturally recursive (tree, graph, hierarchical data)
• Simplification is more important than performance
• You require clean and mathematical representation

Avoid Recursion When:

• Performance is critical
• The depth of recursion may cross Python's recursion limit
• A loop is simpler and faster

---

Conclusion

Recursion is a powerful concept that turns a complex problem into a set of smaller tasks. Understanding base conditions and stack behavior is essential for writing efficient recursive programs.