# Recursion

How to identify recursive problem? Problem specifies choices and based on those choices make decisions.

Recursion main idea. Take a step (decision) to make the input (problem) space smaller.

## Recursion in stack memory

Consider the following recursive function

``````int fun(int n) {
if (n == 1) {
return 1;
}
return 1 + fun(n - 1);
}

int main() {
int n = 3;
printf("%d", fun(n));
return 0;
}``````
• `main` function is pushed to the stack as it is the first function to execute in a file. This means pushing its activation record to the stack, which includes the locals of the function, parameters of the function, return address to the caller, and along with other things. In the diagram the local variable `n=3` is pushed as the record of `main()`.
• Inside `main()`, `fun` is called. This means activation record of `fun(3)` is pushed to the stack, and the parameter `n=3` would be stored inside it.
• Inside `fun(3)`, `fun(2)` is called, so its activation record is pushed to the stack and same for `fun(1)`.
• Inside `fun(1)`, the value 1 is returned. So pop `fun(1)` from the stack and get the address of the previous function to resume execution.
• The above process is repeated till `main()` is popped from the stack and the program exists.

The space complexity of recursion is the maximum number of functions pushed to the stack. For the example shown above the maximum number of functions pushed to the stack `n` and thus the space complexity of recursion is `O(n)`.

## Types of recursion

1. Direct recursion. If the same function is called again.

``````def fun():
fun()``````
2. Indirect recursion. If `fun1` calls `fun2`, and then `fun2` calls `fun1`.

``````def fun1():
fun2()

def fun2():
fun1()``````
3. Tail recursion. Special case of direct recursion, where the recursive call (also called tail call) is the last thing done by the function.

Tail calls can be implemented without adding a new stack frame to the call stack, and thus the space complexity becomes constant. This is called tail-call optimization. GCC/Clang support tail-recursion optimization. Python does not support this.

``````def fun(n):
# some code
fun(n-1) # or it can be 'return fun()'``````
4. Non-tail recursion. Special case of direct recursion, where the recursive call is not the last thing done by the function.

``````def fun(n):
if n == 1:
return 1
return 1 + fun(n - 1) # After making the recursive call
# 1 needs to be added to the output``````

## Convert non-tail to tail recursive

Use these general steps to convert recursive function to tail recursive function

1. Find a recursive call that’s not a tail call.
2. Identify what work is being done between that call and its return statement.
3. Extend the function with an accumulator function `accFn` argument to do that work, with a default value that causes it to do nothing.
4. Repeat until all recursive calls are tail calls.

isEven

Non-tail recursive function

``````def isEven(n):
if n == 0:
return True
return not isEven(n-1)``````

Convert it to tail-recursive function

1. Identify the recursive call and the work being done between the call and its return statement. `return not isEven(n-1)`. And the extra work is negation of the output.
2. Define a function that does this extra work, and pass it as an argument. The default argument of this parameter should be a function that does no work.
``````def do_nothing(x):
return x

def negate(x):
return not x

def isEven(n, accFn = do_nothing):
if n == 0:
return True
return isEven(n-1, negate)``````
3. Next, make use of `accFn` in the function. And temporarily pass the return statement to `accFn`.
``````def isEven(n, accFn = do_nothing):
if n == 0:
return accFn(True)
return accFn(isEven(n-1, negate))``````
4. The above function is still not tail-recursive. But now we can compose `accFn` and `negate` to make it a single function.
``````def compose(func1, func2):
def inner(*args, **kwargs):
return func1(func2(*args, **kwargs))
return inner

def isEven(n, accFn = do_nothing):
if n == 0:
return accFn(True)
return isEven(n-1, compose(accFn, negate))``````

The final code is

``````# Non-tail recursive function
def isEven(n):
if n == 0:
return True
return not isEven(n-1)

# Tail recursive function
def default_value(x):
return x

def extra_work(x):
return not x

def compose(a, b):
def inner(*args, **kwargs):
return a(b(*args, **kwargs))
return inner

def isEven(n, accFn = default_value):
if n == 0:
return accFn(True)
return isEven(n-1, compose(accFn, extra_work))

print(isEven(4))
# True``````

sumTo

Non-tail recursive function

``````def sumTo(n):
if n == 0:
return 0
return n + sumTo(n - 1)

sumTo(10)
# 55``````

Convert to tail recursive

1. Identify the recursive call and the extra work being done
• recursive call = `sumTo(n-1)`
• extra work = `n + sumTo(n-1)` i.e. add `n` to the output of the recursive call.
2. Create an argument and pass all the extra work to that
``````def sumTo(n, prev_sum = 0):
if n == 0:
return prev_sum
return sumTo(n - 1, prev_sum + n)``````
3. The default value should be based on what is returned in the base case. For `n=0`, 0 should be returned.

This is the preferred approach of converting non-tail recursive function to recursive function. This examples shows how to compose the data instead of explicitly composing functions.

The previous example if isEven can also be done using this

1. Identify the recursive call and the extra work being done
• recursive call = `isEven(n-1)`
• extra work = `not isEven(n-1)` i.e. negate the output of the recursive call.
2. Create an argument and pass all the extra work to that
``````def isEven(n, prev_result = True):
if n == 0:
return prev_result
return isEven(n-1, not prev_result)``````
3. The default value should be based on what is returned in the base case. As `0` is considered even, the default value is `True`.

Consider the problem of computing binomial coefficient.

``````def binomial(n, k):
if k == 0:
return 1
return n * binomial(n-1, k-1) // k``````

Move all the extra work to a function. The extra work in this case is

``````out = binomial(n-1, k-1)
out = out * n
out = out // k``````

Now create a function that does this extra work

``````def extra_work(out, lmul, rdiv):
out = out * lmul
out = out // rdiv
return out``````

Pass this function as an argument

``````def binomial(n, k, lmul=1, rdiv=1):
if k == 0:
return extra_work(1, lmul, rdiv)
return extra_work(n * binomial(n-1, k-1) // k, lmul, rdiv)``````

Use the new function to eliminate the extra work

``````def binomial(n, k, lmul=1, rdiv=1):
if k == 0:
return extra_work(1, lmul, rdiv)
return binomial(n-1, k-1, n*lmul, k*rdiv)``````

Since the work function is small, we can just make it inline

``````def binomial(n, k, lmul=1, rdiv=1):
if k == 0:
return lmul * 1 // rdiv
return binomial(n-1, k-1, n*lmul, k*rdiv)``````

## Convert tail recursive to iterative

1. Wrap everything in an infinite loop.
2. Change the function arguments into variable declarations
``````# non-tail recursive
def sumTo(n):
if n == 0:
return 0
return n + sumTo(n - 1)

# tail recursive
def sumTo(n, prev_sum = 0):
if n == 0:
return prev_sum
return sumTo(n - 1, prev_sum + n)

# iterative
def sumTo(n, prev_sum = 0):
while True:
if n == 0:
return prev_sum
n, prev_sum = n - 1, prev_sum + n``````
``````# non-tail recursive
def isEven(n):
if n == 0:
return True
return not isEven(n-1)

# tail recursive
def isEven(n, prev_result = True):
if n == 0:
return prev_result
return isEven(n-1, not prev_result)

# iterative
def isEven(n, prev_result = True):
while True:
if n == 0:
return prev_result
n, prev_result = n - 1, not prev_result``````
``````# non-tail recursive
def factorial(n):
if n < 2:
return 1
return n * factorial(n-1)

# tail recursive
def factorial(n, prev_result = 1):
if n < 2:
return prev_result
return factorial(n-1, prev_result * n)

# iterative
def factorial(n, prev_result = 1):
while True:
if n < 2:
return prev_result
n, prev_result = n - 1, prev_result * n``````
``````# non-tail recursive
def find_val_or_next_smallest(bst, x):
if bst is None:
return None
elif bst.val == x:
return x
elif bst.val > x:
return find_val_or_next_smallest(bst.left, x)
else:
right_best = find_val_or_next_smallest(bst.right, x)
if right_best is None:
return bst.val
return right_best

# tail recursive
def find_val_or_next_smallest(bst, x, acc=None):
if bst is None:
return acc
elif bst.val == x:
return x
elif bst.val > x:
return find_val_or_next_smallest(bst.left, x, acc)
else:
return find_val_or_next_smallest(bst.right, x, bst.val)

# iterative
def find_val_or_next_smallest(bst, x, acc=None):
while True:
if bst is None:
return acc
elif bst.val == x:
return x
elif bst.val > x:
bst, x, acc = bst.left, x, acc
else:
bst, x, acc = bst.right, x, bst.val``````
``````# non-tail recursive
def binomial(n, k):
if k == 0:
return 1
return n * binomial(n-1, k-1) // k

# tail recursive
def binomial(n, k, lmul=1, rdiv=1):
if k == 0:
return extra_work(1, lmul, rdiv)
return binomial(n-1, k-1, n*lmul, k*rdiv)

# iterative
def binomial(n, k, lmul=1, rdiv=1):
while True:
if k == 0:
return lmul // rdiv
n, k, lmul, rdiv = n-1, k-1, lmul*n, k*rdiv``````

## How to solve recursive problems?

Approach 1. Think if you are making any decisions? Use recursive tree.
Approach 2. If you cannot think of decisions, think if you make the input smaller? Use induction hypothesis (tree and linked list problems).

### Input-Output method

Use when it is easy to identify the decisions.

Build a recursive tree

Convert recursive tree to code

``````def solve(inp, out):
# Define base condition, which is mostly when the input becomes empty
if something:
# code
return

# Make decision to generate left tree
solve(smaller_input_left, new_output_left)

# Make decision to generate right tree
solve(smaller_input_right, new_output_right)

inp = ORIGINAL_INPUT
out = EMPTY_OUTPUT

solve(inp, out)``````

### Extended Input-Output

Extension of previous where input and output are of different data type. For example, input can be number and output is a string.

Build recursive tree in this case also, but you would have to track some other parameter along with it.

### Induction Hypothesis

Use when it is easy to think about making the input smaller (especially for tree and linked list problems).

Hypothesis

• Define function `solve(n)` that generates the required output.
• Call the function with smaller input `solve(n-1)`, and generate the output.

Induction

• Identify the relationship between `solve(n)` and `solve(n-1)`.

Use Mathematical Induction to prove that your hypothesis is correct. This is a three step process

1. Check the hypothesis is correct for the base condition.
2. Assume the hypothesis is true for `k`.
3. Check if the hypothesis is also true for `k+1` by using the above assumption.

Base condition

• Smallest valid input, or
• Smallest invalid input

## Time complexity

### Common patterns

``````def func(n):
if n == 0:
return 1
return 1 + func(n-1)``````

The recurrence relation is `T(n) = T(n-1)`. So the function is called recursively `n` times and thus `O(n)`.

``````def func(n):
if n == 0:
return 1
return 1 + func(n - 5)``````

The recurrence relation is `T(n) = T(n-5)`. At each recursive call we subtract 5, so in the end we only end up doing `n/5` calls and thus `O(n)`.

``````def func(n):
if n == 0:
return 1
return 1 + func(n/5)``````

At each recursive call we divide by 5. So we start with `n`, then `n/5`, `n/25`, `n/125` and so on. In total we keep dividing till we cannot divide by 5, so we need to find `x` (the total number of steps in this process) in `n = 5**x`, and taking `log` on both sides we get `x = log(n) base 5`.

And this `T(n) = T(n/k)` is logarithmic base `k` (O(logn)). And by dropping constants we can write it as base 2.

``````def func(n):
if n == 0:
return
func(n-1)
func(n-1)``````

The recurrence relation is `T(n) = 2T(n-1)`. For each recursive call, we make two further calls and thus it is exponential `O(2^n)`.

``````def func(n):
for i in range(n):
pass

if n == 0:
return 1
return 1 + func(n-1)``````

The recurrence relation is `T(n) = T(n-1) + n`. You can expand this recurrence `T(n) = T(n-2) + n-1 + n` and so on. In the end you get `O(n^2)`.

### Substitution method

1. Make a guess.
2. Use induction to prove if the guess is right.
• Example `T(n) = 2T(n/2) + n`, n > 1
• Guess `T(n) = O(nlogn)`
• Prove using induction
• Assume `T(n)` is true i.e. `T(n) <= cn logn`
• Now `T(n/2) <= c(n/2)log(n/2)` or `T(n/2) <= cn log(n/2)`
• Use it in the original recurrence relation
• `T(n) <= cnlog(n/2) + n`
• `T(n) <= cnlog(n) - cnlog(2) + n`
• `T(n) <= cnlog(n) + n(1-c)`
• Therefore, `T(n) <= cnlog(n)` for all `c >= 1`
• Next prove the base conditions and find for what values of n does this recurrent hold (assume some value of c). In this case, let `c=2`, then `n>=2`.

### Iterative method

1. Brute force method where you substitute the recurrent part until a pattern is observed (you basically add everything up, and remove the constants).
• `T(n) = T(n-1) + n`
• Substitute `T(n-1)`, `T(n) = T(n-2) + n-1 + n`
• Keep repeating and you get `T(n) = O(n^2)`.

### Recursive tree

Used when the input is split into two smaller inputs like `T(n) = 2T(n/2) + cn`, where we make two recursive calls with half the input for each.

Draw the recurrence tree till the base case, and sum the time takes at all levels to get the overall time complexity.

### Master Theorem

``````T(n) = aT(n/b) + f(n)

x = n^(log_b(a))

if f(n) < x, then T(n) = n^log_b(a)
if f(n) = x, then T(n) = f(n)log(n)
if f(n) > x, then T(n) = f(n)``````

`T(n/b)` means the input gets smaller by a factor of `b` at each step. This can happen for logarithmic steps. And thus we get `log_b(n)`.

Think of the following recurrence (similar to binary search)

``````def func(n):
if n == 0:
return 1
return func(n/2)``````

`aT(n/b)` means at each step we are doing `a` recursive calls, with input of size `n/b`. This is exponential and we get a total of `a^(log_b(n))` calls.

Think of the following recurrence (draw the recursive tree, and you will why it is exponential)

``````def func(n):
if n == 0:
return 1
func(n-1)
func(n-1)``````

`a^(log_b(n)) = n^(log_b(a))`. This is how we get `x` in the master theorem. To prove this, take `log_b` of both sides

``````a^(log_b(n))        | n^(log_b(a))
log_b(a^(log_b(n))) | log_b(n^log_b(a))
log_b(n)log_b(a)    | log_b(a)log_b(n)
log_b(a)log_b(n)    | log_b(a)log_b(n)``````

If time complexity of `aT(n/b) > f(n)`, then it dominates big-O and we get final time complexity the same as `a(T(n/b))` which is `n^log_b(a)`.

If time complexity of `aT(n/b) < f(n)`, then `f(n)` dominates big-O and we get final time complexity as `f(n)`.

If the time complexity of `aT(n/b) = f(n)`, then at each step we do `f(n)` which has the same time complexity as `aT(n/b)` which is `n^(log_b(a))`. Since there are `log_b(a)` steps, the total time complexity if `n^(log_b(a)) log_b(a)`.

## Problems

Problem. Given a positive integer `n`, print all numbers from `1` to `n`.

Identify recursive problem. Easier to think in terms of making the input smaller.

Hypothesis approach

• Assume the function `solve(n)` prints all numbers from `1` to `n`.
• Next, check for the next smaller input i.e. `n-1` and `solve(n-1)` prints all numbers from `1` to `n-1`.
• Next, identify the relationship between `solve(n)` and `solve(n-1)`. In this case, it is something like `solve(n) = solve(n-1) + print_to_stdout(n)`.
• Next, identify the base case to stop recursion. We can choose the smallest valid input i.e. `1` or the smallest invalid input i.e. `0`.
``````def solve(n):
if n == 0:
return

solve(n - 1)
print(n)

solve(10)
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 9
# 10``````

Extension of the above problem.

Hypothesis approach

• Assume the function `solve(n)` prints all numbers `n` to `1`.
• Next, check for the next smaller input i.e. `n-1` and `solve(n-1)` prints all numbers from `n-1` to `1`.
• Next, identify the relationship between `solve(n)` and `solve(n-1)`. In this case, it is something like `solve(n) = print_to_stdout(n) + solve(n-1)`.
• Use `0` as the base case.
``````def solve(n):
if n == 0:
return

print(n)
solve(n-1)

solve(10)
# 10
# 9
# 8
# 7
# 6
# 5
# 4
# 3
# 2
# 1``````

### Height of binary tree

Problem. Height is the maximum distance from root to leaf node.

Hypothesis approach

• Assume the function `solve(node)` returns the height of binary tree where `node` is the `root` node of the tree.
• Next, check for smaller input. In this case, smaller input refers to the children of `node`, so `solve(left_child_node)` returns the height of the tree rooted at `left_child_node`.
• Next, identify the relationship between the two functions. `solve(node) = max(solve(left_child_node), solve(right_child_node)) + 1`.
• Identify base case, which can be either be node with no children or empty node.
``````class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None

def solve(node):
if node is None:
return 0

height_left = solve(node.left)
height_right = solve(node.right)

height = max(height_left, height_right) + 1

return height

root = Node(3)
root.left = Node(9)
root.right = Node(20)
root.right.left = Node(15)
root.right.left.right = Node(7)

print(solve(root))
# 4``````

### Sort an array

Problem. Given array `[2,3,7,6,4,5,9]`, sort it `[2,3,4,5,6,7,9]`.

Hypothesis approach

• Assume the function `solve(arr, n)` sorts an array of length `n`.
• Next, check for smaller input. In this case, smaller input refers to array of length `n-1`, so `solve(arr, n-1)` sorts an array of length `n-1`.
• Next, identify relationship between the two functions. `solve(arr, n) = solve(arr, n-1) + move arr[n-1] to correct position` (`arr[n-1]` because 0-based indexing is being used).
• Identify base case, which can be empty array or array of length 1.
``````def solve(arr, n):
if n == 0:
return

solve(arr, n-1)

# Swap the last element till it is in correct position
# For input = [1,2,3,5,6,4], and the last element = 4
# Swap (6,4), arr = [1,2,3,5,4,6]
# Swap (5,4), arr = [1,2,3,4,5,6]
# Now 4 > 3, so need to swap more
for i in range(n-1, 0, -1):
if arr[i] < arr[i-1]:
arr[i-1], arr[i] = arr[i], arr[i-1]
else:
break

arr = [2,3,7,6,4,5,9]
solve(arr, len(arr))
print(arr)
# [2, 3, 4, 5, 6, 7, 9]``````

### Sort a stack

Problem. Given a stack `[5, 1, 0, 2]`. and create sorted stack `[0, 1, 2, 5]`.

Hypothesis approach

• Assume the function `solve(stack)` sorts a stack of size `n`.
• Next, check for smaller input. In this case, smaller input refers to stack of size `n-1`, so `solve(smaller_stack)` sorts a stack of size `n-1`.
• Next, identify relationship between two functions. `solve(stack) = solve(smaller_stack) + insert_top_item_in_correct_position`.
• Identify base case, which can be empty stack or stack of size 1.
``````class Stack:
def __init__(self, arr=[]):
self.arr = arr
def push(self, x):
self.arr.append(x)
def pop(self):
if len(self.arr) > 0:
return self.arr.pop()
def top(self):
return self.arr[-1]
def size(self):
return len(self.arr)

def solve(stack):
if stack.size() == 0:
return

top = stack.pop()
solve(stack)

# Remove all items greater than 'top' element from the stack
temp_stack = Stack()
while stack.size() > 0 and top < stack.top():
temp_stack.push(stack.pop())

# Insert 'top' element in correct position and insert the items
# removed in the previous step.
stack.push(top)
while temp_stack.size() > 0:
stack.push(temp_stack.pop())

stack = Stack([2,3,7,6,4,5,9])
solve(stack)

print(stack.arr)
# [2, 3, 4, 5, 6, 7, 9]``````

### Delete middle element of stack

Problem. Given a stack `[1,2,3,4,5]` delete the middle element of stack. In case of even stack size, delete the right element from the center i.e. `len(stack) // 2 + 1`.

Hypothesis approach

• Assume the function `solve(stack, k)` delete’s the element at position `k` (from the bottom) in the stack.
• Next, check for smaller input. In this case, smaller input refers to stack with the top element popped and `solve(smaller_stack, k)` delete’s the element at position `k` in this stack.
• Next, identify relationship between two functions. `solve(stack, k) = solve(smaller_stack, k) + insert_top_element`.
• Identify base case, which is stack of size `k`.
``````class Stack:
def __init__(self, arr=[]):
self.arr = arr
def push(self, x):
self.arr.append(x)
def pop(self):
if len(self.arr) > 0:
return self.arr.pop()
def size(self):
return len(self.arr)

def solve(stack, k):
# Edge case
if stack.size() == 0:
return

if stack.size() == k:
# Delete 'center' element
stack.pop()
return

top = stack.pop()
solve(stack, k)
stack.push(top)

stack = Stack([1,2,3,4,5])
solve(stack, stack.size() // 2 + 1)

print(stack.arr)
# [1, 2, 4, 5]``````

### Reverse a stack

Hypothesis approach

• Assume the function `solve(stack)` reverse’s `stack`.
• Next, check for smaller input. In this case, smaller input refers to stack with the top element popped and `solve(smaller_stack)` reverse’s `smaller_stack`.
• Next, identify relationship between the two functions.
``````stack = [1,2,3,4]
top = 4
smaller_stack = [1,2,3]
solve(smaller_stack) = [3,2,1]``````
• To insert `top` at the start of stack, we have to make another recursive function.
• Assume the function `inner_solve(stack, k)` insert’s the element `k` at the start of `stack`.
• Next, check for smaller input. In this case, smaller input refers to stack with the top element popped and `inner_solve(smaller_stack, k)` insert’s the element `k` at the start of `smaller_stack`.
• Next, identify relationship between the two functions. `inner_solve(stack, k) = inner_solve(smaller_stack, k) + insert the top element back`.
• Identify base case, which is empty stack.
• So the relationship becomes `solve(stack) = solve(smaller_stack) then inner_solve(smaller_stack, top)`.
• Identify base case, which is empty stack.
``````class Stack:
def __init__(self, arr=[]):
self.arr = arr
def push(self, x):
self.arr.append(x)
def pop(self):
if len(self.arr) > 0:
return self.arr.pop()
def size(self):
return len(self.arr)

def inner_solve(stack, k):
if stack.size() == 0:
stack.push(k)
return

top = stack.pop()
inner_solve(stack, k)

stack.push(top)

def solve(stack):
if stack.size() == 0:
return

top = stack.pop()
solve(stack)

inner_solve(stack, top)

stack = Stack([1,2,3,4,5,6])
solve(stack)

print(stack.arr)
# [6, 5, 4, 3, 2, 1]``````

### K-th symbol in grammar

Problem. Given two integers `n` and `k`, where `n` represents row number and `k` column number in a table (1-indexed). Base case (n=1, k=1), the table has value `0`. For `n=2` row, replace `0` in previous row with `(0,1)` and `1` with `(1,0)`. So second row becomes `[0,1]`. Similarly, third row becomes `[0,1,1,0]`. Return the value in cell `n,k`.

Hypothesis approach

• Assume the function `solve(n, k)` return’s the k-th value in the n-th row.
• Next, check for smaller input. In this case, smaller input refers to the previous row i.e. `n-1`. So `solve(n-1, k // 2)` returns `k // 2` value in `n-1` row.
• Next, identify the relationship between the two function. `solve(n, k) = flip_number_from solve(n-1, k // 2)`.
• Identify base case, which is `n = 1`, `k = 1`.
``````def solve(n, k):
if n == 1 and k == 1:
return 0

# (1,1)
# (2,1), (2,2)
# 1 and 2 needs to be mapped to 1. This can be done using (k-1) // 2 + 1
previous_bit = solve(n-1, (k-1) // 2 + 1)

# In case of left_child i.e. (2,1) use the previous bit otherwise flip the
# bit. Because 0 becomes 0,1 and 1 becomes 1,0. In both cases, the left
# child is same as parent.
if k % 2 == 1:
bit = previous_bit
else:
if previous_bit == 0:
bit = 1
else:
bit = 0

return bit

print(solve(2,1))
# 0``````

### Tower of Hanoi

Problem. Given three rods and `N` disks. All the `N` disks are in the first rod in ascending order (with the largest being at the bottom). Print all the moves to move all the `N` disks to the third rod. A smaller disk cannot be put under bigger disk, and you can only move one disk at a time.

Hypothesis approach

• Assume the function `solve(n)` moves `n-1` disks to the other rod (not the 3rd) while preserving the original order.Then the `n-th` disk is moved to rod 3.
• Now check for smaller input. In this case it refers to a stack of `n-1` disks. So `solve(n-1)`, moves `n-2` disks to the other rod (not the 3rd) and move `n-1`th disk to rod 3.
• Next, identify the relationship between the two functions. `solve(n) = move nth disk to rod 3 + solve(n-1)`.
• Identify base case, which is empty stack of disks or a single disk (which can be moved to rod 3 in a single step).
``````def solve(n, from_rod=1, to_rod=3, helper_rod=2):
if n == 0:
return

# Step 1. Move all rods from "from" to "to" using "helper"
# Step 2. Move 'n' rod to "to"
# Step 3. Move all rods from "helper" to "to" using "from"

solve(n-1, from_rod, helper_rod, to_rod)
print(f'Move disk {n} from rod {from_rod} to {to_rod}')
solve(n-1, helper_rod, to_rod, from_rod)

solve(3)
# Move disk 1 from rod 1 to 3
# Move disk 2 from rod 1 to 2
# Move disk 1 from rod 3 to 2
# Move disk 3 from rod 1 to 3
# Move disk 1 from rod 2 to 1
# Move disk 2 from rod 2 to 3
# Move disk 1 from rod 1 to 3``````

### Josephus problem

Problem. There are `n` people in a circle (numbered 1 to n). Starting from the first person, kill the `k-th` person and repeat till only one person is left.

Hypothesis approach

• Assume the function `solve(n, k)` gives the last remaining person.
• Now `solve(n-1, k)` gives the last remaining person if there were `n-1` people.
• Next, identify the relationship between the two functions. If we know the winner for `n-1` and `k`, then the winner of `n` and `k` is `solve(n,k) = solve(n-1,k) + k`. To make the numbers wrap back to 1, since they are in a circle take modulo.
• Base, case if when there is only 1 person and they are the winner.
``````def solve(n, k):
if n == 1:
return 0

return (solve(n-1, k) + k) % n

solve(6, 5) + 1 # Add 1 to convert to 1-based indexing
# 1``````

### Generate all subsets of string

Problem. Given a string `abc` generate all its subsets `'', a, b, c, ab, bc, ac, abc`.

Identify recursive problem. You are given a choice whether to include `a` or `b` or `c` in the output or not.

Recursion idea. Choose whether to include `a` in the output or not. Then you are left with the string `bc`, which is smaller than the original input string (`abc`).

Build recursive tree. Construct the tree by initializing output to empty string and input string to `ab` (not using `abc` for smaller diagram).

Convert recursive tree to code

``````def solve(inp, out):
if len(inp) == 0:
print(out)
return

# Make left tree (include 'a')
solve(inp[1:], out +  inp)

# Make right tree (do not include 'a')
solve(inp[1:], out)

inp = 'abc'
out = ''
solve(inp, out)
# abc
# ab
# ac
# a
# bc
# b
# c
# ``````

The above code can be made more efficient by passing index of string, rather than modifying the string

``````def solve(inp, inp_index, out):
if inp_index == len(inp):
print(out)
return

solve(inp, inp_index+1, out + inp[inp_index])
solve(inp, inp_index+1, out)

inp = 'abc'
out = ''
solve(inp, 0, out)
# abc
# ab
# ac
# a
# bc
# b
# c
# ``````

Problem. Given a list of numbers, generate all unique subsets.

Extension of above problem, but not we need to use a set to remove redundant items.

``````output_set = set()

def solve(nums, index=0, out=''):
if index == len(nums):
return

solve(nums, index+1, out + f'_{nums[index]}')
solve(nums, index+1, out)

nums = [4,1,4]
nums.sort() # necessary to to handle the case [4,1], [1,4]

solve(nums)

# Convert strings to list of numbers
out = []
for v in output_set:
out.append([int(x) for x in v.split('_')[1:]])

print(out)
# [[], [4, 4], [1, 4, 4], , [1, 4], ]``````

Problem. Given a string `abc`, generate all permutations with spaces between characters `a_b_c, a_bc, ab_c, abc`.

Identify recursive problem. You are given a choice where to put underscore after a character or not.

Build recursive tree

Convert recursive tree to code

``````def solve(inp, inp_index=0, out=''):
if inp_index == len(inp) - 1:
out = out + inp[inp_index]
print(out)
return

solve(inp, inp_index+1, out + inp[inp_index] + '_')
solve(inp, inp_index+1, out + inp[inp_index])

inp = 'abc'
solve(inp)
# a_b_c
# a_bc
# ab_c
# abc``````

### Change case of letters in string

Problem. Given a string containing lowercase letters, uppercase characters and digits. Generate all permutations of the string where each character can be changed with its uppercase/lowercase letter. E.g. for `a1B2`, the output is `['a1b2', 'a1B2', 'A1b2', 'A1B2']`.

``````def solve(inp, inp_index=0, out=''):
if inp_index == len(inp):
print(out)
return

c = inp[inp_index]
inp_index += 1

if c >= '0' and c <= '9':
solve(inp, inp_index, out + c)
else:
solve(inp, inp_index, out + c.lower())
solve(inp, inp_index, out + c.upper())

inp = 'a1B2'
solve(inp)
# a1b2
# a1B2
# A1b2
# A1B2``````

### Generate all balanced parenthesis

Problem. Given `n` generate all combinations of balanced parenthesis.

Identify recursive problem. Given a string with `2*n` places, we need to place `n` opening brackets and `n` closing brackets. So we have a choice to put opening/closing bracket at each position and we make a decision to decide which one to place.

Build recursive tree

• Maintain the number of open brackets and closed brackets left to add.
• If both are equal, then only open bracket can be added.
• If number of open bracket = 0, then only closed bracket can be added.
• If number of open brackets less than closed brackets, then either of them can be added.

Convert recursive tree to code

``````def solve(o, c, out=''):
if o == 0 and c == 0:
print(out)
return

if o == 0:
solve(o, c-1, out + ')')
elif o == c:
solve(o-1, c, out + '(')
elif o < c:
solve(o-1, c, out + '(')
solve(o, c-1, out + ')')

n = 3
solve(o=3, c=3)
# ((()))
# (()())
# (())()
# ()(())
# ()()()``````

### Binary num with more 1’s than 0’s

Problem. Given a number `n` as input. Generate all `n-digit` binary numbers where then number of 1’s greater than number of 0’s in all the prefixes of the number. If `n=5`, then one possible output is `11010`, and it prefixes are `1, 11, 110, 1101, 11010` and in all the prefixes number of 1’s greater than number of 0’s.

Identify recursive problem. Given `n` places, we want to place either 0/1 in each of the places based on a decision.

Build recursive tree.

• Maintain the number of 1’s and number of 0’s inserted.
• Number of 1’s should always be greater than number of 0’s at each step (to ensure the prefix condition).

Convert recursive tree to code

``````def solve(n, num_1=0, num_0=0, out=''):
if n == 0:
print(out)
return

if num_1 == num_0:
solve(n-1, num_1+1, num_0, out + '1')
elif num_1 > num_0:
solve(n-1, num_1+1, num_0, out + '1')
solve(n-1, num_1, num_0+1, out + '0')

solve(5)
# 11111
# 11110
# 11101
# 11100
# 11011
# 11010
# 11001
# 10111
# 10110
# 10101``````

### Generate contest matches

Problem. In a match between teams `1` to `n`, you matach 1 plays n, 2 plays n-2 and so on. Then in the second round again the stronger team `(1,n)` plays with `(n//2,n//2+1)`.

``````Input: n = 8
Output: "(((1,8),(4,5)),((2,7),(3,6)))"
Explanation:
First round: (1, 8),(2, 7),(3, 6),(4, 5)
Second round: ((1, 8),(4, 5)),((2, 7),(3, 6))
Third round: (((1, 8),(4, 5)),((2, 7),(3, 6)))
Since the third round will generate the final winner, you need to output the answer (((1,8),(4,5)),((2,7),(3,6))).``````

Recursion idea

• Convert input to list. So [1,2,3,4,…,n]
• `solve(l)`, generates the required string for the above list
• `solve(new_l)`, generate the requirers string the list created from `solve(l)` and so on till the length of the list becomes 1.
``````def solve(l):
new_l = []
for i in range(len(l)//2):
new_l.append(f'({l[i]},{len(l)-i-1})')

if len(new_l) == 1:
return new_l

return solve(new_l)

n = 8
l = [i for i in range(1, n+1)]
print(solve(l))``````