Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Gauld A.Learning to program (Python)_1.pdf
Скачиваний:
21
Добавлен:
23.08.2013
Размер:
1.34 Mб
Скачать

Advanced Topics

Recursion

Note: This is a fairly advanced topic and for most applications you don't need to know anything about it. Occasionally, it is so useful that it is invaluable, so I present it here for your study. Just don't panic if it doesn't make sense stright away.

What is it?

Despite what I said earlier about looping being one of the cornerstones of programming it is in fact possible to create programs without an explicit loop construct. Some languages, such as Lisp, do not in fact have an explicit loop construct like FOR, WHILE, etc. Instead they use a technique known as recursion . This turns out to be a very powerful technique for some types of problem, so we'll take a look at it now.

Recursion simply means applying a function as a part of the definition of that same function. Thus the definition of GNU (the source of much free software) is said to be recursive because GNU stands for 'GNU's Not Unix'. ie GNU is part of the definition of GNU!

The key to making this work is that there must be a terminating condition such that the function branches to a non-recursive solution at some point. (The GNU definition fails this test and so gets stuck in an infinite loop).

Let's look at a simple example. The mathematical factorial function is defined as being the product of all the numbers up to and including the argument, and the factorial of 1 is 1. Thinking about this, we see that another way to express this is that the factorial of N is equal to N times the factorial of (N-1).

Thus:

1! = 1

2! = 1 x 2 = 2

3! = 1 x 2 x 3 = 2! x 3 = 6

N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

So we can express this in Python like this:

def factorial(n): if n == 1:

return 1 else:

return n * factorial(n-1)

Now because we decrement N each time and we test for N equal to 1 the function must complete.

Writing the factorial function without recursion involves quite a bit more code. You need to create a list of all the numbers from 1 to N then loop over that list multiplying the current total by the next item. Try it as an exercise and compare the result to the function above.

Recursing over lists

The other area where recursion is very useful is in processing lists. Provided we can test for an empty list, and generate a list minus its first element we can use recursion easily.

Consider the trivial case of printing each element of a list of strings using a function printList:

def printList(L):

69

if L:

print L[0]

# for [1:] - see 'slicing' in the Python reference manual printList(L[1:])

If L is true - non empty - we print the first element then process the rest of the list.

For a simple list that's a trivial thing using a simple loop. But consider what happens if the List is complex and contains other lists within it. If we can test whether an item is a List then we can call printList() recursively. If not we simply print it. Lets try that:

def printList(L):

#if its empty do nothing if not L: return

#if its a list call printList on 1st element if type(L[0]) == type([]):

printList(L[0])

else: #no list so just print print L[0]

#now process the rest of L

printList(L[1:])

Now if you try to do that using a conventional loop construct you'll find it very difficult. Recursion makes a very complex task comparatively simple.

There is a catch (of course!). Recursion on large data structures tends to eat up memory so if you are short of memory, or have very large data structures to process the more complex conventional code may be safer.

OK, let's now take another leap into the unknown as we introduce Object Oriented Programming.

70