ITERATION AND RECURSION
Harold Brochmann

There have been some really astounding discoveries in mathematics in the last couple of decades. Whole new classes of mathematical objects have been uncovered with names like Strange Attractors and Fractals. What they share is that they can only be revealed through computer based mathematical operations called iterations and recursions. These are conceptually very difficult for the uninitiated to distinguish, and so this article is my attempt at elucidate the difference.

In the HyperTalk listings that follow it is assumed that the script belongs to a button and that the card has a field called "display". Each HyperTalk script is followed by a parallel Pascal program for those who are more at home with that language. Here is the first script:

on mouseup
    put 1 into a_number
put a_number & "," into cd fld "display"
    repeat with i = 1 to 10
        put ((3 * a_number) - 1) into a_number
        put a_number & "," after cd fld "display"
    end repeat
end mouseup

The variable is repeatedly subjected to the function 3x - 1. The resulting sequence of values is displayed.

The part that multiplies x by 2 may be done by a separate procedure:

on mouseup
    global x
    put 1 into x
    put x & return into cd fld "message"
    double_x
    put x & return after cd fld "message"
end mouseup

on double_x
    global x
    multiply x by 2
end double_x

Here is the Pascal equivalent: The main procedure in HyperTalk is called 'mouseup'. The main procedure in Pascal is the program itself. In Pascal any sub procedures must come before the main program. In HyperTalk it doesn't matter which comes first. The second line of the Pascal program is called the variable declaration. It says that every part of the program knows about x and its value. In HyperTalk every procdure (called a handler) must declare x to be global separately. Try leaving these lines out to see what happens.

An iterative functions is one which carries out an algorithm many times, the input for each calculation being the result of the previous one. The result is a sequence or set, rather than a single numerical value as is the case with more familiar functions. For example, an iterative doubling function might look like this:

1 start of with a value of 1 for x
2 record the value of x
3 double the value of x
4 go back to step 2

Here we get an unending sequence of numbers: 1,2,4,8,16 ... unless we change the last instruction to read:

4 if x < 1000 then go to step 2

In computerese such calculations can be accomplished by using 'loop's. In HyperTalk:

on mouseup
    put 1 into x
    repeat until (x > 1000)
        put x & return after cd fld "message"
        multiply x by 2
    end repeat
end mouseup

In Pascal:

program loop;
var x : integer;
begin
    x := 1;
    repeat
        writeln(x : 10);
        x := x * 2;
    until (x > 1000)
end.

These loops limit the number of iterations so only values of x less than 1000 are displayed. The output is the sequence 1,2,4,8,16,32,64,128,512.

The other, more sophisticated approach is to use a procedure which calls itself: In HyperTalk:

on mouseup
    put "" into cd fld "message"
    doubleit 1
end mouseup

on doubleit anumber
    if (anumber > 1000) then exit doubleit
    put anumber & return after cd fld "message"
    multiply anumber by 2
    doubleit anumber
end doubleit

In Pascal:

program procedure_call;
procedure doubleit (anumber: integer);
begin
    if (anumber > 1000) then
        exit(doubleit);
    writeln(anumber : 10);
    anumber := anumber * 2;
    doubleit(anumber);
end;
begin {main}
    doubleit(1);
end.

The output is the same doubling sequence we got before. Note that both the HT and Pascal procedures called doubleit use the local variable anumber. The initial value of anumber (1) is passed to the procedure as a parameter. Procedure doubleit calls itself passing the latest value of anumber back to itself as a parameter. The first line of the procedure is an 'escape clause' without which things would go on and on forever.

What we have seen so far is iteration - an algorithm performed repeatedly. Each time the numer on which it is applied is the result of the previous iteration (except for the very first one). By contrast, recursion involves functions rather than a procedures. Before continuing I want to make certain that everyone understands what a function is. A function is something that returns a result. The following illustrates a returns double of whatever the input is: In HyperTalk

function doubleit anumber
    return 2 * anumber
end doubleit

on mouseup
    put doubleit(1) after cd fld "message"
end mouseup

In Pascal:

program doubling_function;
function doubleit (anumber: integer): integer;
begin
    doubleit := 2 * anumber;
end;
begin {main}
    writeln(doubleit(1): 10);
end.

The screen will display a 2. The two is the output of the function.

Finally here is a recursive function in action: In HyperTalk:

function doubleit anumber
    if (anumber > 1000) then 
        return anumber
        exit doubleit
    end if
    put anumber & return after cd fld "message"
    return doubleit(2 * anumber)
end doubleit

on mouseup
    put "" into cd fld "message"
    put doubleit(1) after cd fld "message"
end mouseup

In Pascal:

program recursion;
function doubleit (anumber: integer): integer;
begin
    if (anumber > 1000) then
        begin
            doubleit := anumber;
            exit(doubleit);
        end;
    writeln(anumber : 10);
    doubleit := doubleit(2 * anumber);
end;
begin {main}
    writeln(doubleit(1) : 10);
end.

The screen shows the sequence 1,2,...1024. It is important to realize that the 1024 is the output of the recursive function and is placed there by the main program and that the preceding numbers are incidentally written by the function.

So what's the essential difference between iteration and recursion? With iteration it is the same variable whose value is constantly changed, and you can access its value at each stage. With recursion, a different local variable (by the same name) is created with each call.

If you want to raise a number to an arbitrary power in HyperTalk you use the caret symbol. For example 23 to the power of 5 is written:

23^5

Pascal lacks equivalent notation and if you want to do arithmetic involving powers you have to write you own function. Here is a recursive function that allows you to raise real numbers to integer powers:

program power;
function power (number: real; exponent: integer): real;
begin
    if (exponent = 1) then
        begin
            power := number;
            exit(power);
        end;
    power := number * power(number, exponent - 1);
end;

begin {main}
    write(power(23, 3) 10: 3);
end.