Recursion/Tree Recursion Quick Review

Recursive Function = Any function that calls itself

Tree Recursion = Having multiple recursive calls, each representing a different option (i.e. whether or not to add a number to a sum or not, or whether to step up one step or two steps)

Base Case = Simplest case for the function, and the case in which you don’t call the function recursively (you can have more than one base case sometimes)

Recursive Case = Case in which you call your function recursively

Three steps to writing a recursive function:

  1. Create base case(s)

  2. Reduce your problem to a smaller subproblem and call your function recursively on the smaller subproblem

  3. Figure out how to get from the smaller subproblem back to the larger problem

Real-world analogy for Recursion

Recursion can feel a little abstract, so here’s kind of a real-world example that will hopefully help make the concept a little more clear.

Imagine that you’re in line for boba, but the line is really long (of course), and so you want to know what position you’re in. The line is too long for you to see how many people are in front of you, and you don’t want to step out of line to count the number of people in front of you, because then you’ll lose your place in line. Instead, what you decide to do is ask the person in front of you how many people are in front of them; that way, you can take their response and add 1 to it. Now, the person in front of you is faced with the same problem that you were trying to solve, just with a slightly smaller number of people in front of them (specifically, they have one less person in front of them than you do). They decide to take the same approach that you did, by asking the person in front of them. This continues until the very first person in line is asked how many people are in front of them. At this point, the person at the front knows that there are 0 people in front of them, so they can tell the person behind them that there are 0 people in front. Now, the second person can figure out that there is 1 person in front of them, and can relay that back to the person behind them, and so on, until the answer reaches you. At this point, you are going to trust that the answer given to you by the person in front of you is correct, and you can add 1 to that number, and have your answer.

Looking at this example, we can see that the “recursive function” is trying to figure out how many people are in front of you, given your position in line. The base case is if you are in position 1 (since then there are 0 people in front of you, and you don’t have anyone to ask in front of you). The recursive case is if you are in any position greater than 1, since then you can “recursively ask” the person in front of you (which is our smaller subproblem!) Finally, we can get from the smaller subproblem back to the big problem by adding 1 to the number from the person in front if you, since you have to include them in your count.

NOte about base cases

Sometimes, you may find it easier to write the recursive case and then build your base case off of the recursive case, as opposed to writing your base case first. That also works! Just remember, if you get stuck on a recursion problem on an exam, you can often get a lot of partial credit for figuring out the base case, even if you can’t fully figure out the recursive case.