Spaces:
Sleeping
Sleeping
File size: 3,873 Bytes
4a3f117 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 | RECURSION
=========
Recursion is when a function calls itself to solve a smaller version of the same problem.
Every recursive function needs:
1. Base case — condition to stop recursion.
2. Recursive case — function calls itself with smaller input.
--- Factorial ---
n! = n * (n-1) * ... * 1
def factorial(n):
if n == 0 or n == 1: # base case
return 1
return n * factorial(n - 1) # recursive case
print(factorial(5)) # 120
print(factorial(0)) # 1
# Iterative equivalent
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
--- Fibonacci ---
fib(n) = fib(n-1) + fib(n-2), fib(0)=0, fib(1)=1
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print([fib(i) for i in range(8)]) # [0, 1, 1, 2, 3, 5, 8, 13]
--- Sum of Array ---
def array_sum(arr):
if not arr:
return 0
return arr[0] + array_sum(arr[1:])
print(array_sum([1, 2, 3, 4, 5])) # 15
--- Power Function ---
def power(base, exp):
if exp == 0:
return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half # O(log n) — fast power
return base * power(base, exp - 1)
print(power(2, 10)) # 1024
print(power(3, 5)) # 243
--- Reverse a String ---
def reverse_string(s):
if len(s) <= 1:
return s
return reverse_string(s[1:]) + s[0]
print(reverse_string("hello")) # "olleh"
--- Check Palindrome ---
def is_palindrome(s):
if len(s) <= 1:
return True
if s[0] != s[-1]:
return False
return is_palindrome(s[1:-1])
print(is_palindrome("racecar")) # True
print(is_palindrome("hello")) # False
--- Tower of Hanoi ---
Move n disks from source to destination using auxiliary peg.
Minimum moves = 2^n - 1.
def hanoi(n, source, destination, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
hanoi(n-1, source, auxiliary, destination)
print(f"Move disk {n} from {source} to {destination}")
hanoi(n-1, auxiliary, destination, source)
hanoi(3, 'A', 'C', 'B')
# Moves disk 1 from A to C
# Moves disk 2 from A to B
# Moves disk 1 from C to B
# ... (7 total moves)
--- Binary Search (Recursive) ---
def binary_search(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7, 0, len(arr)-1)) # 3
--- Flatten Nested List ---
def flatten(lst):
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item))
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
--- Generate All Subsets (Power Set) ---
def subsets(nums):
if not nums:
return [[]]
rest = subsets(nums[1:])
return rest + [[nums[0]] + s for s in rest]
print(subsets([1, 2, 3]))
# [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
--- Generate Permutations ---
def permutations(nums):
if len(nums) <= 1:
return [nums]
result = []
for i, num in enumerate(nums):
rest = nums[:i] + nums[i+1:]
for perm in permutations(rest):
result.append([num] + perm)
return result
print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
--- Recursion vs Iteration ---
Recursion: cleaner code, natural for tree/graph problems, risk of stack overflow.
Iteration: better performance, no stack overflow, sometimes harder to read.
Use recursion when the problem is naturally recursive (trees, divide-and-conquer).
Convert to iteration for very deep recursion using an explicit stack.
|