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
    			answer =  list[0]
                    elif len(list) == 0: # another base case
         			answer = 0
    		else:
    			answer = list[0] + total(list[1:]) # recursive part
       		return answer
    

• 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
  • fractal tree
  • Sierpinski Triangle
  • tree drawn by turtle
  • tree drawn by turtle