Common Recursive Algorithms

In computer science, recursion is a powerful technique used to solve problems by breaking them down into smaller, more manageable subproblems. Let's explore some commonly used recursive algorithms and understand how they work.

1. Factorial

Factorial is a mathematical function defined as the product of an integer and all the integers below it. It is denoted by the exclamation mark (!). The factorial of a non-negative integer n is written as n! and is calculated as:

n! = n * (n-1) * (n-2) * ... * 2 * 1

Let's see an example of calculating the factorial of a number using recursive algorithm:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

result = factorial(5)
print(result)  # Output: 120

In the above code, the factorial function takes an integer n as input. If n is 0, it returns 1 as the base case. Otherwise, it recursively calls itself with n-1 as the argument, until it reaches the base case.

2. Fibonacci Series

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones. The series starts with 0 and 1. So, the Fibonacci series looks like: 0, 1, 1, 2, 3, 5, 8, 13, ...

Let's see an example of generating the Fibonacci series using a recursive algorithm:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

result = fibonacci(6)
print(result)  # Output: 8

In the above code, the fibonacci function takes an integer n as input. If n is less than or equal to 1, it returns n as the base case. Otherwise, it recursively calls itself with n-1 and n-2 as the arguments, until it reaches the base case.

3. Binary Search

Binary search is an algorithm used to search for a specific element in a sorted list or array. It follows the divide and conquer paradigm by repeatedly dividing the search space in half and discarding the half that is not needed.

Let's see an example of implementing binary search using a recursive algorithm:

def binary_search(arr, low, high, target):
    if high >= low:
        mid = low + (high - low) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binary_search(arr, low, mid-1, target)
        else:
            return binary_search(arr, mid+1, high, target)
    else:
        return -1

arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
result = binary_search(arr, 0, len(arr)-1, target)
print(result)  # Output: 5

In the above code, the binary_search function takes a sorted array arr, the lowest index low, the highest index high, and the target element to be searched. If the high index is greater than or equal to the low index, the function calculates the mid index and compares the target with the element at the mid index. Based on the comparison, it recursively calls itself on the appropriate half of the array until it finds the target or determines that it does not exist.

These are just a few examples of commonly used recursive algorithms. Recursion provides an elegant and intuitive way to solve problems, especially those involving repetitive or hierarchical structures. By understanding the basic principles and techniques, you can tackle a wide range of problems using recursion.