Recursion - Level 3

Lecture 93:- Recursion - Level 3

At Level 3 of understanding recursion, let's explore more advanced topics and challenging problems involving recursion:

Tail Recursion Optimization: Some programming languages and compilers optimize tail-recursive functions, which means that the recursive call is the last operation in the function. In such cases, the compiler can convert the recursive call into an iterative loop, saving space on the call stack.

Example:

In this example, the factorial_tail_recursive function is tail-recursive, and certain compilers can optimize it into an iterative loop.

Recursive Data Structures: Recursive data structures are data structures that can contain references to instances of the same data structure type. Trees and linked lists are common examples of recursive data structures.

Example:

In this example, the TreeNode class is a recursive data structure because each TreeNode object can have references to other TreeNode objects.

Dynamic Programming using Recursion: Recursion and dynamic programming often go hand in hand. Dynamic programming is a technique to optimize recursive algorithms by storing and reusing intermediate results in a table.

Example - Fibonacci using Dynamic Programming (Memoization):

Recursive Backtracking: Recursive backtracking is a powerful technique used to solve problems with a constraint that can be satisfied incrementally. It explores all possible solutions and abandons those that violate the constraints.

Example:

In this example, the sudoku_solver function uses recursive backtracking to solve a Sudoku puzzle.

Mutually Recursive Data Structures: Similar to mutually recursive functions, data structures can also be mutually recursive, where two or more data structures have references to each other.

Example:

In this example, the TreeNode class has a list of child nodes, and the Tree class has a reference to the root node, creating a mutually recursive relationship.

Recursion at Level 3 involves more complex concepts, like dynamic programming, tail recursion optimization, and recursive backtracking. Recursive solutions can be elegant and powerful, but they require a deep understanding of the problem and careful handling of base cases and recursive calls. With practice, you'll be able to leverage recursion effectively in a wide range of scenarios.

pythonCopy code

class TreeNode:    def __init__(self, val=0):        self.val = val        self.children = [] class Tree:    def __init__(self):        self.root = None

pythonCopy code

def sudoku_solver(board):    empty_cell = find_empty_cell(board)    if not empty_cell:        return True    row, col = empty_cell    for num in range(1, 10):        if is_valid_move(board, row, col, num):            board[row][col] = num            if sudoku_solver(board):                return True            board[row][col] = 0   # Backtrack if the current move doesn't lead to a solution    return False def find_empty_cell(board):    for i in range(9):        for j in range(9):            if board[i][j] == 0:                return (i, j)    return None def is_valid_move(board, row, col, num):    # Check if 'num' is valid in the given row, column, and 3x3 grid    # ... # Usage: # board = 9x9 2D list representing the Sudoku puzzle # sudoku_solver(board)

pythonCopy code

memo = {} def fibonacci_memoization(n):    if n in memo:        return memo[n]    if n <= 1:        return n    else:        result = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2)        memo[n] = result        return result

pythonCopy code

class TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right

pythonCopy code

def factorial_tail_recursive(n, result=1):    if n == 0:        return result    else:        return factorial_tail_recursive(n - 1, result * n)