# Non-Programmer's Tutorial for Python 3/Advanced Functions Example

*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:

``` python
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)
```

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 function `mult` is defined
    with the lines:

``` python
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
    variable `result`.

And what does `mult(3, 2)` return?
:   We need to do a walkthrough of the `mult` function to find out.

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.

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 `result = mult(3, 2)` which can now assign
    the value 6 to the variable `result`.

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 of `result` which is 6. The
    complete line printed is `3 * 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 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:

`mult(3, 2)`\
`3 + mult(3, 1)`\
`3 + 3 + mult(3, 0)`\
`3 + 3 + 0`\
`3 + 3`\
`6`

#### Recursion

Programming constructs solving a problem by solving a smaller version of
the same problem are called *recursive*. 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 of *recursion* is:

Recursion
:   If you still don\'t get it, see *recursion*.

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

### Examples

**factorial.py**

``` python
#defines a function that calculates the factorial

def factorial(n):
    if n == 0:
        return 1
    if n<0:
        return "Error, negative numbers do not have factorial values!!"
    return n * 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! = 2`\
`3! = 6`\
`4! = 24`\
`5! = 120`\
`-3! = Error, negative values do not have factorial values!!`

**countdown.py**

``` python
def count_down(n):
    print(n)
    if n > 0:
        return count_down(n-1)

count_down(5)
```

Output:

`5`\
`4`\
`3`\
`2`\
`1`\
`0`

