Recursion

Analytica User GuideRecursion

A recursive function is a function that calls itself within its definition. This is often a convenient way to define a function, and sometimes the only way. As an example, consider this definition of factorial:

Function Factorial2(n: Positive Atom) Definition: IF n > 1 THEN N*Factorial2(n-1) ELSE 1

If its parameter, n, is greater than 1, Factorial2 calls itself if with the actual parameter value n-1. Otherwise, it simply returns 1. Like any normal recursive function, it has a termination condition under which the recursion stops — when n <= 1.

Tip

The built-in function Factorial does the same, and is fully abstractable, to boot. We define Factorial2 here as a simple example to demonstrate key ideas.

Normally, if you try to use a function in its own definition, it complains about a cyclic dependency loop. To enable recursion, you must display and set the Recursive attribute:

Select the Attributes dialog from the Object menu.

Select Functions from the Class menu in this dialog.

Scroll down the list of attributes and click Recursive twice, so that it shows √, meaning that the recursive attribute is displayed for each function in its Object window and the Attribute panel.

Check OK to close Attributes dialog.

For each function for which you wish to enable recursion:

Open the Object Window for the function by double-clicking its node (or select the node and click the Object button).

Type 1 into its Recursive field.

As another example, consider this recursive function to compute a list of the prime factors of an integer, x, equal to or greater than y:

Function Prime_factors(x, y: Positive Atom) Definition: Var n := Floor(x/y); IF n<y THEN [x] ELSE IF x = n*y THEN Concat([y], Factors(n, y)) ELSE Prime_factors(x, y+1) Factors(60, 2) → [2, 2, 3, 5]

In essence, Prime_factors says to compute n as x divided by y, rounded down. If y is greater than n, then x is the last factor, so return x as a list. If x is an exact factor of y, then concatenate x with any factors of n, equal or greater than n. Otherwise, try y+1 as a factor.

Tip

To prevent accidental infinite recursion, it stops and gives a warning if the stack reaches a depth of 256 function calls.