# Non-Programmer's Tutorial for Python 3/Recursion

## Recursion

In Python, a recursive function is a function which calls itself.

### Introduction to recursion

So far, in Python, we have seen functions which call other functions.
However, it is possible for a function to call itself. Let\'s look at a
simple example.

``` python
# Program by Mitchell Aikens
# No Copyright
# 2010

num = 0

def main():
    counter(num)

def counter(num):
    print(num)
    num += 1
    counter(num)

main()
```

If you were to run this program in IDLE, it would run forever. The only
way to stop the loop would be to interrupt the execution by pressing
Ctrl + C on your keyboard. This is an example of an infinite recursion.
(Some users have reported a glitch in the current IDLE system causing
the exception raised by Ctrl + C to start looping as well. If this
happens, press Ctrl + F6, and the IDLE shell should restart.)

It is arguable that recursion is just another way to accomplish the same
thing as a while loop. In some cases, this is absolutely correct.
Though, there are other uses for Recursion that are very valid, where
`while` loops or `for` loops may not be optimal.

Recursion can be controlled, just like loops. Lets look at an example of
a controlled loop.

``` python
# Program by Mitchell Aikens
# No copyright
# 2012
def main():
    loopnum = int(input("How many times would you like to loop?\n"))
    counter = 1
    recurr(loopnum,counter)

def recurr(loopnum,counter):
    if loopnum > 0:
        print("This is loop iteration",counter)
        recurr(loopnum - 1,counter + 1)
    else:
        print("The loop is complete.")

main()
```

The above uses arguments/parameters to control the number of recursions.
Simply use what you already know about functions and follow the flow of
the program. It is simple to figure out. If you are having trouble,
please refer back to Non-Programmer\'s Tutorial for Python 3/Advanced
Functions
Example.

## Practical Applications of Recursion

Often, recursion is studied at an advanced computer science level.
Recursion is usually used to solve complex problems that can be broken
down into smaller, identical problems. Recursion isn\'t required to
solve a problem. Problems that can be solved with recursion, most likely
can be solved with loops. Also, a loop may be more efficient than a
recursive function. Recursive functions require more memory, and
resources than loops, making them less efficient in a lot of cases. This
usage requirement is sometimes referred to as
`<i>`{=html}overhead`</i>`{=html}. You might be thinking, \"Well why
bother with recursion. I\'ll just use a loop. I already know how to loop
and this is a lot more work.\" This thought is understandable, but not
entirely ideal. When solving complex problems, a recursive function is
sometimes easier, faster, and simpler to build and code.

Think of these two \"rules\":

-   If I can solve the problem now, without recursion, the function
    simply returns a value.
-   If I cannot solve the problem now without recursion, the function
    reduces the problem to something smaller and similar, and calls
    itself to solve the problem.

Let\'s apply this using a common mathematical concept, factorials. If
you are unfamiliar with factorials in mathematics, please refer to the
following reading. Factorials

The factorial of a number `<i>`{=html}n`</i>`{=html}, is denoted as
`<i>`{=html}n!`</i>`{=html}.

Here are some basic rules of factorials.

If n = 0 then n! = 1 If n \> 0 then n! = 1 x 2 x 3 x \... x n

For example, let\'s look at the factorial of the number 9.

9! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9

Let\'s look at a program which calculates the factorial of any number
entered by the user, by method of recursion.

``` python3
def main():
    num = int(input("Please enter a non-negative integer.\n"))
    fact = factorial(num)
    print("The factorial of",num,"is",fact)

def factorial(num):
    if num == 0:
        return  1
    else:
        return num * factorial(num - 1)

main()
```

Recursion is also useful in an advanced topic called generators. To
generate the series 1,2,1,3,1,2,1,4,1,2\... we would need this code:

``` python
def crazy(min_):
    yield min_
    g=crazy(min_+1)
    while True:
        yield next(g)
        yield min_

i=crazy(1)
```

to get the next element you would call next(i)

