AI Hints
DSA in Python · Lesson 40 of 132

Recursion

A function that calls itself.

⏱ 2 min read▶ Video at 46:17🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Recursion is when a function solves a problem by calling itself, on a smaller version of the same problem. Like Russian dolls. To open them all, you open one doll, and then do the same thing with the smaller doll inside, until you reach the tiniest one.

Recursion
From the video: Recursion
  • A function that calls itself
  • A smaller version each time
  • Like Russian dolls

Counting down

This function prints a number, then calls itself with the number minus one. The if at the top is the base case. When N reaches zero, it stops calling itself, and says lift off. Without a base case, it would never stop. Run it.

countdown.pypython
def countdown(n):
    if n == 0:
        print("Lift off!")
        return
    print(n)
    countdown(n - 1)

countdown(3)
Output
3
2
1
Lift off!

Factorial

Factorial of five means five times four times three times two times one. Notice that factorial of five is just five times factorial of four. That's a smaller version of the same problem, which makes it perfect for recursion. The base case is one. Run it.

factorial.pypython
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5))
print(factorial(10))
Output
120
3628800

Summary

A recursive function calls itself on a smaller problem, and a base case stops it. Next, what Python is doing behind the scenes, on the call stack.

Key takeaways
  • Call yourself, smaller
  • A base case stops it
  • factorial(n) = n × factorial(n−1)
Next up: The Call Stack — how Python keeps track