Non-Programmer's Tutorial for Python 2.6/Advanced Functions Example
Some people find this section useful, and some find it confusing. If you find it confusing you can skip it (or just look at the examples.) Now we will do a walk through for the following program:
def mult(a, b):
if b == 0:
return 0
rest = mult(a, b - 1)
value = a + rest
return value
result = mult(3, 2)
print "3 * 2 = ", result
3 * 2 = 6
Basically this program creates a positive integer multiplication function (that is far slower than the built in multiplication function) and then demonstrates this function with a use of the function. This program demonstrates the use of recursion, that is a form of iteration (repetition) in which there is a function that repeatedly calls itself until an exit condition is satisfied. It uses repeated additions to give the same result as mutiplication: e.g. 3 + 3 (addition) gives the same result as 3 * 2 (multiplication).
RUN 1
- Question: What is the first thing the program does?
- Answer: The first thing done is the function mult is defined with all the lines except the last one.
def mult(a, b):
if b == 0:
return 0
rest = mult(a, b - 1)
value = a + rest
return value
- This creates a function that takes two parameters and returns a value when it is done. Later this function can be run.
- What happens next?
- The next line after the function,
result = mult(3, 2)
is run.
- What does this line do?
- This line will assign the return value of
mult(3, 2)
to the variableresult
.
- And what does
mult(3, 2)
return? - We need to do a walkthrough of the
mult
function to find out.
RUN 2
- What happens next?
- The variable
a
gets the value 3 assigned to it and the variableb
gets the value 2 assigned to it.
- And then?
- The line
if b == 0:
is run. Sinceb
has the value 2 this is false so the linereturn 0
is skipped.
- And what then?
- The line
rest = mult(a, b - 1)
is run. This line sets the local variablerest
to the value ofmult(a, b - 1)
. The value ofa
is 3 and the value ofb
is 2 so the function call ismult(3,1)
- So what is the value of
mult(3, 1)
? - We will need to run the function
mult
with the parameters 3 and 1.
def mult(3, 2):
if b == 0:
return 0
rest = mult(3, 2 - 1)
value = 3 + rest
return value
RUN 3
- So what happens next?
- The local variables in the new run of the function are set so that
a
has the value 3 andb
has the value 1. Since these are local values these do not affect the previous values ofa
andb
.
- And then?
- Since
b
has the value 1 the if statement is false, so the next line becomesrest = mult(a, b - 1)
.
- What does this line do?
- This line will assign the value of
mult(3, 0)
to rest.
- So what is that value?
- We will have to run the function one more time to find that out. This time
a
has the value 3 andb
has the value 0.
- So what happens next?
- The first line in the function to run is
if b == 0:
.b
has the value 0 so the next line to run isreturn 0
- And what does the line
return 0
do? - This line returns the value 0 out of the function.
- So?
- So now we know that
mult(3, 0)
has the value 0. Now we know what the linerest = mult(a, b - 1)
did since we have run the functionmult
with the parameters 3 and 0. We have finished runningmult(3, 0)
and are now back to runningmult(3, 1)
. The variablerest
gets assigned the value 0.
- What line is run next?
- The line
value = a + rest
is run next. In this run of the function,a = 3
andrest = 0
so nowvalue = 3
.
- What happens next?
- The line
return value
is run. This returns 3 from the function. This also exits from the run of the functionmult(3, 1)
. Afterreturn
is called, we go back to runningmult(3, 2)
.
- Where were we in
mult(3, 2)
? - We had the variables
a = 3
andb = 2
and were examining the linerest = mult(a, b - 1)
.
- So what happens now?
- The variable
rest
get 3 assigned to it. The next linevalue = a + rest
setsvalue
to3 + 3
or 6.
- So now what happens?
- The next line runs, this returns 6 from the function. We are now back to running the line
result = mult(3, 2)
. Now the return value can be assigned to the variableresult
.
- What happens next?
- The next line after the function,
print "3 * 2 = ", result
is run.
- And what does this do?
- It prints
3 * 2 =
and the value ofresult
which is 6. The complete line printed is3 * 2 = 6
- What is happening overall?
- Basically we used two facts to calculate the multiple of the two numbers. The first is that any number times 0 is 0 (
x * 0 = 0
). The second is that a number times another number is equal to the first number plus the first number times one less than the second number (x * y = x + x * (y - 1)
). So what happens is3 * 2
is first converted into3 + 3 * 1
. Then3 * 1
is converted into3 + 3 * 0
. Then we know that any number times 0 is 0 so3 * 0
is 0. Then we can calculate that3 + 3 * 0
is3 + 0
which is3
. Now we know what3 * 1
is so we can calculate that3 + 3 * 1
is3 + 3
which is6
.
This is how the whole thing works:
mult(3, 2) 3 + mult(3, 1) 3 + 3 + mult(3, 0) 3 + 3 + 0 3 + 3 6
Should you still have problems with this example, look at the process backwards. What is the last
step that happens? We can easily make out that the result of mult(3, 0)
is
0
. Since b
is 0
, the function mult(3, 0)
will return 0
and stop.
So what does the previous step do? mult(3, 1)
does not return 0
because b
is not 0
. So the next lines are executed:
rest = mult (a, b - 1)
, which is rest = mult (3, 0)
,
which is 0
as we just worked out. So now the variable rest
is set to 0
.
The next line adds the value of rest
to a
, and since a
is 3
and rest
is 0
, the result is 3
.
Now we know that the function mult(3, 1)
returns 3
. But we want to
know the result of mult(3,2)
. Therefore, we need to jump back to the
start of the program and execute it one more round:
mult(3, 2)
sets rest
to the result of mult(3, 1)
. We know
from the last round that this result is 3
. Then value
calculates as a + rest
,
i. e. 3 + 3
. Then the result of 3 * 2 is printed as 6.
The point of this example is that the function mult(a, b)
starts itself inside
itself. It does this until b
reaches 0
and then calculates the result as explained above.
Recursion
editProgramming constructs of this kind are called recursive and probably the most intuitive definition of recursion is:
- Recursion
- If you still don't get it, see recursion.
These last two sections were recently written. If you have any comments, found any errors or think I need more/clearer explanations please email. I have been known in the past to make simple things incomprehensible. If the rest of the tutorial has made sense, but this section didn't, it is probably my fault and I would like to know. Thanks.
Examples
editfactorial.py
#defines a function that calculates the factorial
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print "2! =", factorial(2)
print "3! =", factorial(3)
print "4! =", factorial(4)
print "5! =", factorial(5)
Output:
2! = 2 3! = 6 4! = 24 5! = 120
countdown.py
def count_down(n):
print n
if n > 0:
return count_down(n-1)
count_down(5)
Output:
5 4 3 2 1 0
Commented_mult.py
# The comments below have been numbered as steps, to make explanation
# of the code easier. Please read according to those steps.
# (step number 1, for example, is at the bottom)
def mult(a, b): # (2.) This function will keep repeating itself, because....
if b == 0:
return 0
rest = mult(a, b - 1) # (3.) ....Once it reaches THIS, the sequence starts over again and goes back to the top!
value = a + rest
return value # (4.) therefore, "return value" will not happen until the program gets past step 3 above
print "3 * 2 = ", mult(3, 2) # (1.) The "mult" function will first initiate here
# The "return value" event at the end can therefore only happen
# once b equals zero (b decreases by 1 everytime step 3 happens).
# And only then can the print command at the bottom be displayed.
# See it as kind of a "jump-around" effect. Basically, all you
# should really understand is that the function is reinitiated
# WITHIN ITSELF at step 3. Therefore, the sequence "jumps" back
# to the top.
Commented_factorial.py
# Another "jump-around" function example:
def factorial(n): # (2.) So once again, this function will REPEAT itself....
if n <= 1:
return 1
return n * factorial(n - 1) # (3.) Because it RE-initiates HERE, and goes back to the top.
print "2! =", factorial(2) # (1.) The "factorial" function is initiated with this line
print "3! =", factorial(3)
print "4! =", factorial(4)
print "5! =", factorial(5)
Commented_countdown.py
# Another "jump-around", nice and easy:
def count_down(n): # (2.) Once again, this sequence will repeat itself....
print n
if n > 0:
return count_down(n-1) # (3.) Because it restarts here, and goes back to the top
count_down(5) # (1.) The "count_down" function initiates here