Recursion for Runaways

If you like to tinker with maths and are looking for more exotic operators, for example to calculate the Factorial or the Fibonacci series, then this is something you are going to have to implement yourself in LiveCode. But there is no need to despair, this can be done pretty much with a single line, wrapped in a function definition.

MATHS HAZARD – You may skip the following paragraph if you are not a friend of mathematical definitions.

The Factorial of a non-negative number n can be defined as the product of all of its positive integers that are less than or equal to n, with the Factorial of 0 returning 1. The operator for Factorial is denoted by an exclamation mark (!), allowing us to write the operation as follows: n!

The following example demonstrates how Factorial is calculated for the number 6:

6! = 1*2*3*4*5*6 = 720

Now this does not seem to be too much of an issue to implement or write, but how do you go about writing a function in LiveCode that does all the heavy lifting for you, so that you do not have to write a long sequence of multiplications?

Well, there are fundamentally two algorithmic approaches you could consider. These are iteration and recursion. They both operate in quite different ways and have advantages and disadvantages.

Let us look at the iterative approach first, as this is possibly the programming paradigm most people are familiar with. 

We create a function that takes an argument for which we are calculating the Factorial product. This function then cycles through all the positive integers that are less than or equal to the initial argument and multiplies all of these integers together. The function result is the Factorial result.

function factI x
  local tProduct = 1
  local tCounter
  repeat with tCounter = 1 to x
     multiply tProduct by tCounter
  end repeat
  return tProduct
end factI

Now in order to implement this algorithm we need two local variables and a repeat loop. This keeps track of the result as it is being updated through each iteration of the loop. But what if you really do not want to be bothered with local variables and loops and keeping track of data?

Well, meet recursion. Recursion can remember all the data that is specific to an instance of a function call. This means that we can pretty much throw most of the code away that we use in the iterative approach. Yes, we do not need local variables and we do not need a repeat loop. In fact, we can calculate the Factorial of a number with a single line of code in a function.

A recursive implementation usually contains some kind of condition check so it knows when to stop and when to call itself. This has been implemented in the following code using an “if then else statement”. If we are below a certain value stop, otherwise call the function again, but with a changed argument.

function factR x
  if x < 2 then return 1 else return factR (x - 1) * x
end factR

Now that was not too painful, but what is actually going on here that allows us to write code that is so much shorter?

Consider calculating 6! and let us expand how factR calls itself at each recursive level:

Level 1: factR(6)
Level 2: (factR(5) * 6)
Level 3: ((factR(4) * 5) * 6)
Level 4: (((factR(3) * 4) * 5) * 6)
Level 5: ((((factR(2) * 3) * 4) * 5) * 6)
Level 6: (((((factR(1) * 2) * 3) * 4) * 5) * 6)
               (((((1 * 2) * 3) * 4) * 5) * 6) = 720

Note: The parentheses demonstrate the execution order at each level and are not intended to be interpreted in a mathematical sense. The commutative law applies.

So this gives us a total of 6 calls to the function factR for 6! 

Another number sequence we mentioned in the beginning is that of Fibonacci. This sequence received its name from Leonardo of Pisa who published the historical mathematics book “Liber Abaci” around 1202. Leonardo of Pisa was also know by the name Fibonacci.

This Fibonacci number sequence starts: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,. . .

 This sequence has fascinated mathematicians for centuries and reveals remarkable patterns that are very much linked to natural structures, such as the formation of shells, branches and even the arrangement of the seeds in sunflowers. My particular interest is the use of the Fibonacci numbers for the close approximation of the Golden Ratio.

A Fibonacci number is generated by calculating the sum of the previous two numbers in the Fibonacci sequence. This operation is quite different to that used to derive the Factorial number sequence, never the less, it is possible to also wrap this into an iterative and recursive implementation.

Calculating the Fibonacci numbers iteratively requires additional local variables, compared to calculating the Factorial numbers. We step through all of the Fibonacci numbers and create the next ones by adding the previous two numbers together.

function fibI x
  local tFirst = 1, tSecond = 1
  local tCounter, tSum
  repeat with tCounter = 3 to x
     put tFirst + tSecond into tSum
     put tSecond into tFirst
     put tSum into tSecond
  end repeat
  return tSecond
end fibI

 In order to implement this algorithm we need four local variables and a repeat loop. As with the Factorial calculation, this keeps track of the result as it is being updated through each iteration of the loop.

The recursive approach can again do away with local variables and the repeat loop, creating the implementation as follows:

 function fibR x
  if x < 3 then return 1 else return fibR (x-1) + fibR (x-2)
end fibR

 Now I am not going to demonstrate how the recursive levels are expanded here and would like to leave this for the reader to explore. What I would like to add is that calculating the Fibonacci number for 6 calls fibR a total of 15 times.

Now recursion (or meta programming as it is sometimes referred to) is great as it can really reduce your code and hide a lot of the complexity, but beware. Some algorithms are better suited to recursion than others, and recursion can be computationally more expensive than iterative approaches. For example, calculating 20! calls factR 20 times, and that is great. Calculating the Fibonacci number of 20 calls fibR a staggering 13529 times.