# Recursion

### Concepts
- when function or method calls itself directly or indirectly
- bigger problem is defined as smaller subproblem
- problems inherently recursive in nature for those problems it is ideal like tree problems

### Types
- Interative method
- Recursion (mathatical notation)

### Special Case
- tail recursion - SC - O(1) else SC - O(n) should be last thing program should do not just last line

### Components
- recursive function
- basecase.. generic case or sub problem you already know the answer... needed or else it will go till infinity
- recursion tree or execution stack
- backtracking

### Important concepts
- basecase
- recurrence relation
- relation between result of the problems and subproblem

### Importance of recursion
- Many algorithm techniques are based on recursion
- dynamic programming
- backtracking
- divide and conquer (binary search, quick sort, merge sort)
- Many problems are inherently recursive
- Tower of Hanoi
- DFS based traversals

### Problems
- print from 1 to n and n to 1

def one_n(n):
    if n == 0:
        return
    one_n(n - 1)
    print(n)
    
def n_one(n):
    if n == 0:
        return
    print(n)
    one_n(n - 1)

- sum from 1 to n -> n + sum (1...n - 1)

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

- reverse a string

def reverse(msg, i):
    if i >= len(msg):
        return ''
    return msg[i] + reverse(msg, i + 1)

- check for palindrome
- reverse a string and check inital and reversed string are same
- sum of digits

def sum_digits(n):
    if n <= 0:
        return 0
    return n % 10 + sum_digits(n // 10)

- factiorial of n

def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1)

- given the rod of lengh n you have to cut this rod into maximum number of pieces
- eg 7, [2, 3, 5]
- TC - number rod legth ^ n
- SC - O(rod length)

def rod_cutting(rod_length, lengths):
    if rod_length < 0:
        return None
    if rod_length == 0:
        return 0
    result = 0
    for item in lengths:
        current = rod_cutting(rod_length - item, lengths)
        if current is not None:
            result = max(result, current + 1) 
    return result

- given the rod of lengh n you have to cut this rod, each piece contains price and need to max the price
- eg 7, [2, 3, 5] [100, 5, 500]
- TC - rod length ^ n
- SC - O(rod length)

def rod_cutting_price(rod_length, lengths, prices):
    if rod_length < 0:
        return None
    if rod_length == 0:
        return 0
    result = 0
    for i in range(len(lengths)):
        item = lengths[i]
        price = prices[i]
        current = rod_cutting_price(rod_length - item, lengths, prices)
        if current is not None:
            result = max(result, current + price) 
    return result

- Generate Subsets or subsequences or powerset of a string
- eg AB = '', A, B, AB
- eg ABC = '', A, B, C, AB, BC, AC, ABC
- Note: subsets are generated by skipping charecters and order of charecters are not changed
- 2 ^ n - number of subsets
- Note: at each recursion include or dont inlcude a charecter
- TC - O(2 ** n)
- SC - O(length of string)

def subsets(input, current = '', h = 0):
    if h == len(input):
        print (current, end=' ')
        return
    subsets(input, current + input[h], h + 1)
    subsets(input, current, h + 1)

- subset sum - count the number of subsets equals to the given sum
- Optimize using backtracking??
- Optimize using dynamic programming??

def subsets(input, k, h = 0):
    if h == len(input):
        if k == 0:
            return 1
        else:
            return 0
    return subsets(input, k - input[h], h + 1) + subsets(input, k, h + 1)

- print all permutations of string
- example = ABC = ABC, ACB, BAC, BCA, CAB, CBA
- n! permutations
- TC - O(n!) - without printing - O(n*n!) - with printing
- SC - O(n)

def print_permutations(input, i = 0):
    if i == len(input) - 1:
        print(''.join(input), end = ' ')
        return
    
    for j in range(i, len(input)):
        input[j], input[i] = input[i], input[j]
        print_permutations(input, i + 1)
        input[i], input[j] = input[j], input[i]

- Fibonacci

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 2) + fib(n - 1)

- Tower of Hanoi
- Josephus Problem
- pascals trangle value
- reverse linked list
- swap pairs
- reverse string inplace
- search binary tree