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 print "3 * 2 = ", mult(3, 2)

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,
`print "3 * 2 = ", mult(3, 2)`

is run.

- And what does this do?
- It prints
`3 * 2 =`

and the return value of`mult(3, 2)`

- 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 variable`b`

gets the value 2 assigned to it.

- And then?
- The line
`if b == 0:`

is run. Since`b`

has the value 2 this is false so the line`return 0`

is skipped.

- And what then?
- The line
`rest = mult(a, b - 1)`

is run. This line sets the local variable`rest`

to the value of`mult(a, b - 1)`

. The value of`a`

is 3 and the value of`b`

is 2 so the function call is`mult(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) rest = mult(3, 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 and`b`

has the value 1. Since these are local values these do not affect the previous values of`a`

and`b`

.

- And then?
- Since
`b`

has the value 1 the if statement is false, so the next line becomes`rest = 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 and`b`

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 is`return 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 line`rest = mult(a, b - 1)`

did since we have run the function`mult`

with the parameters 3 and 0. We have finished running`mult(3, 0)`

and are now back to running`mult(3, 1)`

. The variable`rest`

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`

and`rest = 0`

so now`value = 3`

.

- What happens next?
- The line
`return value`

is run. This returns 3 from the function. This also exits from the run of the function`mult(3, 1)`

. After`return`

is called, we go back to running`mult(3, 2)`

.

- Where were we in
`mult(3, 2)`

? - We had the variables
`a = 3`

and`b = 2`

and were examining the line`rest = mult(a, b - 1)`

.

- So what happens now?
- The variable
`rest`

get 3 assigned to it. The next line`value = a + rest`

sets`value`

to`3 + 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
`print "3 * 2 = ", mult(3, 2)`

which can now print out the 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 is`3 * 2`

is first converted into`3 + 3 * 1`

. Then`3 * 1`

is converted into`3 + 3 * 0`

. Then we know that any number times 0 is 0 so`3 * 0`

is 0. Then we can calculate that`3 + 3 * 0`

is`3 + 0`

which is`3`

. Now we know what`3 * 1`

is so we can calculate that`3 + 3 * 1`

is`3 + 3`

which is`6`

.

This is how the whole thing works:

3 * 2 3 + 3 * 1 3 + 3 + 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.

#### RecursionEdit

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

### ExamplesEdit

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