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 variablen=3
is pushed as the record ofmain()
. Inside
main()
,fun
is called. This means activation record offun(3)
is pushed to the stack, and the parametern=3
would be stored inside it.  Inside
fun(3)
,fun(2)
is called, so its activation record is pushed to the stack and same forfun(1)
.  Inside
fun(1)
, the value 1 is returned. So popfun(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

Direct recursion. If the same function is called again.
def fun(): fun()

Indirect recursion. If
fun1
callsfun2
, and thenfun2
callsfun1
.def fun1(): fun2() def fun2(): fun1()

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 tailcall optimization. GCC/Clang support tailrecursion optimization. Python does not support this.
def fun(n): # some code fun(n1) # or it can be 'return fun()'

Nontail 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 nontail to tail recursive
Use these general steps to convert recursive function to tail recursive function
 Find a recursive call that’s not a tail call.
 Identify what work is being done between that call and its return statement.
 Extend the function with an accumulator function
accFn
argument to do that work, with a default value that causes it to do nothing.  Repeat until all recursive calls are tail calls.
isEven
Nontail recursive function
def isEven(n):
if n == 0:
return True
return not isEven(n1)
Convert it to tailrecursive function
 Identify the recursive call and the work being done between the call and its return statement.
return not isEven(n1)
. And the extra work is negation of the output.  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(n1, negate)
 Next, make use of
accFn
in the function. And temporarily pass the return statement toaccFn
.def isEven(n, accFn = do_nothing): if n == 0: return accFn(True) return accFn(isEven(n1, negate))
 The above function is still not tailrecursive. But now we can compose
accFn
andnegate
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(n1, compose(accFn, negate))
The final code is
# Nontail recursive function
def isEven(n):
if n == 0:
return True
return not isEven(n1)
# 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(n1, compose(accFn, extra_work))
print(isEven(4))
# True
sumTo
Nontail recursive function
def sumTo(n):
if n == 0:
return 0
return n + sumTo(n  1)
sumTo(10)
# 55
Convert to tail recursive
 Identify the recursive call and the extra work being done
 recursive call =
sumTo(n1)
 extra work =
n + sumTo(n1)
i.e. addn
to the output of the recursive call.
 recursive call =
 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)
 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 nontail 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
 Identify the recursive call and the extra work being done
 recursive call =
isEven(n1)
 extra work =
not isEven(n1)
i.e. negate the output of the recursive call.
 recursive call =
 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(n1, not prev_result)
 The default value should be based on what is returned in the base case. As
0
is considered even, the default value isTrue
.
Consider the problem of computing binomial coefficient.
def binomial(n, k):
if k == 0:
return 1
return n * binomial(n1, k1) // k
Move all the extra work to a function. The extra work in this case is
out = binomial(n1, k1)
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(n1, k1) // 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(n1, k1, 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(n1, k1, n*lmul, k*rdiv)
Convert tail recursive to iterative
 Wrap everything in an infinite loop.
 Change the function arguments into variable declarations
# nontail 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
# nontail recursive
def isEven(n):
if n == 0:
return True
return not isEven(n1)
# tail recursive
def isEven(n, prev_result = True):
if n == 0:
return prev_result
return isEven(n1, 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
# nontail recursive
def factorial(n):
if n < 2:
return 1
return n * factorial(n1)
# tail recursive
def factorial(n, prev_result = 1):
if n < 2:
return prev_result
return factorial(n1, 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
# nontail 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
# nontail recursive
def binomial(n, k):
if k == 0:
return 1
return n * binomial(n1, k1) // k
# tail recursive
def binomial(n, k, lmul=1, rdiv=1):
if k == 0:
return extra_work(1, lmul, rdiv)
return binomial(n1, k1, 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 = n1, k1, 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).
InputOutput 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 InputOutput
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(n1)
, and generate the output.
Induction
 Identify the relationship between
solve(n)
andsolve(n1)
.
Use Mathematical Induction to prove that your hypothesis is correct. This is a three step process
 Check the hypothesis is correct for the base condition.
 Assume the hypothesis is true for
k
.  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(n1)
The recurrence relation is T(n) = T(n1)
. 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(n5)
. 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(n1)
func(n1)
The recurrence relation is T(n) = 2T(n1)
. 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(n1)
The recurrence relation is T(n) = T(n1) + n
. You can expand this recurrence T(n) = T(n2) + n1 + n
and so on. In the end you get O(n^2)
.
Substitution method
 Make a guess.
 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)
orT(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(1c)
 Therefore,
T(n) <= cnlog(n)
for allc >= 1
 Assume
 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
, thenn>=2
.
Iterative method
 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(n1) + n
 Substitute
T(n1)
,T(n) = T(n2) + n1 + 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(n1)
func(n1)
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 bigO 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 bigO 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
Print numbers 1 to n
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 from1
ton
.  Next, check for the next smaller input i.e.
n1
andsolve(n1)
prints all numbers from1
ton1
.  Next, identify the relationship between
solve(n)
andsolve(n1)
. In this case, it is something likesolve(n) = solve(n1) + 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
Print numbers n to 1
Extension of the above problem.
Hypothesis approach
 Assume the function
solve(n)
prints all numbersn
to1
.  Next, check for the next smaller input i.e.
n1
andsolve(n1)
prints all numbers fromn1
to1
.  Next, identify the relationship between
solve(n)
andsolve(n1)
. In this case, it is something likesolve(n) = print_to_stdout(n) + solve(n1)
.  Use
0
as the base case.
def solve(n):
if n == 0:
return
print(n)
solve(n1)
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 wherenode
is theroot
node of the tree.  Next, check for smaller input. In this case, smaller input refers to the children of
node
, sosolve(left_child_node)
returns the height of the tree rooted atleft_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 lengthn
.  Next, check for smaller input. In this case, smaller input refers to array of length
n1
, sosolve(arr, n1)
sorts an array of lengthn1
.  Next, identify relationship between the two functions.
solve(arr, n) = solve(arr, n1) + move arr[n1] to correct position
(arr[n1]
because 0based 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, n1)
# 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(n1, 0, 1):
if arr[i] < arr[i1]:
arr[i1], arr[i] = arr[i], arr[i1]
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 sizen
.  Next, check for smaller input. In this case, smaller input refers to stack of size
n1
, sosolve(smaller_stack)
sorts a stack of sizen1
.  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 positionk
(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 positionk
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’sstack
.  Next, check for smaller input. In this case, smaller input refers to stack with the top element popped and
solve(smaller_stack)
reverse’ssmaller_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 elementk
at the start ofstack
.  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 elementk
at the start ofsmaller_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.
 Assume the function
 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]
Kth symbol in grammar
Problem. Given two integers n
and k
, where n
represents row number and k
column number in a table (1indexed). 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 kth value in the nth row.  Next, check for smaller input. In this case, smaller input refers to the previous row i.e.
n1
. Sosolve(n1, k // 2)
returnsk // 2
value inn1
row.  Next, identify the relationship between the two function.
solve(n, k) = flip_number_from solve(n1, 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 (k1) // 2 + 1
previous_bit = solve(n1, (k1) // 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)
movesn1
disks to the other rod (not the 3rd) while preserving the original order.Then thenth
disk is moved to rod 3.  Now check for smaller input. In this case it refers to a stack of
n1
disks. Sosolve(n1)
, movesn2
disks to the other rod (not the 3rd) and moven1
th disk to rod 3.  Next, identify the relationship between the two functions.
solve(n) = move nth disk to rod 3 + solve(n1)
.  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(n1, from_rod, helper_rod, to_rod)
print(f'Move disk {n} from rod {from_rod} to {to_rod}')
solve(n1, 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 kth
person and repeat till only one person is left.
Hypothesis approach
 Assume the function
solve(n, k)
gives the last remaining person.  Now
solve(n1, k)
gives the last remaining person if there weren1
people.  Next, identify the relationship between the two functions. If we know the winner for
n1
andk
, then the winner ofn
andk
issolve(n,k) = solve(n1,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(n1, k) + k) % n
solve(6, 5) + 1 # Add 1 to convert to 1based 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[0])
# 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
#
Print unique subsets
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):
output_set.add(out)
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], [4], [1, 4], [1]]
Add underscore between characters
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, c1, out + ')')
elif o == c:
solve(o1, c, out + '(')
elif o < c:
solve(o1, c, out + '(')
solve(o, c1, 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 ndigit
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(n1, num_1+1, num_0, out + '1')
elif num_1 > num_0:
solve(n1, num_1+1, num_0, out + '1')
solve(n1, 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 n2 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 listsolve(new_l)
, generate the requirers string the list created fromsolve(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)i1})')
if len(new_l) == 1:
return new_l[0]
return solve(new_l)
n = 8
l = [i for i in range(1, n+1)]
print(solve(l))