Programmeerimise alused II - Kursused - Arvutiteaduse instituut

Before session 5

Before the next class session, read the text material about recursion.

Recursion

Generally, recursion means “defining something in terms of itself” usually at some smaller scale, perhaps multiple times, to achieve one's objective. For example, we might say “A human being is someone whose mother is a human being”, 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”. A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.

We know that in Python, a function can call other functions. It is even possible for the function to call itself. These type of construct are termed as recursive functions.

Recursion is often seen as an efficient method of programming since it requires the least amount of code to perform the necessary functions. However, recursion must be incorporated carefully, since it can lead to an infinite loop if no condition is met that will terminate the function.

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 with 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 the procedure of order 1 on each segment of the pattern? Order 2: we’d get the following Koch fractal:

Repeating the procedure again results in 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 order 2 Koch fractals. But each of these in turn needs four order 1 Koch fractals, and each of those in turn needs four order 0 fractals. Ultimately, the only drawing that will take place is 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 thing: if the order is not zero, koch calls itself recursively to get its job done.

Do not forget to call the function for getting the picture, for example koch(3,300). Add speed(10) to speed up the animation and exitonclick() to close the turtle window.

Factorial

Another example on recursion and a recursive function is to find 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 will recursively call itself by decreasing the number. Each function call multiples the number with the factorial of number-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 condition. Every recursive function must have a base condition that stops the recursion (otherwise, the function calls 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 out and countdown is invoked with argument 2.
- countdown starts with argument 2. As it is not equal to 0, the value 2 is printed out and countdown is invoked with argument 1.
  - countdown starts with argument 1. As it is not equal to 0, the value 1 is printed out and countdown is invoked with argument 0.
    - countdown starts with argument 0. As it is equalt to 0, "Blastoff!" is printed out.
    - 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, 134, ... was devised by Fibonacci (1170-1250), who used the sequence to model the breeding of rabbits (pairs). For example, if in generation 7 you had 21 pairs of rabbits, of which 13 were adults, then in some time the adults would all have bred new children, and the previous children would have grown up to become adults. So in generation 8 you’ll have 13+21=34 pairs of rabbits, of which 21 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

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 partially 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 will sum all of the 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.

Let's write our own sum 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]))

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()

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”.

Test

Go to Moodle and take the test on the recursion.

Homework

The deadline for homework is Friday. You should start with homework already before the session.

The deadline is on Thursday, the 8th of December, 23:59 (the final deadline is Friday, the 9th of December, 23:59 Estonian time).

Exercise 1. Fractal

The following image contains examples of a fractal (orders 1, 2, 3, 4 and 5). Write a recursive function which takes the order number and the length of the tree (a tree is the fractal of order 1) as the arguments, and draws the fractal of the corresponding order. Demonstrate the work of your function drawing the fractal of order 5.

Exercise 2. Sum of the first n numbers

Write a recursive function that returns the sum of the first n integers. For example, the sum of the first 6 numbers is 6+5+4+3+2+1=21.

Programmeerimise alused II 2022/23 sügis