Recursion

• What Is Recursion?
• a function calling itself
• a way of breaking a problem down into smaller and smaller pieces which eventually solve the problem
• a way of repeating code (similar to a loop) so it is a control structure
• it's all of these
• Calculating the Total of a List of Numbers
• define the total of some numbers in a list as the total of (the first element) and (the total of the rest of the list)
• total of the whole list is list[0] + total (list minus the first element)
• reuse the definition but on a smaller argument
• ```	def total(list):
if len(list) == 1:  # base case
elif len(list) == 0: # another base case
else:
answer = list[0] + total(list[1:]) # recursive part
```
• The Three Laws of Recursion
• must have a base case which is NOT recursive (at least one base case, can be more)
• must have a recursive case which calls itself
• the recursive case must move the problem towards the base case
• the base case
• can have more than one "if num == 0 or num == 1:"
• sometimes the base case is just to NOT do anything
```     def fun(num):
if num > 0:
print(num)
fun(num-1)
```
• the order of statements in a recursive function are even MORE important than in other code
• try reversing the two statements inside the if block above
• safer to make sure the base case is tested for FIRST so that you don't fall into the recursive case by accident
• Factorial
• classic recursion example
• n! = n * (n-1) * (n-2) * ... * 1
• n! = n * (n-1)!
• 0! = 1
• 1! = 1
• Factorial
• Converting an Integer to a String in Any Base
• Binary Search
• Stack Frames: Implementing Recursion
• imagine the call stack when a recursive function is executing
• gets taller as the function calls itself
• gets shorter as the base cases execute and return values
• an infinite loop in a recursive function will cause call stack to run out of space (or Python has fixed limit of how tall the stack can be)
• a call stack is made up of the information about the function call which is about to start = parameter values, place for the return value to go when it's found
• also called a 'stack frame'
• Visualizing Recursion