Data Structures & Algorithms – Recursion

Recursion is a technique in computer science where a function calls itself in order to solve a problem. A function that uses recursion is called a recursive function. Recursive functions are used to solve problems that can be broken down into smaller, identical sub-problems. Recursive functions are a powerful tool for solving problems, but they can also be difficult to understand and implement correctly.

A classic example of a problem that is solved using recursion is the factorial function. The factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n. The mathematical definition of factorial can be expressed recursively as:

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

Here is an example of a recursive implementation of factorial in Python:

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

print(factorial(5)) #120

In this example, the factorial() function calls itself until the base case of n==1 is reached. The base case is the stopping condition for the recursion and it’s very important to have a base case to avoid infinite recursion.

Another classic example of a problem that is solved using recursion is the problem of finding the n-th Fibonacci number. The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The mathematical definition of Fibonacci numbers can be expressed recursively as:

F(n) = F(n-1) + F(n-2) where F(0) = 0 and F(1) = 1.

Here is an example of a recursive implementation of Fibonacci numbers in Python:

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

print(fibonacci(5)) #5

In this example, the fibonacci() function calls itself twice recursively until the base cases n==0 or n==1 are reached.

Recursion can also be used to solve problems that involve traversing a data structure like a tree or a graph. One common example is traversing a binary tree in pre-order, in-order, or post-order.

Here is an example of a recursive implementation of pre-order traversal of a binary tree in Python:

class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data

def preorder_traversal(root):
    if root:
        print(root.data)
        preorder_traversal(root.left)
        preorder_traversal(root.right)

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
preorder_traversal(root) #1 2 4 5 3

It’s worth noting that recursion can be memory-intensive since each

call to the recursive function adds a new frame to the call stack, and if the recursion is not done correctly, it can lead to a stack overflow error. Therefore, it’s important to have a clear understanding of the problem and the base case that will stop the recursion, and also to design the recursive function in a way that it reduces the problem size on each recursive call.

Another common technique to optimize the recursive function is using memoization, which is a technique of storing the results of expensive function calls and returning the cached result when the same inputs occur again. This technique is often used to avoid redundant calculation and is especially useful in recursive functions that have overlapping sub-problems.

In summary, recursion is a technique in computer science where a function calls itself in order to solve a problem. Recursive functions are used to solve problems that can be broken down into smaller, identical sub-problems. Some common examples of problems that are solved using recursion are the factorial function, the Fibonacci numbers, and traversing a data structure like a tree or a graph. It’s important to have a clear understanding of the problem and the base case that will stop the recursion and also to optimize the recursive function using techniques like memoization to avoid stack overflow errors and redundant calculations.