#!/usr/bin/env python
#
#  recursion.py
#~ Recoded By Dan Gau

def main():
	print("Answer is ",rec1(3,5))
	print("2^5 = ",power(2,5))
	print("1+2+..+100 ",summ(100))
	printChart(.15, 20, 40)
	Towers(4, 3, 2)
	
	array = [];
	for i in range(50):
		array.append(5*i)
	for i in range(20,40):
		if (binSearch(array, 0, len(array), i)):
			print("Found ",i)
		else:
			print(i," is NOT in the array")
	return 0


#~ This was just used for a tracing question. It doesn't really
#~ do anything meaningful but calculate (n+1)m
def rec1(n, m):
	if (n == 0):
		return m
	elif (m == 0):
		return n
	else:
		return m +rec1(n-1, m)


#~ Calculates base raised to the exp power, exp must be non-negative.
def power(base, exp):
	if (exp == 0):
		return 1
	elif (exp == 1):
		return base
	else:
		return base*power(base, exp-1)


#~ Calculates 1+2+3+...+n
def summ(n):
	if (n == 1):
		return 1
	else:
		return n + summ(n-1)


#~ Prints a tip chart with a tip rate of rate, starting with
#~ a dollar value of low and ending with a dollar value of high
def printChart(rate, low, high):
	if (low <= high):
		print(low,"  ",low*rate)
		printChart(rate, low+1, high)


#~ Prints the moves necessary to solve the Towers of Hanoi problem
#~ for n disks being moved from tower start to tower end. The towers
#~ are numbered 1, 2 and 3.
def Towers(n, start, end):
	if (n > 0):
		middle = 6 - start - end
		Towers(n-1, start, middle)
		print("Move disk ",n," from tower ",start," to tower ",end)
		Towers(n-1, middle, end)

#~ Determines whether or not target is store in the array vals in between
#~ index low and index high.
def binSearch(vals, low, high, target):
	if (low > high):
			return False
			
	mid = (low+high)//2
	
	if (target > vals[mid]):
		return binSearch(vals, mid+1, high, target)
	elif (target < vals[mid]):
		return binSearch(vals, low, mid-1, target)
	else:
		return True


if __name__ == '__main__':
	main()