Introduction
A recursive function is a function that calls itself in order to solve a problem. Recursion is useful for solving problems that can be broken down into smaller, similar problems. Recursive functions need a base case to terminate the recursion and prevent infinite loops.
How Recursion Works
- Base Case: The condition that stops the recursion.
- Recursive Case: The part of the function that calls itself with modified arguments.
Example: Factorial Function
The factorial of a number n (denoted as n!) is the product of all positive integers less than or equal to n. The factorial of 0 is defined as 1.
Iterative Approach
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
print(factorial_iterative(5)) # Output: 120
Recursive Approach
def factorial_recursive(n):
if n == 1:
return 1
else:
return n * factorial_recursive(n - 1)
print(factorial_recursive(5)) # Output: 120
Example: Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.
Iterative Approach
def fibonacci_iterative(n):
sequence = [0, 1]
while len(sequence) < n:
sequence.append(sequence[-1] + sequence[-2])
return sequence
print(fibonacci_iterative(10)) # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Recursive Approach
def fibonacci_recursive(n):
if n <= 1:
return n
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
# Print the first 10 Fibonacci numbers
fib_sequence = [fibonacci_recursive(i) for i in range(10)]
print(fib_sequence) # Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Example: Sum of a List
Iterative Approach
def sum_list_iterative(numbers):
total = 0
for num in numbers:
total += num
return total
print(sum_list_iterative([1, 2, 3, 4, 5])) # Output: 15
Recursive Approach
def sum_list_recursive(numbers):
if len(numbers) == 0:
return 0
else:
return numbers[0] + sum_list_recursive(numbers[1:])
print(sum_list_recursive([1, 2, 3, 4, 5])) # Output: 15
Example: Reverse a String
Iterative Approach
def reverse_string_iterative(s):
reversed_str = ""
for char in s:
reversed_str = char + reversed_str
return reversed_str
print(reverse_string_iterative("hello")) # Output: "olleh"
Recursive Approach
def reverse_string_recursive(s):
if len(s) == 0:
return s
else:
return s[-1] + reverse_string_recursive(s[:-1])
print(reverse_string_recursive("hello")) # Output: "olleh"
Example: Checking for Palindrome
A palindrome is a string that reads the same forward and backward.
Iterative Approach
def is_palindrome_iterative(s):
return s == s[::-1]
print(is_palindrome_iterative("radar")) # Output: True
print(is_palindrome_iterative("hello")) # Output: False
Recursive Approach
def is_palindrome_recursive(s):
if len(s) <= 1:
return True
else:
return s[0] == s[-1] and is_palindrome_recursive(s[1:-1])
print(is_palindrome_recursive("radar")) # Output: True
print(is_palindrome_recursive("hello")) # Output: False
Conclusion
Recursive functions are used for solving problems that can be broken down into smaller, similar problems. By understanding how to implement recursive functions with base cases and recursive cases, you can solve complex problems in a more straightforward manner. The provided examples demonstrate practical applications of recursion in various contexts.