Recursion - Level 2

Lecture 92:- Recursion - Level 2

At Level 2 of understanding recursion, let's dive deeper into recursion and explore more complex concepts and techniques:

Multiple Recursive Calls: In some recursive functions, you may need to make multiple recursive calls within the same function. This can lead to different types of recursion, such as binary recursion or n-ary recursion.

Example - Binary Recursion:

In this example, the binary_sum function recursively calculates the sum of elements in a list using binary recursion. It divides the list into two halves and recursively calculates the sum of each half.

Mutual Recursion: Mutual recursion occurs when two or more functions call each other in a circular manner.

Example:

In this example, the is_even and is_odd functions mutually call each other to determine if a number is even or odd.

Memoization: Memoization is a technique to optimize recursive functions by storing the results of expensive function calls and returning the cached result when the same inputs occur again. This can significantly improve the performance of recursive functions, especially those with overlapping subproblems.

Example:

Divide and Conquer: Divide and Conquer is a problem-solving technique where a problem is divided into smaller subproblems, solved independently, and then combined to obtain the final solution. Recursive functions often follow the divide and conquer paradigm.

Example:

In this example, merge_sort uses the divide and conquer approach to sort an array using the merge sort algorithm.

Backtracking: Backtracking is a general algorithm for finding all (or some) solutions to a problem by incrementally building a solution and abandoning it when it is determined not to be viable.

Example:

In this example, the find_subsets_with_sum function uses backtracking to find all subsets of an array with a given sum.

Recursion is a powerful technique that can lead to elegant and concise solutions for complex problems. However, it requires careful consideration of base cases, termination conditions, and the potential for stack overflow in deep recursion. Memoization and other optimization techniques can improve the efficiency of recursive algorithms. Practice implementing various recursive algorithms to solidify your understanding and problem-solving skills.

pythonCopy code

def subset_sum(arr, target, current_sum, start, path, result):    if current_sum == target:        result.append(path[:])        return    for i in range(start, len(arr)):        if current_sum + arr[i] <= target:            path.append(arr[i])            subset_sum(arr, target, current_sum + arr[i], i + 1, path, result)            path.pop() def find_subsets_with_sum(arr, target):    result = []    subset_sum(arr, target, 0, 0, [], result)    return result

pythonCopy code

def merge_sort(arr):    if len(arr) <= 1:        return arr    mid = len(arr) // 2    left_half = merge_sort(arr[:mid])    right_half = merge_sort(arr[mid:])    return merge(left_half, right_half) def merge(left, right):    result = []    i, j = 0, 0    while i < len(left) and j < len(right):        if left[i] < right[j]:            result.append(left[i])            i += 1        else:            result.append(right[j])            j += 1    result.extend(left[i:])    result.extend(right[j:])    return result

pythonCopy code

# Using memoization to optimize Fibonacci calculation memo = {} def fibonacci(n):    if n in memo:        return memo[n]    if n <= 1:        return n    else:        result = fibonacci(n - 1) + fibonacci(n - 2)        memo[n] = result        return result

pythonCopy code

def is_even(n):    if n == 0:        return True    else:        return is_odd(n - 1) def is_odd(n):    if n == 0:        return False    else:        return is_even(n - 1)

pythonCopy code

def binary_sum(arr, left, right):    if left == right:        return arr[left]    else:        mid = (left + right) // 2        return binary_sum(arr, left, mid) + binary_sum(arr, mid + 1, right)