Note: Some people find this section useful, and some find it confusing. If you find it confusing, feel free to skip it and continue with the next section.

To show more advanced ways of using functions, we'll now 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)

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 multiplication: e.g. 3 + 3 (addition) gives the same result as 3 * 2 (multiplication).

Question: What is the first thing the program does?

Answer: The first thing done is the functionmult is defined with the lines:

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.

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.

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) which can now assign the value 6 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

Programming constructs solving a problem by solving a smaller version of the same problem are calledrecursive. In the examples in this chapter, recursion is realized by defining a function calling itself. This facilitates implementing solutions to programming tasks as it may be sufficient to consider the next step of a problem instead of the whole problem at once. It is also useful as it allows to express some mathematical concepts with straightforward, easy to read code.

Any problem that can be solved with recursion could be re-implemented with loops. Using the latter usually results in better performance. However equivalent implementations using loops are usually harder to get done correctly.

Probably the most intuitive definition ofrecursion is:

Recursion

If you still don't get it, seerecursion.

Try walking through the factorial example if the multiplication example did not make sense.

factorial.py

#defines a function that calculates the factorialdeffactorial(n):ifn==0:return1ifn<0:return"Error, negative numbers do not have factorial values!!"returnn*factorial(n-1)print("2! =",factorial(2))print("3! =",factorial(3))print("4! =",factorial(4))print("5! =",factorial(5))print("-3! =",factorial(-3))

Output:

2! = 23! = 64! = 245! = 120-3! = Error, negative values do not have factorial values!!

countdown.py

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

Output:

543210

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