Published on 6 Nov 2018
School
Department
Course
Professor
ECS 36A - Lecture 8 - Recursions
A recursion is when a function calls on itself in its own definition. This helps expedite certain
processes.
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1) within factorial(n), factorial (n-1) is called
The Tower of Hanoi:
is a classical example involving the redistribution of disks in a new order. Though visualization
helps with this concept, below is a program that reimagines it through code.
def hanoi(n, src, dst, tmp):
if n > 0:
hanoi(n - 1, src, tmp, dst)
move(src, dst)
hanoi(n - 1, tmp, dst, src)
- move src peg to dst peg
- can use tmp peg
def hanoi_(n-1) (src, dst, tmp):
pass
Goals of Recursions
* Explore all states
* Explore all branches
* Create input that cause errors