[Tutor] Re Help with this script

[jfouhy at paradise.net.nz]

Quoting John Carmona <jeannot18 at hotmail.com>:

> Is it that if you use "while 1:" you create a recursive function? Hope I
> am right.

No ...

Remember how functions can call other functions?

def add(x, y):
    """ Add two integers together. """
    return x+y

def mul(x, y):
    """ Multiply two integers together. """
    if x == 0:
        return 0
    if x < 0:
        x = -x
    product = y
    while x > 1:
        product = add(product, y)
        x = add(x, -1)

The mul function calls add to do some of its work for it.

A recursive functio nis just a function that calls itself.  For example, we
could rewrite add as:

def increment(x):
    """ Increment an integer. """
    return x + 1

def decrement(x):
    """ Decrement an integer. """
    return x - 1

def add(x, y):
    """ Add two integers together. """
    if x == 0:
        return y
    if x == 1:
        return increment(y)
    if x == -1:
        return decrement(y)
    if x < 0:
        return add(-1, add(add(1, x), y))
    else:
        return add(1, add(add(-1, x), y))

In this case, add is a recursive function, because it makes calls to itself. 
There's nothing magical about recursive functions or recursion; you just have to
be a bit careful to make sure that your program will end.  

Example:

def poem():
    print 'A mad metaprogrammer wrote a mad metaprogram,\n which started: "',
    poem()
    print 'sort of close," were the words that the programmer finally chose\nTo
bring his mad program to some sort of close.'

The poem() function will call the poem() function which will call the poem()
function which will call the poem() function, with no end in sight...

Another example:

def qsort(lst):
    """ Quicksort a list. """
    if len(lst) <= 1:
        return lst
    pivot = lst[0]
    return qsort([x for x in lst if x < pivot]) + [pivot] + qsort([x for x in
lst if x > pivot])

This will stop because the argument in each recursive call to qsort is smaller
than the original, and because there is a smallest value ([]).

Does this help?

[Bonus questions:

1. Can you rewrite the recursive add() so that you only need one of (increment,
decrement)?

2. Do you recognise the inspiration for poem()?
]

-- 
John.