• method of breaking up problem into smaller and smaller problems until it can be easily solved
  • while iterative algorithms use loops, recursive algorithms rely on functions that call themselves
  • any problem that can be solved iteratively can be solved recursively
    • sometimes recursive is more elegant

Three Laws of Recursion

  1. a recursive algorithm must have a base case
  2. a recursive algorithm must change its state and move towards the base case
  3. a recursive algorithm must call itself, recursively

Recursive Algorithm

  • written inside a function
  • must have a base case
    • a condition that ends a recursive algorithm to stop it from continuing
  • inside the function, the function calls itself
  • each time it calls itself it grows closer to the base case
  • when the base case condition is satisfied the problem is solved and the function stops calling itself
  • example in Python:
    def bottles_of_beer(bob):
        if bob < 1:
            print('No more bottles of beer on the wall. No more bottles of beer.')
        tmp = bob
        bob -= 1
        print('{} bottles of beer on the wall. {} bottles of beer. Take one
                down, pass it around, {} bottles of beer on the wall.'.format(tmp, tmp, bob))
    • if statement satisfies 1st law
    • bob -= 1 satisfies 2nd law
    • calling bottles_of_beer(bob) inside bottles_of_beer(bob) satisfies 3rd law
  • example in Python:
    def print_to_zero(n):
        if n < 0:
    • here the 2nd law is satisfied by the n-1 argument given to the function inside the function

Copyright © 2022