We have just discussed Fibonacci numbers, which are defined in the following way (if we number them starting from 0, as all programmers do): $$ \begin{array}{l} f_n = 1, 0\le n\le 1 \\ f_n = f_{n-1} + f_{n-2}, \quad n\ge2\\ \end{array} $$
We have used some clever trick to compute them, having two variables:
def fib(n):
c,p = 1,1
for _ in range(n):
c,p = c+p,c
return p
fib(10)
89
However, we may also define the same function in another way, very similar to the mathematical definition of Fibonacci number given above:
def fib(n):
if n<=1:
return 1
else:
return fib(n-1) + fib(n-2)
fib(10)
89
You may be surprised: how is it possible to use the function fib
inside its own definition? In face, such technique is called recursion, and it often used in programming.
Let us consider the example of calculating fib(3)
. Recursion works as follows:
fib(3)
, the function calls fib(2)
and fib(1)
fib(2)
is called, it calls fib(1)
and fib(0)
.return 1
(because the argument n
is less than 2)fib(2)
is computed as 1+1=2
fib(1)
is called in step 1, it also returns 1 (as in step 3)fib(3)
is computed to be equal to 2+1=3
.We can actually add some print
operators to the function to see how those calls are made:
def fib(n):
print(f'Calling fib({n})')
if n<=1:
print(f'fib({n}) returns 1')
return 1
else:
f1 = fib(n-1)
f2 = fib(n-2)
print(f'fib({n}) returns {f1+f2}={f1}+{f2}')
return f1+f2
fib(3)
Calling fib(3) Calling fib(2) Calling fib(1) fib(1) returns 1 Calling fib(0) fib(0) returns 1 fib(2) returns 2=1+1 Calling fib(1) fib(1) returns 1 fib(3) returns 3=2+1
3
You may notice that during those computations fib(1)
is called twice. In fact, if you try to compute fib
for any number larger than 20, you may notice significant delay - that is because number of calls to function fib
increases very rapidly. For example, to compute fib(16)
we would need to make aroung 65000 calls, while during our previous algorithm with a loop we need to repeat the loop only 16 times.
This does not necessarily mean that recursion is bad. Sometimes it is not easy to program an algorithm without recursion, as we will see in the next example. However, if you can think of a non-recursive way to solve the problem - you should prefer it, because it is likely to be more effective. However, recursive algorithms often tend to be shorter and more beautiful.
The best graphical example of recursion is a Koch Snowflake, which looks like this:
Image from Wikipedia, CC BY-SA 3.0
This picture shows snowflakes of different complexities:
You probably recognized recursion in this algorithm:
The function to draw Koch Curve will look like this:
# Run this cell if you are using the tutorial via Google Colab
!pip install jturtle
import jturtle as turtle
def koch_curve(n,x):
if n==0:
turtle.forward(x)
else:
koch_curve(n-1,x/3)
turtle.left(60)
koch_curve(n-1,x/3)
turtle.right(120)
koch_curve(n-1,x/3)
turtle.left(60)
koch_curve(n-1,x/3)
turtle.right(90)
koch_curve(2,100)
turtle.done()
Let's draw Koch curvers with different $n$-s:
turtle.right(90)
for n in range(4):
koch_curve(n,100)
turtle.penup()
turtle.forward(-100)
turtle.right(90)
turtle.forward(40)
turtle.left(90)
turtle.pendown()
turtle.done()
Finally, to produce Koch's Snowflake, we need to draw 3 Koch curves:
def koch_snowflake(n,x):
for _ in range(3):
koch_curve(n,x)
turtle.right(120)
koch_snowflake(3,100)
turtle.done()
A very similar figure to Koch Snowflake is called Minkowski Island, or Quadratic Koch Curve. The idea is similar, but instead of turning 60 degrees - we turn 90.
By Prokofiev - Own work, CC BY-SA 4.0, Link
While writing this function, we will try to be creative and use loop to draw each part of the curve. The trick is to use the list of all angles that we need to turn in between, together with their direction (i.e. 90 will mean turn $90^\circ$ left, 0 - do not turn at all, and -90 - turn $90^\circ$ right)
def minkowski(n,x):
if n==0:
turtle.forward(x)
else:
for t in [90,-90,-90,0,90,90,-90,0]:
minkowski(n-1,x/4)
turtle.left(t)
for _ in range(4):
minkowski(2,100)
turtle.left(90)
turtle.done()
If you continue studying Programming or Computer Science, you will learn that an important data structure is tree - a collection of elements that have parent and child elements. For example, folders or directories in our computer form a tree.
In our final example, we will draw something similar to a tree, and on the other hand similar to a dandelion or some umbrella-like plant. We will start with one branch, and then for each branch generate $n$ sub-branches, and so on.
from random import randint
def tree(n,b,x):
turtle.forward(x) # draw the branch
if n>0: # draw n sub-branches on top of it
for _ in range(b):
a = randint(-40,40)
turtle.left(a)
tree(n-1,b,x)
turtle.right(a)
turtle.forward(-x) # move back to the beginning of the branch
tree(3,3,100)
turtle.done()
This code is very clever, and it might take you some time to figure out. The difficult thing here is to make turtle return to the original position each time the branch is drawn. So, at the top level, the logic of the function is the following:
forward(x)
forward(-x)
.When drawing branched, we always assume that tree
moves the turtle back to its original position before the drawing.
for _ in range(5):
tree(3,3,100)
turtle.right(90)
turtle.forward(120)
turtle.left(90)
turtle.done()
We have cosidered just a few examples of drawing trees, but there could be many more. For example, try to experiment with our tree
function to produce different types of flora by doing one or more of the following:
a = randint(-40,40)
defines random angle for each branch. By changing the angles you can control the spread of branches, and also whether the tree would look straight, or falling to the left or rightx
by some growth factor, which should be somewhat close to 1I hope you would agree with me, that in the examples above we have managed to draw pretty beautiful pictures! They are not only pleasant aesthetically, but they are beautiful in mathematical sense. Koch Snowflake and Minkowski Island are examples of fractal structures, which can be infinitely complex, i.e. if you draw such a figure for very large $n$, you would be able to zoom into it, and part of the figure would be similar to the original one. Ideally, such a fractal would be infinitely complex. However, we managed to write a simple and rather short program, which can produce arbitrary complex figures. I believe this shows the main beauty of programming -- with simple code you can program computer to perform many complex operations and achieve very complex results!
Of course, real programs are more complex than those we have seen in this course, and you are still to learn how to fight complexity in programming. However, Python is a very good starting point, because from here you can start exploring programming in many different directions:
Picture from this project at hackday.io
And there are many more areas where Pyton can be used as a language! However, before diving right into one of those specific areas, I suggest that you learn a little bit more of core language features in our next course.
I hope you enjoyed the course, and are curious to learn more! Good luck!