Recursion
- 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
- a recursive algorithm must have a base case
- a recursive algorithm must change its state and move towards the base case
- 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.') return 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)) bottles_of_beer(bob)
- if statement satisfies 1st law
bob -= 1
satisfies 2nd law- calling
bottles_of_beer(bob)
insidebottles_of_beer(bob)
satisfies 3rd law
- example in Python:
def print_to_zero(n): if n < 0: return print(n) print_to_zero(n-1)
- here the 2nd law is satisfied by the
n-1
argument given to the function inside the function
- here the 2nd law is satisfied by the