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
Last updated
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
Last updated
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
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
n = 0
n = 1
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 once
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 elements