Objectives
- Define recursion
- Implement a recursive algorithm
- Recognize recursive functions
- Compare and contrast iteration and recursion
Overview
- Recursion is when a function calls itself either directly of indirectly
- Recursion can be replaced by iteration (and vice-versa)
- Recursion is often easier to code when we have a recursive formula
- Recursion often takes up more computer resources than iteration
Recursive factorial
def fact(n): if n < 0: return None elif n < 2: return 1 else: return n * fact(n-1) fact(5) # displays 120 fact(0) # displays 1 fact(6) # displays 720
Recursive greatest common divisor
def gcd(a,b): if a == 0: return b else: return gcd(b % a, a) gcd(15, 7) # returns 1 gcd(15, 5) # returns 5 gcd(14, 42) # returns 14
Recursive Fibonacci
def fib(n): if n < 0: return None elif n < 2: return n else: return fib(n-1) + fib(n-2) for i in range(-1, 11): print(fib(i)) # displays: None, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55
Recursive conversion of base 10 to base 2
def isInt(s): """ Determines if the argument value represents an integer value """ try: i = int(s) if isinstance(s, str): return i == float(s) else: return i == s except: return False def convertDecimalToBinary(n): if not isInt(n) or int(n) < 0: return None else: n = int(n) if n == 0: return "" else: return convertDecimalToBinary(n//2) + str(n % 2) print(convertDecimalToBinary("")) # displays: None print(convertDecimalToBinary(-5)) # displays: None print(convertDecimalToBinary(32.6)) # displays: None print(convertDecimalToBinary(57)) # displays: 111001 print(convertDecimalToBinary("57")) # displays: 111001 print(convertDecimalToBinary("Bob")) # displays: None
Recursive string reversal
def strrev(s): if len(s) > 0: for c in s: return strrev(s[1:]) + c else: return "" strrev("Python") # returns "nohtyP"
Recursive Towers of Hanoi
def hanoi(disks, fromPole, toPole): """Poles are numbered 1, 2, 3. Disks is number of disks to be moved.""" tempPole = 6 - fromPole - toPole if disks < 1: return if disks > 1: hanoi(disks-1, fromPole, tempPole) print("Move 1 disk from pole {0} to pole {1}".format(fromPole, toPole)) if disks > 1: hanoi(disks-1, tempPole, toPole) hanoi(0, 1, 3) # displays nothing (no moves to be made) hanoi(2, 1, 3) # displays the following: # Move 1 disk from pole 1 to pole 2 # Move 1 disk from pole 1 to pole 3 # Move 1 disk from pole 2 to pole 3 hanoi(3, 1, 3) # displays the following: # Move 1 disk from pole 1 to pole 3 # Move 1 disk from pole 1 to pole 2 # Move 1 disk from pole 3 to pole 2 # Move 1 disk from pole 1 to pole 3 # Move 1 disk from pole 2 to pole 1 # Move 1 disk from pole 2 to pole 3 # Move 1 disk from pole 1 to pole 3