Computer Programming - Courses - Institute of Computer Science

Homework for Week 15

Before the next class session, please read the following material about recursion.

Recursion

Generally, recursion means "defining something in terms of itself". 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 function as it calls itself. When we call this function with a positive integer, it recursively calls itself by decreasing the number. This function call has the name recursive step. At each step the function multiples the number with the factorial of number minus 1 until the number is equal to one. These recursive calls 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 1. As it is not equal to 0, the value 1 is printed and countdown is invoked with argument 0.
    - countdown starts with argument 0. As it is equal to 0, "Blastoff!" is printed.
    - countdown with argument 0 ends its work.
  - countdown with argument 1 ends its work.
- countdown with argument 2 ends its work.
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 the 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 the 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)

Show self-assessment question

Graphical example: drawing fractals

A fractal is a drawing that 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 process on each segment of the pattern? Order 2: we would get the following shape:

Repeating the process 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 that 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:

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 gold 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 gold coins. The third safe is put in a fourth safe together with three new gold 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. Car price

We estimate that every year the car loses 20% of its value compared to last year. Write a recursive function (a function that calls itself) car_price that takes the car's price and the number of years as its argument and returns the car's worth after that number of years. The function must round all returned prices to two decimal places.

>>> car_price (10000.0, 0)
10000.0
>>> car_price (10000.0, 5)
3276.8
>>> car_price (10000.0, 1)
8000.0
>>> car_price (8000.0, 5) # or car_price (10000.0, 6)
2621.44

This problem can also be solved with a while loop or formula, but solving with a recursive function helps understand the meaning of the recursion better.

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 that 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 15 (home1.py, home2.py, and home3.py).

Computer Programming 2020/21 spring