[go: up one dir, main page]
Scribd
Upload
6 views11 pages

Untitled Document

Uploaded by

kylemessi001
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views11 pages

Untitled Document

Uploaded by

kylemessi001
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Solutions for Recursion Exercises

Beginner-Level Solutions

Factorial Calculation

def factorial(n):

if n == 0 or n == 1: # Base case

return 1

else: # Recursive step

return n * factorial(n - 1)

print(factorial(5)) # Output: 120

Sum of Digits

def sum_digits(n):

if n == 0: # Base case

return 0

else: # Recursive step

return n % 10 + sum_digits(n // 10)


print(sum_digits(123)) # Output: 6

Count Down

def count_down(n):

if n <= 0: # Base case

return

else: # Recursive step

print(n)

count_down(n - 1)

count_down(5) # Output: 5, 4, 3, 2, 1

Power Calculation

def power(base, exponent):

if exponent == 0: # Base case

return 1

else: # Recursive step

return base * power(base, exponent - 1)


print(power(2, 4)) # Output: 16

Check Palindrome

def is_palindrome(s):

if len(s) <= 1: # Base case

return True

else: # Recursive step

return s[0] == s[-1] and is_palindrome(s[1:-1])

print(is_palindrome("radar")) # Output: True

Intermediate-Level Solutions

Fibonacci Sequence

def fibonacci(n):

if n == 0 or n == 1: # Base cases

return n

else: # Recursive step

return fibonacci(n - 1) + fibonacci(n - 2)


print(fibonacci(6)) # Output: 8

Greatest Common Divisor (GCD)

def gcd(a, b):

if b == 0: # Base case

return a

else: # Recursive step

return gcd(b, a % b)

print(gcd(48, 18)) # Output: 6

Reverse a String
def reverse(s):

if len(s) == 0: # Base case

return s

else: # Recursive step

return s[-1] + reverse(s[:-1])


print(reverse("hello")) # Output: "olleh"

Binary Search

def binary_search(arr, target, low, high):

if low > high: # Base case: target not found

return -1

mid = (low + high) // 2

if arr[mid] == target: # Base case: target found

return mid

elif arr[mid] > target: # Search in the left half

return binary_search(arr, target, low, mid - 1)

else: # Search in the right half

return binary_search(arr, target, mid + 1,


high)

arr = [1, 2, 3, 4, 5, 6]

print(binary_search(arr, 4, 0, len(arr) - 1)) #


Output: 3
Tower of Hanoi

def tower_of_hanoi(n, source, target, auxiliary):

if n == 1: # Base case

print(f"Move disk 1 from {source} to {target}")

return

tower_of_hanoi(n - 1, source, auxiliary, target)

print(f"Move disk {n} from {source} to {target}")

tower_of_hanoi(n - 1, auxiliary, target, source)

tower_of_hanoi(3, "A", "C", "B")

# Output:

# Move disk 1 from A to C

# Move disk 2 from A to B

# Move disk 1 from C to B

# Move disk 3 from A to C

# Move disk 1 from B to A

# Move disk 2 from B to C

# Move disk 1 from A to C


Advanced-Level Solutions

Permutations of a String

def permutations(s, step=0):

if step == len(s): # Base case

print("".join(s))

for i in range(step, len(s)):

s_copy = [c for c in s]

s_copy[step], s_copy[i] = s_copy[i],


s_copy[step]

permutations(s_copy, step + 1)

permutations(list("abc"))

# Output: All permutations of "abc"

11.

Recursive Sum

def recursive_sum(lst):

if len(lst) == 0: # Base case


return 0

else: # Recursive step

return lst[0] + recursive_sum(lst[1:])

print(recursive_sum([1, 2, 3, 4])) # Output: 10

Path in a Maze

def is_path(maze, x, y, path):

if x < 0 or y < 0 or x >= len(maze) or y >=


len(maze[0]) or maze[x][y] == 0:

return False

if (x, y) in path:

return False

if x == len(maze) - 1 and y == len(maze[0]) - 1:

path.append((x, y))

return True

path.append((x, y))

if is_path(maze, x + 1, y, path) or is_path(maze,


x, y + 1, path):
return True

path.pop()

return False

maze = [

[1, 0, 0],

[1, 1, 0],

[0, 1, 1]

path = []

is_path(maze, 0, 0, path)

print(path) # Output: Path to the goal

Recursive Flattening

def flatten(lst):

if not lst:

return []

if isinstance(lst[0], list):
return flatten(lst[0]) + flatten(lst[1:])

else:

return [lst[0]] + flatten(lst[1:])

print(flatten([1, [2, [3, 4]], 5])) # Output: [1, 2,


3, 4, 5]

12.

N-Queens Problem

def solve_n_queens(n, board=[], col_set=set(),


diag1_set=set(), diag2_set=set()):

if len(board) == n:

print(board)

return

row = len(board)

for col in range(n):

if col in col_set or (row - col) in diag1_set


or (row + col) in diag2_set:

continue
solve_n_queens(n, board + [col], col_set |
{col}, diag1_set | {row - col}, diag2_set | {row +
col})

solve_n_queens(4)

# Output: Solutions to 4-Queens problem

You might also like