# Recursion

Recursion is quite a typical problem and can be rather tricky to get right on the first go. Try visualizing recursive algorithms by tracing them out on paper with simpler recursions

## Runtime analysis

### Time complexity

The runtime of recursive algorithms can often be determined by looking at the branching factor and using things like master theorem to calculate accurately.

### Space complexity

There is always space used for recursive calls in Python. But in languages with tail-call optimization like Elixir, the space can be $O(1)$

## Take note...

Define base cases to terminate the recursion

Recursion implies using a stack to model the problem so a stack can be used to replace recursive methods

Recursion is particularly useful for permutation problems

## Corner cases

`n = 0`

`n = 1`

`n >= len(arr)`

## Techniques

### Reducing space

Rather than doing `acc + [nums[i]]`

for each recursive call (this creates a new array every time), use `.append()`

before the recursive call and `.pop()`

after. Then, when a base case is reached, use `acc[::]`

to duplicate the array just once

### Memoization

Commonly used to optimize repeated computations. The memoization stores the result of a branch and allows future calls to that branch to re-use the memoized values instead of performing the computation again

Commonly associated with bottom-up approach

### Tabulation

Storing the result of computations and using them for later computations

Commonly associated with top-down approach

### Converting to iterative

Store the previous iteration's answer and use it as the basis for the next iteration, performing operations to modify it

Base case is usually

`[]`

but it may vary

### Dealing with duplicates

Duplicate values can be particularly annoying to deal with because they can cause repeated and wrong computation. To resolve this, rather than iterating over the entire array directly, iterate over a frequency map of the elements, controlling how many elements appear in each recursive call

Particularly useful for problems like Combination Sum 2 where the duplicates can cause overcounting if naively recursed

For questions about **permutations** where the order of the elements matter, we can continue to use the above strategy or create an auxiliary array that maintains the order of the elements so that the first `1`

cannot be used after the second `1`

, thus enforcing the order of the elements

Last updated