I have to say, So far Recursion has been the most interesting topic for me we have came across in CSC148! and the fact that we could do something like
Minimax, using recursion makes it even cooler. doing something so powerful with something that gets easier and easier with more practice!
To be honest it was really hard for me to get my head around the whole idea of recursion and I would get really confused about how the base cases and the whole idea of calling the function in itself. But lab after lab if got more clear!
I loved the idea of the simple game of Subtract Square and the not so easy Tippy we did you our two assignments! and the Minimax strategy just makes everything better in there. I really wanted to do a Tic-Tac-Toe game, I will share the code with you at the end of this slog, but unfortunately I can't share the Minimax code since we still have not handed in our work for the assignment.
Ok getting back to recursion! since we are getting marked on this entry, I though it's better to do a summary of recursion and what we have thought with some examples.
What is Recursion?
Recursion in
computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to
iteration).
[1]The approach can be applied to many types of problems, and
recursion is one of the central ideas of computer science.
[2]
"The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions."
[3] (from wikipedia)
a simple example would be the factorial in mathematics! we know that every term can be achieved by multiplying it with the factorial of the integer before it! that's what makes the factorial recursive!
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
The two key elements of a recursive algorithm are:
- The termination condition:
n == 0
- The reduction step where the function calls itself with a smaller number each time:
factorial(n - 1)
If you are on of the students taking MAT137, you have felt that great feeling when the instructor is talking about Recursive sequences and nobody knows what they are talking about except you!
Another example of recursive things in mathematics could be the pascal's triangle.
Pascal's triangle is the BOMB for us computer scientists! If you don't know about it
check this link out!
I also want to post some of the lab exercises on trees, BT trees for you here, they are probably going to take a bunch of space but I will try to post them regularly for you
But first things first, here is the code for the tic-tac-toe game;
TIC-TAC-TOE:
import random
new = ['','','','','','','','','']
man = ''
machine = ''
null = ''
def sign(man, machine):
man = input("What team you want to be? X or O ")
while man not in ('x','X','o','O'):
print ("Invalid Choice!")
man = raw_input("What team you want to be? X or O ")
if man == 'x' or man == 'X':
print ("Ok, X is yours!")
machine = 'o'
else:
print ("Ok, O is yours!")
machine = 'x'
return man.upper(), machine.upper()
def decide_turn():
turn = None
while turn not in ('y','Y','n','N'):
turn = input("Do you want to go first? ")
if turn == 'y' or turn == 'Y':
return 1
elif turn == 'n' or turn == 'N':
return 0
else:
print ("its an invalid choice.")
def draw(a):
print ("\n\t",a[0],"|",a[1],"|",a[2])
print ("\t", "--------")
print ("\n\t",a[3],"|",a[4],"|",a[5])
print ("\t", "--------")
print ("\n\t",a[6],"|",a[7],"|",a[8], "\n")
def congo_man():
print ("You won!!")
def congo_machine():
print ("Hahha, I won!!!")
def man_first(man, machine, new):
while winn(man, machine, new) is None:
move = man_move(man, new)
new[int(move)] = man
draw(new)
if winn(man, machine, new) != None:
break
else:
pass
print ("ummmm....i'll take..")
p_move = machine_move(man, machine, new)
print (p_move)
new[int(p_move)] = machine
draw(new)
q = winn(man, machine, new)
if q == 1:
congo_man()
elif q == 0:
congo_machine()
else:
print ("Its tie man...")
def machine_first(man, machine, new):
while not winn(man, machine, new):
print ("i'll take...")
p_move = machine_move(man, machine, new)
print (p_move)
new[p_move] = machine
draw(new)
if winn(man, machine, new) != None:
break
else:
pass
move = man_move(man, new)
new[int(move)] = man
draw(new)
q = winn(man, machine, new)
if q == 1:
congo_man()
elif q == 0:
congo_machine()
else:
print ("It's a tie man...")
def winn(man, machine, new):
ways = ((0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6))
for i in ways:
if new[i[0]] == new[i[1]] == new[i[2]] != null:
winner = new[i[0]]
if winner == man:
return 1
elif winner == machine:
return 0
if null not in new:
return 'TIE'
if null not in new:
return 'TIE'
return None
def man_move(man, new):
a = input("where you want to move? ")
while True:
if a not in ('0','1','2','3','4','5','6','7','8'):
print ("Sorry, invalid move")
a = input("where you want to move? ")
elif new[int(a)] != null:
print ("Sorry, the place is already taken")
a = input("where you want to move? ")
else:
return int(a)
def machine_move(man, machine, new):
best = [4, 0, 2, 6, 8]
blank = []
for i in range(0,9):
if new[i] == null:
blank.append(i)
for i in blank:
new[i] = machine
if winn(man, machine, new) is 0:
return i
new[i] = null
for i in blank:
new[i] = man
if winn(man, machine, new) is 1:
return i
new[i] = null
return int(blank[random.randrange(len(blank))])
def display_instruction():
""" Displays Game Instuructions. """
print
("""
Welcome to the Game...
You will make your move known by entering a number, 0 - 8.
The will correspond to the board position as illustrated:
0 | 1 | 2
-----------
3 | 4 | 5
-----------
6 | 7 | 8
Prepare yourself, the ultimate bettel is about to begin.....
"""
)
def main(man, machine, new):
display_instruction()
print ("so lets begin..")
a = sign(man, machine)
man = a[0]
machine = a[1]
b = decide_turn()
if b == 1:
print ("Ok, you are first!")
print ("Lets get started, here's a new board!")
draw(new)
man_first(man, machine, new)
elif b == 0:
print ("Ok, I'll be the first!")
print ("So, lets start..")
draw(new)
machine_first(man, machine, new)
else:
pass
main(man, machine, new)
input("Press enter to exit")
