Tutorial 38 - Recursive patch I


Topics

Recursive programing with patches

 

Functions used

omif, om=, om*, om- and omloop

 

Description

Some computational algorithms require recursive functions. A recursive function is a function in which body we may find a call to itself. A good example is the factorial of an integer. Factorial 5, for example means 1 * 2 * 3 * 4 * 5 and it equals 120. The algorithm maybe something like that:

> Error: Stack overflow on control stack.
>        To globally increase stack space,
>        increase *minimum-stack-overflow-size*
> While executing: "Unknown"
> Type Command-/ to continue, Command-. to abort.
> If continued: Continue with a larger stack
See the Restarts menu item for further choices.


Patch structure

First let us create on the workspace an empty patch and add to it one input and one output. The input <n> is our main argument.

A: If n is equal to zero (the termination test) omif (B) will return 1 else, we will multiply n using om* (C) with (n- 1)

D: In order to multiply n with (n- 1), (n- 2), etc... let us drag the patch from the workspace within itself. In this way n will always be tested by the factorial function we created and will be decremented until it equals zero. With every passage through the testing function omif n will be multiplied by (n- 1) and so forth.

Now in order to use this patch drag it onto another patch.

The outputs and inputs will appear and we may use it as any other patch. The example above returns 120 which is equal to (5 * 4 * 3 * 2 *1)

NOTE: Another way to do this patch is given in tutorial 36