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:

defmult(a,b):ifb==0:return0rest=mult(a,b-1)value=a+restreturnvalueresult=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 thendemonstrates 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.

defmult(a,b):ifb==0:return0rest=mult(a,b-1)value=a+restreturnvalue

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 ofmult(3, 2) to the variableresult.

And what doesmult(3, 2) return?

We need to do a walkthrough of themult function to find out.

RUN 2

What happens next?

The variablea gets the value 3 assigned to it and the variableb gets the value 2 assigned to it.

And then?

The lineif b == 0: is run. Sinceb has the value 2 this is false so the linereturn 0 is skipped.

And what then?

The linerest = mult(a, b - 1) is run. This line sets the local variablerest to the value ofmult(a, b - 1). The value of a is 3 and the value of b is 2 so the function call ismult(3,1)

So what is the value ofmult(3, 1) ?

We will need to run the function mult with the parameters 3 and 1.

defmult(3,2):ifb==0:return0rest=mult(3,2-1)value=3+restreturnvalue

RUN 3

So what happens next?

The local variables in the new run of the function are set so thata has the value 3 and b 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 ofmult(3, 0) to rest.

So what is that value?

We will have to run the function one more time to find that out. This timea has the value 3 andb has the value 0.

So what happens next?

The first line in the function to run isif b == 0:. b has the value 0 so the next line to run isreturn 0

And what does the linereturn 0 do?

This line returns the value 0 out of the function.

So?

So now we know thatmult(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 running mult(3, 1). The variablerest gets assigned the value 0.

What line is run next?

The linevalue = a + rest is run next. In this run of the function,a = 3 andrest = 0 so nowvalue = 3.

What happens next?

The linereturn value is run. This returns 3 from the function. This also exits from the run of the function mult(3, 1). Afterreturn is called, we go back to running mult(3, 2).

Where were we in mult(3, 2)?

We had the variablesa = 3 andb = 2 and were examining the linerest = mult(a, b - 1).

So what happens now?

The variablerest 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 lineresult = 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 prints3 * 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 into 3 + 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 + 03 + 36

Should you still have problems with this example, look at the process backwards. What is the laststep that happens? We can easily make out that the result ofmult(3, 0) is0. Sinceb is0, the functionmult(3, 0) will return0 and stop.

So what does the previous step do?mult(3, 1) does not return0becauseb is not0. So the next lines are executed:rest = mult (a, b - 1), which isrest = mult (3, 0), which is0 as we just worked out. So now the variablerest is set to0.

The next line adds the value ofrest toa, and sincea is3 andrestis0, the result is3.

Now we know that the functionmult(3, 1) returns3. But we want toknow the result ofmult(3,2). Therefore, we need to jump back to thestart of the program and execute it one more round:mult(3, 2) setsrest to the result ofmult(3, 1). We knowfrom the last round that this result is3. Thenvalue calculates asa + rest,i. e.3 + 3. Then the result of 3 * 2 is printed as 6.

The point of this example is that the functionmult(a, b) starts itself insideitself. It does this untilb reaches0 and then calculates the result as explained above.

Programming constructs of this kind are calledrecursive and probably the most intuitive definition ofrecursion is:

Recursion

If you still don't get it, seerecursion.

These last two sections were recently written. If you have anycomments, found any errors or think I need more/clearer explanationsplease email. I have been known in the past to make simple thingsincomprehensible. If the rest of the tutorial has made sense, but thissection didn't, it is probably my fault and I would like to know.Thanks.

factorial.py

#defines a function that calculates the factorialdeffactorial(n):ifn<=1:return1returnn*factorial(n-1)print"2! =",factorial(2)print"3! =",factorial(3)print"4! =",factorial(4)print"5! =",factorial(5)

Output:

2! = 23! = 64! = 245! = 120

countdown.py

defcount_down(n):printnifn>0:returncount_down(n-1)count_down(5)

Output:

543210

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)defmult(a,b):# (2.) This function will keep repeating itself, because....ifb==0:return0rest=mult(a,b-1)# (3.) ....Once it reaches THIS, the sequence starts over again and goes back to the top!value=a+restreturnvalue# (4.) therefore, "return value" will not happen until the program gets past step 3 aboveprint"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:deffactorial(n):# (2.) So once again, this function will REPEAT itself....ifn<=1:return1returnn*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 lineprint"3! =",factorial(3)print"4! =",factorial(4)print"5! =",factorial(5)

Commented_countdown.py

# Another "jump-around", nice and easy:defcount_down(n):# (2.) Once again, this sequence will repeat itself....printnifn>0:returncount_down(n-1)# (3.) Because it restarts here, and goes back to the topcount_down(5)# (1.) The "count_down" function initiates here

• Book:Non-Programmer's Tutorial for Python 2.6