#!/usr/bin/env python
# coding: utf-8

# # 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 <em>call themselves</em> to solve smaller subproblems
# - fractals is a drawing which also has self-similar structure, where it can be defined in terms of itself
# 
# ## Definitions
# <strong>Recursion: </strong> The process of solving a problem by reducing it to smaller versions of itself is called recursion. <br>
# <strong>Recursive definition: </strong> a definition in which something is defined in terms of smaller version of itself. <br>
# <strong>Recursive algorithm:</strong> an algorithm that finds a solution to a given problem by reducing the problem to smaller versions of itself<br>
# <strong>Infinite recursion:</strong> 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
# <pre>
# 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
# </pre>

# 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
# <pre>
#     0! = 1 - base case
#     n! = n.(n-1)! for n >= 1 - general case
# </pre>

# ### exercise 1
# Write a recursive fact(n) function that takes a positive integer n and returns its factorial.
# <pre>
# 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)
# </pre>

# ### exercise 2
# Write a recursive function -- gcd(a, b) -- that finds the greatest common divisor of two given positive integers, a and b.
# <pre>
# 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
# </pre>

# ### 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[ ]: