Before session 16
Before the next class session, please read the following material about recursion.
Recursion
Generally, recursion means "defining something in terms of itself" at a certain smaller scale. For example, we might say "A man is a child of another man", or "a directory is a structure that holds files and (smaller) directories", or "a family tree starts with a couple who has children, each with their own family sub-trees". An example from the physical world would be two mirrors facing each other. Any object between these mirrors would be reflected recursively.
In computer science, recursion is a process in which a function calls itself. This allows the function to be repeated several times, since the function calls itself during its execution. Functions that incorporate recursion are called recursive functions.
Recursion is often seen as an efficient method of programming since in many cases it requires the least amount of code to perform the necessary functions. However, recursion must be used carefully, otherwise, it can lead to an infinite loop if no condition is met that terminates the function.
Factorial
An example of recursion and recursive function is finding the factorial of an integer. The factorial of a number is the product of an integer and all the integers below it. For example, the factorial of 6 (denoted as 6!) is 6*5*4*3*2*1=720.
def calc_factorial(x):
if x == 1:
return 1
else:
return x * calc_factorial(x-1)
num = 4
print("The factorial of", num, "is", calc_factorial(num))
In the example above, calc_factorial is a recursive functions as it calls itself. When we call this function with a positive integer, it recursively calls itself by decreasing the number. Each function call multiples the number with the factorial of number minus 1 until the number is equal to one. This recursive call can be explained in the following steps:
calc_factorial(4) # 1st call with 4 4 * calc_factorial(3) # 2nd call with 3 4 * 3 * calc_factorial(2) # 3rd call with 2 4 * 3 * 2 * calc_factorial(1) # 4th call with 1 4 * 3 * 2 * 1 # return from the 4th call as number=1 4 * 3 * 2 # return from the 3rd call 4 * 6 # return from the 2nd call 24 # return from the 1st call
Our recursion ends when the number reduces to 1. This is called the base case. Every recursive function must have a base case that stops the recursion, since otherwise the function would call itself infinitely.
Another example: count down
A recursive function does not have to contain a return statement. Here is an example:
from time import sleep
def countdown(n):
if n == 0:
print("Blastoff!")
else:
print(n)
sleep(1) # wait for 1 second
countdown(n-1)
countdown(3)
What happens when we call this function?
- countdown starts with argument 3. As it is not equal to 0, the value 3 is printed and countdown is invoked with argument 2.
- countdown starts with argument 2. As it is not equal to 0, the value 2 is printed and countdown is invoked with argument 1.
- countdown starts with argument 0. As it is not equal to 0, the value 1 is printed and countdown is invoked with argument 0.
- countdown starts with argument 1. As it is equal to 0, "Blastoff!" is printed.
- countdown with argument 0 ends its work.
- countdown with argument 1 ends its work.
- countdown starts with argument 0. As it is not equal to 0, the value 1 is printed and countdown is invoked with argument 0.
- countdown with argument 2 ends its work.
- countdown starts with argument 2. As it is not equal to 0, the value 2 is printed and countdown is invoked with argument 1.
- countdown with argument 3 ends its work.
One more example: Fibonacci numbers
The Fibonacci sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... was devised by Italian mathematician Fibonacci (1170–1250), who used the sequence to model the breeding of rabbits (pairs). For example, if we have 21 pairs of rabbits, 13 of which are adults, then in some time the adults breed new pair of rabbits, and the previous pairs will grow up and become adults. So in next generation, we will have 13+21=34 pairs of rabbits, 21 of which are adults. The rabbit breeding model has a simplifying assumption that the rabbits never die. Scientists often make (unrealistic) simplifying assumptions and restrictions to make some headway with the problem.
If we number the terms of the sequence from 0, we can describe each term recursively as the sum of the previous two terms:
fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2) for n >= 2
This can be easily coded in Python:
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
Graphical example: drawing fractals
A fractal is a drawing which has a self-similar structure, where it can be defined in terms of itself.
Let us start with the most famous fractal – the Koch fractal or Koch snowflake.
Order 0: the Koch fractal starts from a straight line of a given size.
Order 1: instead of drawing just one line, draw four smaller segments as shown below:
What would happen if we repeat this procss on each segment of the pattern? Order 2: we would get the following shape:
Repeating the procss again gives the shape of order 3:
Now let us think about the fractal the other way around. To draw a Koch fractal of order 3, we can simply draw four Koch fractals of order 2. But each of these in turn needs four Koch fractals of order 1, and each of those in turn needs four fractals of order 0. Ultimately, the actual drawing will take place only at order 0. This is very simple to code in Python:
from turtle import *
def koch(order, size):
if order == 0: # The base case is just a straight line
forward(size)
else:
koch(order-1, size/3) # Go 1/3 of the way
left(60)
koch(order-1, size/3)
right(120)
koch(order-1, size/3)
left(60)
koch(order-1, size/3)
The key idea: if the order is not zero, koch calls itself recursively to get the job done.
Last example: one more fractal
from turtle import *
def fractal(order, size):
if order == 1:
forward(size)
else:
forward(size)
left(60)
fractal(order-1, size/3)
backward(size/3)
right(60)
fractal(order-1, size/3)
backward(size/3)
right(60)
fractal(order-1, size/3)
backward(size/3)
left(60)
left(90)
fractal(3, 250)
exitonclick()
Recursive data structures
The organization of data for the purpose of making it easier to use is called a data structure.
We can define a nested number list as follows:
A nested number list is a list whose elements are either:
- numbers
- nested number lists
Notice that the term, nested number list is used in its own definition. Recursive definitions like this are quite common in mathematics and computer science. They provide a concise and powerful way to describe recursive data structures that are composed of smaller and simpler instances of themselves. The definition is not circular, since at some point we will reach a list that does not have any lists as elements.
Now suppose our job is to write a function that sums all values in a nested number list. Python has a built-in function which finds the sum of a sequence of numbers:
>>> sum([1, 2, 8]) 11
For our nested number list, however, sum will not work:
>>> sum([1, 2, [11, 13], 8])
Traceback (most recent call last):
File "<pyshell#1>", line 1, in <module>
sum([1, 2, [11, 13], 8])
TypeError: unsupported operand type(s) for +: 'int' and 'list'
>>>
The problem is that the third element of this list, [11, 13], is a list, which can not be added to 1, 2, and 8.
Therefore, we write a recursive function, which will work with nested lists (recursive data structures) as well:
def oursum(lst):
s = 0
for el in lst:
if isinstance(el, list):
s += oursum(el)
else:
s += el
return s
print(oursum([1, 2, 8]))
print(oursum([1, 2, [11, 13], 8]))
print(oursum([1, [2, 3], [[[[4, 5], 6]]], 7, 8]))
Recursion, mysticism, humor
Recursion is widely used in programming, computer science and mathematics, as well as in linguistics, music, art etc.
For example, Maurice Cornelis Escher (1898–1972) used recursion in the arts.
Some references to cartoons, pictures, concepts related to recursion:
- http://en.wikipedia.org/wiki/Ouroboros
- http://xkcd.com/244/
- www.peteonsoftware.com/images/201108/InfiniteRecursion.jpg
- http://en.wikipedia.org/wiki/Drawing_Hands
- http://en.wikipedia.org/wiki/Recursive_acronym
To sum up: “To understand recursion, you must first understand recursion”.
Quiz
Go to Moodle and solve the quiz on recursion.
Exercises
1. Gold coins
A cold coin is put inside a safe and the safe is closed. Then the safe is put in another, larger safe together with a new cold coin. The second safe is then put in a third safe together with two new cold coins. The third safe is put in a fourth safe together with three new cold coins and so on. (So the first safe is accompanied by 1 coin, the second safe by 2 coins, the third safe by 3 coins etc.)
Write a recursive function number_of_coins that takes safe number as its argument and returns the total number of gold coins in the safe.
>>> number_of_coins(1) 1 >>> number_of_coins(3) 4 >>> number_of_coins(4) 7 >>> number_of_coins(10) 46
2. Levels
Write a function levels that takes a nested list of integers as its argument and replaces each element with it nesting level. The nesting level of a number is defined as the number of brackets that surround that number. The function should not return or print anything, it should only change the given list.
Example 1
>>> a = [17, [69, [25], [[74], 43], 66], 98] >>> levels(a) >>> a [1, [2, [3], [[4], 3], 2], 1]
Example 2
>>> b = [8, [6, 7, [-1], [4, [[10]]], 2], 1] >>> levels(b) >>> b [1, [2, 2, [3], [3, [[5]]], 2], 1]
It can be assumed that all sublists are non-empty.
Hint. At each recursive call, the function probably needs the recursion depth where the execution currently is, to be given as its argument, in addition to the list. To achieve this, define a helper function and call that in the main function:
def levels_helper(lst, depth): # Helper function
. . .
levels_helper( . . . , depth + 1) # Recursive call
def levels(lst): # Main function
levels_helper(lst, 1)
3. Line of descent
Information about family tree is represented by a dictionary, where keys are names of individuals and values are sets of parents of these individuals. For example,
familytree = {
'Kalle': {'Teet', 'Maris'},
'Maris': {'Konstantin', 'Mari'},
'Rita': {'Teet', 'Maris'},
'Siim': {'Teet', 'Maris'},
'Mari': {'Karl', 'Leeni'},
'Teet': {'Joosep', 'Adele'},
'Adele': {'Johannes', 'Leida'},
'Konstantin': {'Viktor', 'Jelena'},
'Joosep': {'August', 'Emma'},
'Viktor': {'Nikolai', 'Maria'}
}
Write a recursive function find_line with three parameters. The first parameter is a family tree dictionary, and the next two parameters are the names of the descendant and the ancestor. The function returns a list which describes the line of descent from the descendant to the ancestor. If no such line exists, then the function should return an empty list.
For example, with the family tree above the function should work as follows:
>>> find_line(familytree, 'Kalle', 'Leida') ['Kalle', 'Teet', 'Adele', 'Leida'] >>> find_line(familytree, 'Adele', 'Mari') []
Submit your solutions
Go to Moodle and upload your solutions under homework for Session 16 (home1.py, home2.py, and home3.py).