Recursion in Python

Recursion is a programming technique in which a function calls itself. A recursive function solves a problem by dividing it into smaller problems and solving them.

1. What is Recursion?

When a function calls itself from within its own definition, this technique is called recursion.

def hello():
    print("Hello")
    hello()

2. Basic Recursive Function

def count_down(number):

    if number == 0:
        return

    print(number)

    count_down(number - 1)


count_down(5)

Output:

5
4
3
2
1

3. What is a Base Case?

A base case is the condition where recursion stops.

def count_down(number):

    if number == 0:
        return

    print(number)

    count_down(number - 1)

Here:

if number == 0:
    return

is the base case. When number == 0, the function does not make any further call.

4. Recursive Case

The recursive case is the part where the function calls itself again.

def count_down(number):

    if number == 0:
        return

    print(number)

    count_down(number - 1)

Here:

count_down(number - 1)

is the recursive call.

5. Recursion Execution Flow

6. Factorial Using Recursion

Factorial is a very common example of recursion.

Example:

5! = 5 × 4 × 3 × 2 × 1
   = 120

Recursive solution:

def factorial(number):

    if number == 0:
        return 1

    return number * factorial(number - 1)


result = factorial(5)

print(result)

Output:

120

7. Factorial Execution

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

8. Sum of Numbers Using Recursion

def sum_numbers(number):

    if number == 0:
        return 0

    return number + sum_numbers(number - 1)


result = sum_numbers(5)

print(result)

Output:

15

Calculation:

5 + 4 + 3 + 2 + 1 = 15

9. Power Using Recursion

def power(base, exponent):

    if exponent == 0:
        return 1

    return base * power(base, exponent - 1)


result = power(2, 4)

print(result)

Output:

16

10. Fibonacci Using Recursion

In the Fibonacci sequence, the next number is the sum of the the previous two numbers.

0, 1, 1, 2, 3, 5, 8, 13...

def fibonacci(number):

    if number <= 1:
        return number

    return fibonacci(number - 1) + fibonacci(number - 2)


for i in range(8):
    print(fibonacci(i))

Output:

0
1
1
2
3
5
8
13

11. Recursion with String

Recursion can also be used to reverse a string.

def reverse_string(text):

    if text == "":
        return ""

    return reverse_string(text[1:]) + text[0]


result = reverse_string("CIIT")

print(result)

Output:

TIIC

12. Count Characters Using Recursion

def count_characters(text):

    if text == "":
        return 0

    return 1 + count_characters(text[1:])


result = count_characters("Python")

print(result)

Output:

6

13. Recursion with List

def print_items(items, index=0):

    if index == len(items):
        return

    print(items[index])

    print_items(items, index + 1)


courses = [
    "Python",
    ".NET",
    "Java"
]

print_items(courses)

Output:

Python
.NET
Java

14. CIIT Example 🤓👀

Suppose CIIT has multiple course levels and we need to display them recursively.

def show_courses(courses, index=0):

    if index == len(courses):
        return

    print("Course:", courses[index])

    show_courses(courses, index + 1)


courses = [
    "Python Full Stack",
    ".NET Full Stack",
    "Java Full Stack",
    "Data Science"
]

show_courses(courses)

Output:

Course: Python Full Stack
Course: .NET Full Stack
Course: Java Full Stack
Course: Data Science

15. Recursion vs Loop

16. Recursion and Call Stack

Each recursive function call creates a new function call frame in memory. This process is managed through the call stack.

factorial(3)

factorial(3)
    ↓
factorial(2)
    ↓
factorial(1)
    ↓
factorial(0)

Base Case

Then results return back:
1
2
6

17. Common Mistakes

Mistake 1: Base Case Missing

def test(number):

    print(number)

    test(number - 1)

This function does not have a stopping condition.

Mistake 2: Wrong Base Case

def count_down(number):

    if number == 10:
        return

    count_down(number - 1)

If the starting value is 5, the function can never reach 10.

18. When to Use Recursion?

• When working with tree structures.
• In problems such as graph traversal.
• In divide-and-conquer algorithms.
• In mathematical problems such as factorial and Fibonacci.
• When processing nested structures.

19. Interview Points

• What is recursion?
• What is a recursive function?
• What is a base case?
• What is a recursive case?
• What is the difference between recursion and a loop?
• When can a RecursionError occur in recursion?
• How can factorial be calculated using recursion?
• How can the Fibonacci sequence be generated using recursion?