---
# System prepended metadata

title: Recursion
tags: [Data Structures & Algorithms, GeeksforGeeks]

---

# 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
``` python
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)
``` python
def sum_n(n):
    if n == 0:
        return
    return n + sum_n(n - 1)
```
- reverse a string
``` python
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
``` python
def sum_digits(n):
    if n <= 0:
        return 0
    return n % 10 + sum_digits(n // 10)
```
- factiorial of n
``` python
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)
``` python
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)
``` python
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)
``` python
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??
``` python
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)
``` python
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
``` python
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
