# 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

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

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)$

- 1.Define base cases to terminate the recursion
- 2.Recursion implies using a stack to model the problem so a stack can be used to replace recursive methods
- 3.Recursion is particularly useful for permutation problems

- 1.
`n = 0`

- 2.
`n = 1`

- 3.
`n >= len(arr)`

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 oncedef fn(i, acc):

if i >= len(arr):

ans.append(acc[::])

return

for j in range(i, len(arr)):

acc.append(arr[i])

fn(j + 1, acc)

acc.pop()

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

Storing the result of computations and using them for later computations

- Commonly associated with top-down approach

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

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 elementsLast modified 2mo ago