Introduction to Recursion
Factorial Function by Iteration
# factorial.py
def factorial(number):
answer = 0
for i in range(1, number + 1):
answer = answer * i
return answer
print(factorial(3)) # returns 6
print(factorial(7)) # returns 5040
Factorial Function by Recursion
# factorial.py
def factorial(number):
if number == 0: # 0 is the base case that ends the recursion
return 1
else:
return number * factorial(number - 1) # the recursive function call
print(factorial(3)) # returns 6
print(factorial(7)) # returns 5040
Fibonacci Sequence by Recursion
#fibonacci.py
def fib(number):
if number == 0:
return 0
elif number == 1:
return 1
else:
return fib(number - 1) + fib(number - 2)
for number in range(10):
print(number, fib(number))
Towers of Hanoi
# hanoi.py
def hanoi(discs, start_peg, middle_peg, goal_peg):
'''Print solution to Towers of Hanoi with any number of discs.'''
if discs >= 1:
# move tower of size n - 1 to middle_peg
hanoi(discs - 1, start_peg, goal_peg, middle_peg)
# move base disc from start_peg to goal_peg
print("Move disc", discs, "from peg", start_peg, "to peg", goal_peg)
# move tower from middle_peg to goal_peg
hanoi(discs - 1, middle_peg, start_peg, goal_peg)
hanoi(4, "A", "B", "C")
Homework:
Answer the following questions in a file called hw9-1_yourname.py and submit it to the assignment in the Portal (due at the beginning of class tomorrow). #1-3 are required; everyone should attempt the Challenge Problem.
-
What is a base case in recursion?
-
Why is a base case essential when using recursion?
-
What will happen when this recursive function runs? Correct it to make it work correctly.
def factorial(number):
if number == 0:
return 1
else:
return number * factorial(number)
print(factorial(3))
Challenge Problem:
Write a recursive function that sums the squares of integers from 1 to the number given. For example, if 5 is passed into the function, the function would return the value of 1^2 + 2^2 + 3^2 + 4^2 + 5^2.