b.stefanuk.caRecursion
- Recursion is an approach to problem solving where the final solution can be partially obtained by solving smaller problems of a similar structure.
- **Any recursive function consists of one or more *base cases*, and call(s) to the function itself with its arguments changed.
- It is worth repearing that these are the two essential keys of a recursive function: establishing correct base cases, and ensuring that the recursion eventually converges to a solution.
- Some divide and conquer algorithms and dynamic programming algorithms are best solved using recursion (but not always, don't force it). It depends on whether the sub-problems are independent or if there are single or mutiple sub-problems to be solved.Tip
- Recursion is often a good choice for searching, enumeration, or divide-and-conquer solutions
- Recursion is a good alternative when the input is expressed using recursive rules such as computer grammar.
- Recursion is a good alternative when you are working with deeply nested iteration loops, or when you have an undefined number of levels.
- If you need to remove recursion from a program, use a library stack data structure to minic the implicit call stack
- If you need to use a recursive funciton with the same arguments, make sure to cache them, this is a core idea behind Dynamic Programming
[! Note] Tips
- What is the base case? mark it with
return- How are you changing the data so the search space is smaller?
- How are you interacting with the call stack?
Redo all of these problems!
15.1 Tower of Hanoi Problem
I failed this problem... tried it set it up but just got confused about base cases and how to establish all the conditions. This is a difficult problem. While I did pick up on the solution in theory, coding it was the difficulty. The trick to this one is figuring out the base case, which itself is tricky. The first recursion pass you need to move from all rings down to moving just the first ring. Once you've done this, you move the second ring to the open slot which wasn't used in the first move. But you aren't doen yet, you then have to move the 1 ring on top of the 2 ring, which requires another recursive call, because once you're at 3 ring or greater, then you have to put 2 ring back on the stack and then again operate on 1 ring, moving it over. It's all very complicated.
- Again, think of the call stack, you want the largest items to be moved last, so you have to start with them, moving smaller rings onto the stack and then operating on them when it comes time.
- The key is to keep track of where you just moved items to and from, whichever peg you just moved from and to, use the remaining peg, because that one has the item that's smaller (and usable) as the from peg, keeping the to peg the same.
15.2 Non-attacking queens
- construct a board
[0,0], [0,1], ... [0,N], ..., [N,0], ..., [N,N]withboard = [[x,y] for x in range(N) for y in range(N)] - I did get the concept that we are supposed to use rows, and handle items with a guess and check strategy
- I overcomplicated the solution though. Only needed 4 slots. Since we KNOW that there are only one items in each row
The trick for this one is to make assumption about where an item could go, and then test against violations. The logic for checking whether a spot has a violation, and gets a bit tricky.
15.3 Generate permutations
- Another tough one for me. Recursion tasks are difficult for me.
- The key insight for this question was that you had to loop within the recursive function and alter the search space each iteration by only looping over the remaining elements for each permutation.
Think of the call stack when working with recursion, and understand how this branches into a visual tree-like structure. When you have a binary tree, for example, there are only two options and it's easy to make all the calls, but with a N-ary tree, all of the branches may have to be handled in a for loop.
ADDITIONAL RESOURCES Mastering recursive programming