Notebook

Recursion¶

defining something in terms of itself usually at some smaller scale, perhaps multiple times, to achieve your objective
e.g., a human being is someone whose mother is a human being
directory is a structure that holds files and (smaller) directories, etc.
in programming, functions can generally call themselves to solve smaller subproblems
fractals is a drawing which also has self-similar structure, where it can be defined in terms of itself

Definitions¶

Recursion: The process of solving a problem by reducing it to smaller versions of itself is called recursion.
Recursive definition: a definition in which something is defined in terms of smaller version of itself.
Recursive algorithm: an algorithm that finds a solution to a given problem by reducing the problem to smaller versions of itself
Infinite recursion: never stops

general construct of recurive algorithms:¶

recursive algorithms have base case(s) and general case(s)
base case(s) provides direct answer that makes the recursion stop
general case(s) recursively reduces to one of the base case(s)

recursive countdown example¶

In [ ]:

# Recursively print countdown from 10-1 and blast off!
# Run it as a script
import os
import time
def countDown(n):
    os.system('clear')
    if n == 0:
        print('Blast Off!')
        time.sleep(1)
        os.system('clear')
    else:
        print(n)
        time.sleep(1)
        countDown(n-1) # tail recursion
        #print(n)
        

In [ ]:

countDown(10)

Fibonacci numbers¶

Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
devised by Fibonacci (1170-1250), who used the sequence to model the breeding of (pairs) of rabbits
say in generation 7 you had 21 pairs in total, of which 13 were adults, then in next generation the adults will have bred new children, and the previous children will have grown up to become adults. So, in generation 8, you'll have 13+21=34 rabbits, of which 21 are adults.

Fibonacci number definition¶

fib(0) = 0 - base case 1
fib(1) = 1 - base case 2
fib(n) = fib(n-1) + fib(n-2) for n >= 2 - general case

In [ ]:

# In Python:
#count = 0
def fib(n):
    global count
    #count += 1
    if n <= 1:
        return n
    f = fib(n-1) + fib(n-2)
    return f

In [ ]:

fib(10)
#print(count)
#assert fib(8) == 21
#assert fib(10) == 55

visualize fib(4) using pythontutor.com¶

https://goo.gl/YNizhH

In [ ]:

from IPython.display import IFrame
src = """
http://pythontutor.com/iframe-embed.html#code=%23%20In%20Python%3A%0Adef%20fib%28n%29%3A%0A%20%20%20%20if%20n%20%3C%3D%201%3A%0A%20%20%20%20%20%20%20%20return%20n%0A%20%20%20%20f%20%3D%20fib%28n-1%29%20%2B%20fib%28n-2%29%0A%20%20%20%20return%20f%0A%20%20%20%20%0Aprint%28fib%284%29%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=false&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false
"""
IFrame(src, width=900, height=300)

how many times is fib() called for fib(4)?¶

Modify fib to count the number of times fib gets called.

Factorial definition¶

    0! = 1 - base case
    n! = n.(n-1)! for n >= 1 - general case

exercise 1¶

Write a recursive fact(n) function that takes a positive integer n and returns its factorial.

Here are some test cases that the fact(n) should pass:
assert fact(5) == 120
assert fact(10) == 3628800
assert fact(100) == math.factorial(100)

exercise 2¶

Write a recursive function -- gcd(a, b) -- that finds the greatest common divisor of two given positive integers, a and b.

Here are some test cases that gcd(a, b) should pass:
assert gcd(2, 100) == 2
assert gcd(50, 10) == 10
assert gcd(125, 75) == 25

exercise 3¶

Write a program that simulates the steps required to solve the "Tower of Hanoii" puzzle for some disks n.

https://www.mathsisfun.com/games/towerofhanoi.html
Recursive algorithm
If there are 1 or more disks to move:
1. Move the top n-1 disks from needle 1 (source) to needle 2 (helper), using needle 3 (dest) as the intermediate needle
2. Move disk number n from needle 1 to needle 3
3. Move the top n - 1 disks from needle 2 to needle 3, using needle 1 as the intermediate needle

In [ ]:

def moveDisks(n, src, helper, dst):
    if n > 0:
        moveDisks(n-1, src, dst, helper)
        print('Move disk #{} from {} to {}'.format(n, src, dst))
        moveDisks(n-1, helper, src, dst)

In [ ]:

moveDisks(3, 'needle1', 'needle2', 'needle3')

In [ ]: