Recursion is a technique in which a function calls itself during its execution. It allows complex problems to be solved by breaking them down into smaller, more manageable subproblems. Recursion can be a powerful tool for solving problems that exhibit a recursive structure.
Base Case and Recursive CaseIn a recursive function, two main components are present: the base case and the recursive case. The base case defines the terminating condition that stops the recursion, preventing infinite function calls. The recursive case defines the logic that breaks the problem into smaller subproblems and calls the function recursively to solve them.
Example: Factorial CalculationThe factorial of a non-negative integer n is the product of all positive integers less than or equal to n. Let's implement a recursive function to calculate the factorial of a number.
Syntax
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
num = 5
print("Factorial of", num, "is", factorial(num))
Output
Factorial of 5 is 120
Example: Fibonacci Series
The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones. Let's implement a recursive function to generate the Fibonacci series.
Syntax
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
num_terms = 10
print("Fibonacci series:")
for i in range(num_terms):
print(fibonacci(i), end=" ")
Output
Fibonacci series:
0 1 1 2 3 5 8 13 21 34
Example: Binary Search
Binary search is a commonly used searching algorithm that efficiently finds a target value in a sorted array. Let's implement a recursive binary search function.
Syntax
def binary_search(arr, target, low, high):
if low > high:
return -1
else:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target_number = 7
result = binary_search(numbers, target_number, 0, len(numbers) - 1)
if result != -1:
print("Element found at index", result)
else:
print("Element not found")
Output
Element found at index 6
Advantages and Considerations