Recursion is a programming technique in which a function calls itself to solve a problem. A recursive function keeps calling itself until a base condition is reached.
Recursion means that a function calls itself from inside its own definition.
Basic structure:
def function():
function()However, the function must have a condition to stop calling itself.
def message(n):
if n == 0:
return
print("Hello")
message(n - 1)
message(3)
The function calls itself with a smaller value each time.
When n becomes 0, the function stops.
The base case is the condition that stops a recursive function.
def count(n):
if n == 0:
return
print(n)
count(n - 1)
count(5)
Here, if n == 0: is the base case.
The recursive case is the part of the function where the function calls itself.
def count(n):
if n == 0:
return
print(n)
# Recursive case
count(n - 1)
The statement count(n - 1) is the recursive case.
def countdown(n):
if n == 0:
print("Done")
return
print(n)
countdown(n - 1)
countdown(5)The factorial of a number is the product of all positive integers from that number down to 1.
For example:
Python example:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(5))When we call:
factorial(5)Python evaluates it like this:
The final result is 120.
def total(n):
if n == 0:
return 0
return n + total(n - 1)
print(total(5))The calculation is: 5 + 4 + 3 + 2 + 1 = 15.
The Fibonacci sequence starts with 0 and 1. Each following number is the sum of the previous two numbers.
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6))def fibonacci(a, b, count):
if count == 0:
return
print(a)
fibonacci(b, a + b, count - 1)
fibonacci(0, 1, 7)def reverse(text):
if text == "":
return text
return reverse(text[1:]) + text[0]
print(reverse("Python"))def power(base, exponent):
if exponent == 0:
return 1
return base * power(base, exponent - 1)
print(power(2, 5))This calculates 2⁵ = 32.
def print_list(items, index):
if index == len(items):
return
print(items[index])
print_list(items, index + 1)
numbers = [10, 20, 30, 40]
print_list(numbers, 0)A recursive function can have more than one parameter.
def display(start, end):
if start > end:
return
print(start)
display(start + 1, end)
display(1, 5)When a recursive function calls itself, Python keeps track of each function call using the call stack.
Each new call is placed on the stack. When the base case is reached, the calls return one by one.
def count(n):
if n == 0:
return
print(n)
count(n - 1)
count(3)The calls are approximately:
If a recursive function never reaches a stopping condition, it continues calling itself.
def example():
example()
example()This causes Python to eventually raise a RecursionError.
Python limits how deeply ordinary recursive calls can continue.
If that limit is exceeded, Python raises RecursionError.
def test():
test()
test()Using a loop:
for i in range(1, 6):
print(i)Using recursion:
def display(i):
if i > 5:
return
print(i)
display(i + 1)
display(1)Both can produce the same output, but they use different approaches. Loops are often simpler for straightforward repetition, while recursion can be useful for problems that naturally break into smaller versions of the same problem.
RecursionError.| Term | Meaning |
|---|---|
| Recursion | A function calling itself. |
| Base Case | The condition that stops recursion. |
| Recursive Case | The part that calls the function again. |
| Call Stack | Memory structure used to keep track of active function calls. |
| RecursionError | Error raised when recursive calls become too deep. |
RecursionError.Question: What is the purpose of a base case in recursion?