Practical 10: Recursions and Backtracking Algorithms Exercises

Objective

In this lab, you will implement backtracking and recursion exercises. This exercise will help you understand the mechanics of these algorithms and compare their performance.

Submission Date: November 4st

Prerequisites

Basic knowledge of Python syntax
Understanding of lists and functions in Python
Familiarity with time complexity concepts (optional, but helpful)

Part 1: Factorial

Let's create a recursive function to generate factorial solution:

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

# Test the function
n=3
print("The factorial of", num, "is", factorial(num))

Part 2: Fibonacci Generator

Step 1: Implement a Recursive Fibonacci Generator

Let's create a recursive function to generate Fibonacci numbers:

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

# Test the function
for i in range(10):
    print(f"F({i}) = {fibonacci_recursive(i)}")

Step 2: Implement an Iterative Fibonacci Generator

Now, let's create an iterative function to generate Fibonacci numbers:

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Test the function
for i in range(10):
    print(f"F({i}) = {fibonacci_iterative(i)}")

Step 3: Compare Performance

Let's create a function to measure the execution time of both approaches:

import time

def measure_time(func, n):
    start = time.time()
    result = func(n)
    end = time.time()
    return result, end - start

# Test both functions and compare their execution times
n = 30
recursive_result, recursive_time = measure_time(fibonacci_recursive, n)
iterative_result, iterative_time = measure_time(fibonacci_iterative, n)

print(f"Recursive: F({n}) = {recursive_result}, Time: {recursive_time:.6f} seconds")
print(f"Iterative: F({n}) = {iterative_result}, Time: {iterative_time:.6f} seconds")

Step 4: Implement a Generator Function for Fibonacci Sequence

Now, let's create a generator function that yields Fibonacci numbers:

def fibonacci_generator(limit):
    a, b = 0, 1
    count = 0
    while count < limit:
        yield a
        a, b = b, a + b
        count += 1

# Test the generator
for i, fib in enumerate(fibonacci_generator(10)):
    print(f"F({i}) = {fib}")

Step 5: Implement Memoization for Recursive Fibonacci

To improve the performance of the recursive approach, let's implement memoization:

def fibonacci_memoized(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memoized(n-1, memo) + fibonacci_memoized(n-2, memo)
    return memo[n]

# Test the memoized function
for i in range(10):
    print(f"F({i}) = {fibonacci_memoized(i)}")

# Compare performance with the original recursive function
n = 30
memoized_result, memoized_time = measure_time(fibonacci_memoized, n)
print(f"Memoized: F({n}) = {memoized_result}, Time: {memoized_time:.6f} seconds")

Part 3 Problem: Climbing Stairs

1. Problem Statement

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

1 step + 1 step
2 steps

Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Constraints:

1 <= n <= 45

2. Conceptual Understanding

This problem is about finding the number of different combinations to reach a goal (the top of the stairs) given a set of fixed moves (1 or 2 steps at a time).

Think of it like this: You're standing at the bottom of a staircase, and for each step, you have two choices: take 1 step or take 2 steps. We need to count all the possible sequences of these choices that lead to the top.

This problem introduces the concept of dynamic programming, where we build the solution to a larger problem from solutions to smaller subproblems.

We'll use the Dynamic Programming approach:

Create an array dp where dp[i] represents the number of ways to climb to the i-th step.
Initialize the base cases: dp[1] = 1 (one way to climb 1 step) and dp[2] = 2 (two ways to climb 2 steps).
For steps 3 to n, the number of ways to reach step i is the sum of ways to reach the previous step (and then take 1 step) and the ways to reach two steps back (and then take 2 steps). So, dp[i] = dp[i-1] + dp[i-2]
Return dp[n] as the final answer.

This approach is optimal because it solves each subproblem only once and uses the results to build up to the final solution.

3. Python Implementation

Recursive Method

def climbStairs(n):
    def climb(n):
        if n==1: #only one step option is available
            return 1
        if n ==2: # two options are possible: to take two 1-steps or to only take one 2-steps
            return 2
        return climb(n-1) + climb(n-2)
    return climb(n)

Dynamic Programming Method

def climbStairs(n):
    if n <= 2:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

We use a list dp to store the number of ways for each step.
We initialize the base cases for 1 and 2 steps.
We then iterate from 3 to n, filling in the dp array.
The final answer is in dp[n].

Part 4: Tower of Hanoi

1. Problem Statement

The Tower of Hanoi is a classic problem in computer science and mathematics. The problem setup is as follows:

There are three rods and a number of disks of different sizes which can slide onto any rod.
The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest disk at the top.
The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:
1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No larger disk may be placed on top of a smaller disk.

Your task is to write a function that prints out the series of moves required to solve the Tower of Hanoi puzzle for n disks.

Example: Input: n = 3 (number of disks) Output:

Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

2. Conceptual Understanding

The Tower of Hanoi problem is an excellent example of a problem that can be solved using recursion. The key insight is that to move n disks:

Move n-1 disks from the source to the auxiliary rod.
Move the largest disk from the source to the destination rod.
Move the n-1 disks from the auxiliary rod to the destination rod.

This process is recursive because moving n-1 disks involves the same process with a smaller number of disks.

Think of it like unpacking nested boxes. You need to unpack the smaller boxes (move smaller disks) before you can move the largest box (disk).

The recursive solution follows these steps:

Base case: If there's only one disk, move it directly from the source to the destination.
Recursive case: a. Move n-1 disks from source to auxiliary rod. b. Move the nth disk from source to destination. c. Move n-1 disks from auxiliary to destination.

This approach elegantly solves the problem by breaking it down into smaller, manageable subproblems.

3. Python Implementation

def tower_of_hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1 from rod {source} to rod {destination}")
        return
    tower_of_hanoi(n-1, source, auxiliary, destination)
    print(f"Move disk {n} from rod {source} to rod {destination}")
    tower_of_hanoi(n-1, auxiliary, destination, source)

# Example usage
n = 3
tower_of_hanoi(n, 'A', 'C', 'B')

Backtracking Algorithms

Part 5: Combination Sum

1. Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

Explanation:

2 and 3 are candidates, and 2 + 2 + 3 = 7.

Note that 2 can be used multiple times.

7 is a candidate, and 7 = 7.

These are the only two combinations.

2. Python Implementation

class Solution(object):
    def combinationSum(self, candidates, target):
        def backtrack(start, target, path):
            if target == 0:
                result.append(path)
                return
            if target < 0:
                return
            for i in range(start, len(candidates)):
                backtrack(i, target - candidates[i], path + [candidates[i]])
        result = []
        candidates.sort()
        backtrack(0, target, [])
        return result

Part 6: Word Search

1. Problem Statement

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED”

Output: true

2. Conceptual Understanding

Implement a recursive function backtrack that takes the current position (i, j) in the grid and the current index k of the word.

Base cases:

If k equals the length of the word, return True, indicating that the word has been found.
If the current position (i, j) is out of the grid boundaries or the character at (i, j) does not match the character at index k of the word, return False.
Mark the current cell as visited by changing its value or marking it as empty.
Recursively explore all four directions (up, down, left, right) by calling backtrack with updated positions (i+1, j), (i-1, j), (i, j+1), and (i, j-1).
If any recursive call returns True, indicating that the word has been found, return True.
If none of the recursive calls returns True, reset the current cell to its original value and return False.
Iterate through all cells in the grid and call the backtrack function for each cell. If any call returns True, return True, indicating that the word exists in the grid. Otherwise, return False.

3. Python Implementation

class Solution(object):
    def exist(self, board, word):
        def backtrack(i, j, k):
            if k == len(word):
                return True
            if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[k]:
                return False
            temp = board[i][j]
            board[i][j] = '' 
            if backtrack(i+1, j, k+1) or backtrack(i-1, j, k+1) or backtrack(i, j+1, k+1) or backtrack(i, j-1, k+1):
                return True
            board[i][j] = temp
            return False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if backtrack(i, j, 0):
                    return True
        return False

Part 7: Permutations

1. Problem Statement

Given an array nums of distinct integers, return all the possible . You can return the answer in any order.

Example:

Input: nums = [1,2,3]

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Input: nums = [0,1]

Output: [[0,1],[1,0]]

Input: nums = [1]

Output: [[1]]

2. Conceptual Understanding

3. Python Implementation

Solution 1:

from itertools import permutations
class Solution(object):
    def permute(self, nums):
        return list(permutations(nums))

Solution 2:

class Solution(object):
    def permute(self, nums):
        def recursive(nums, perm=[], res=[]):  # helper
            if not nums:
                res.append(perm[::])
            for i in range(len(nums)): # [1,2,3]
                newNums = nums[:i] + nums[i+1:]
                perm.append(nums[i])
                recursive(newNums, perm, res) # - recursive call will reach the leaf
                perm.pop() 
            return res
        return recursive(nums)

The function takes four parameters: the number of disks n, and the names of the source, destination, and auxiliary rods.
The base case (n == 1) simply moves the disk and returns.
For n > 1, we recursively move n-1 disks, then move the nth disk, then recursively move the n-1 disks again.

Further Exercises for Students

Modify the iterative function to return a list of Fibonacci numbers up to n, instead of just the nth number.
Implement a function that finds the index of the first Fibonacci number that exceeds a given value.
Create a function that determines if a given number is a Fibonacci number.
Implement a function that calculates the ratio between consecutive Fibonacci numbers and observe how it approaches the golden ratio.

Discussion Questions

What are the advantages and disadvantages of the recursive approach compared to the iterative approach?
How does memoization improve the performance of the recursive function? Are there any drawbacks?
In what scenarios might you prefer to use a generator function over other implementations?
How does the space complexity differ between these implementations?

Conclusion

In this lab, you've implemented multiple approaches to generate Fibonacci sequences in Python. You've explored recursive, iterative, and generator-based solutions, as well as an optimization technique (memoization). By comparing these approaches, you can gain insights into algorithm design, performance optimization, and the trade-offs between different implementation strategies.