DSA technical paper on RECURSION #41 by priyamina.md

Recursion in Data Structures and Algorithms

1. What is Recursion?

Definition: Recursion is a programming concept where a function calls itself in its own definition. It is a powerful technique used in algorithms to break down a problem into smaller sub-problems of the same type.

Key Components:

• Base Condition: A recursive function must have a base condition to stop the recursion. It defines the simplest form of the problem that doesn't require further recursion.

• Stack Overflow: Without proper base conditions or termination criteria, recursion can lead to a stack overflow, causing the program to crash. It's essential to ensure that the recursion eventually reaches a base case.

• Recursion Tree: Visualizing recursive calls as a tree structure helps in understanding the flow of the recursive algorithm. Each node in the tree represents a recursive call.

2. Examples: Basic Recursion Problems

Example 1: Factorial Calculation

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

Example 2: Fibonacci Sequence

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

3. Backtracking

Definition: Backtracking is an algorithmic technique that uses recursion to systematically search for a solution to a problem. If the current solution is not viable, the algorithm backtracks to the previous step and explores other possibilities.

Example: N-Queens Problem

def is_safe(board, row, col, n):
    # Check if a queen can be placed in a given position
    # ...

def solve_n_queens(board, row, n):
    if row == n:
        # Base case: All queens are placed successfully
        # Process the solution or store it
    else:
        for col in range(n):
            if is_safe(board, row, col, n):
                # Place queen and move to the next row
                board[row][col] = 1
                solve_n_queens(board, row + 1, n)
                # Backtrack: Remove the queen if the current placement doesn't lead to a solution
                board[row][col] = 0

4. Types of Recursion: Parameterized and Functional Recursion

Parameterized Recursion

In parameterized recursion, the recursive function takes additional parameters that help in solving sub-problems.

Example: Binary Search

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

Functional Recursion

In functional recursion, the recursive function returns a modified version of itself.

Example: Reverse a List

def reverse_list(lst):
    if not lst:
        return []
    else:
        return reverse_list(lst[1:]) + [lst[0]]

5. Multiple Recursion Calls with Example

Definition: Multiple recursion calls occur when a recursive function makes more than one recursive call within its body.

Example: Merge Sort

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        merge(arr, left_half, right_half)

In conclusion, recursion is a fundamental concept in computer science and programming, providing an elegant way to solve complex problems by breaking them down into simpler sub-problems. Understanding recursion is crucial for mastering algorithms and data structures, and it opens the door to various problem-solving techniques such as backtracking.