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)

Three steps to writing a recursive function:

  1. Create base case(s) (base case = simplest case for the function, and the case in which you don’t call the function recursively)

  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