Learning Python 3 with the Linkbot/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. Lets look at a simple example.

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

# 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 overhead. 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 n, is denoted as n!.

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.

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:

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)