Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. Here's an example of a recursive function in Python:
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
In this example, the `factorial()` function calculates the factorial of a given number `n` using recursion. The factorial of a non-negative integer `n` is the product of all positive integers less than or equal to `n`. The base case is when `n` is 0 or 1, where the factorial is defined as 1. Otherwise, the function calls itself with a smaller value `n - 1` and multiplies it by `n`.
Let's see how to use this function:
result = factorial(5)
print(result) # Output: 120
The `factorial(5)` call returns the factorial of 5, which is 120.
Recursion can be a powerful technique for solving problems that can be divided into smaller, similar subproblems. However, it's important to ensure that a proper base case is defined, so the recursive calls eventually reach a termination condition. Otherwise, it can lead to infinite recursion and stack overflow errors.
Here's another example of a recursive function that calculates the nth Fibonacci number:
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
The `fibonacci()` function calculates the nth Fibonacci number by summing the previous two Fibonacci numbers. The base case is when `n` is 0 or 1, where the function returns `n`. Otherwise, it calls itself recursively with `n - 1` and `n - 2` to calculate the two preceding Fibonacci numbers and adds them together.
Let's use the `fibonacci()` function:
result = fibonacci(6)
print(result) # Output: 8
The `fibonacci(6)` call returns the 6th Fibonacci number, which is 8.
Recursion can be a powerful tool in programming, but it's important to use it judiciously and ensure that the recursive calls converge towards the base case.
Comments