Programmeerimine 2022/23 kevad

Homework for Week 15

Recursion

Recursion is a very powerful way of writing programs, often allowing to shorten a long program to a few lines. Many standard algorithms in computer science are recursive, where recursion act as a bridge between the theoretical world and program. Using recursion may require a different way of thinking, but the practical benefits are worth it.

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 the number minus 1 until the number becomes 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 pairs 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)

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 repeated this process on each pattern segment? 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

Run the program. Do you understand why the shape of the figure is like it is?

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 to make 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:

1. numbers
2. 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:

For our nested number list, however, sum will not work:

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

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.

2. Fractal

Using the turtle module, write a recursive function that draws the following picture:

Stop the recursion when the length of the line reaches one pixel.

Hint. Each subsequent dash is √2 times smaller than the previous one.

Autotester exists but does not check the correctness of the output image.

Submit your solutions

Go to Moodle and upload your solutions under homework for Session 15 (home1.py and home2.py).

Advice

First, solve the problem. Then write the code.