Skim through this on exceptions Read through wiki on tower of hanoi as we will be using it a lot this class.
Recursion is the act of a function calling itself. A great example of this is the factorial function in mathematics.
In mathematics, n! (pronounced n factorial) is written as n * (n-1)! where 0! = 1! = 1, so 5! = 5 * 4! = 5 * 4 * 3! = 5 * 4 * 3 * 2! = 5 * 4 * 3 * 2 * 1! = 5 * 4 * 2 * 1 = 120
When we write recursive functions, we usually have a base case of when we should stop, and we want to move towards that base case on every interation of the function.
If we wanted to write a function to compute a factorial, we would write:
def factorial(n):
if n == 1: # our base case
return 1 # return 1 since 1! = 1
else:
return n * factorial(n - 1) # n! = n * (n-1)!As we see here, we have a base case when we stop (when n = 1) and on each interation n gets closer to the base case, assuming the user enters a positive integer.
Lambdas are anonymous functions, or functions that dont have names, they are used when you want to write short one line functions.
To see the usefulness of this, we will expand the concept of arguements in functions, and maybe you've realized this already, but functions can take functions as arguements. Lets look at an example where this would be usefule:
def square(x):
return x*x
def cube(x):
return x*x*x
def sum_from_a_to_b(a,b,function):
currentSum = 0
for x in range(a,b+1):
currentSum = currentSum + function(x)
return currentSum
#now lets use it
print( sum_from_a_to_b(1,10,square) ) # will print the sum of the squares
print( sum_from_a_to_b(1,10,cube) ) # will print the sum of the cubesNow what if we dont want to create a new function like cube that we will only use once, well we can just use a lambda:
print(sum_from_a_to_b(1,10, lambda x: x*x*x) ) #will print the sum of the cubes
In the tower of hanoi there are three towers with N rings on the first one (in ascending order). The goal of the game is to move all the rings to the middle tower. The rules are simple, you may only move one ring at a time and a ring can only be placed on a ring that is larger than itself.
Open up the file for this class and play the game on your terminal/command line to get a feel for the game.
Then try to implement solve, an algorithm that will win the game automatically for you.
In this cipher our key is not a single number, but rather a word or series of numbers. The code is encripted with by cycling through each letter of the code and key at the same time, using a mini caesar cypher on each letter.
For example if our code is 'abc' and our key is '123' then 'a' gets shifted one place, 'b' two and 'c' three, so we get as an output 'bdf'. If our key is shorter than our code we just wrap around and start again. Again 'z' + 1 = 'a'.
Decripting this algorithm is a bit harder, but not impossible. This problem is a bit more advanced and uses frequency analysis and can be implemented with machine learning.