Recursion in Flowcode

[mnf]

A powerful technique in programming is Recursion. (See https://en.wikipedia.org/wiki/Recursion)

This is defined as a function calling itself within it's own definition - and lends itself to some very elegant functions..

It is used where a problem can be solved for a subset of the current problem and the problem can be split and solved for some simpler part(s) of the problem . So for example, the Fibonacci number (each number in the sequence is the sum of the previous 2) - Fib(n) can be defined as

Code: Select all

Fib(n) = Fib(n-1) + Fib(n-2)

There must always be some base condition for which the problem can be solved - for the Fibonacci sequence we know Fib(0) = 1 and Fib(1) = 1 (now sometimes Fib(0) is defined as 0 but the sequence is the same)

The Radio4 puzzle for Today - today ('Seven diners sit down to eat seven different dishes at a Chinese restaurant. Unfortunately, everyone is served the wrong dish - but the circular table can rotate. Is it always possible to rotate the table so that at least two diners have the correct food?') - led to thinking about permutations (Permutations and Combinatorics are a large and fascinating area of maths/programming)

Can Recursion be used in Flowcode?

Yes it can - though depending on the target MCU you need to be careful about stack overflows (depth of recursion)

permute.fcfx

(14.03 KiB) Downloaded 824 times

Generates permutations of an array and outputs them to UART. To do something more useful add code (or a macro call) to Permute. Notice that the first part of Permute tests for an end case - ending the recursion, and stopping the MCU crashing.

Notice also that I use a global array (and it's size) to permute - rather than passing it to the Permute macro as a parameter. This reduces the stack use - and allows a greater level of recursion on an MCU with limited stack space. An array of n digits has n! (factorial) permutations - so numbers get large fast. 6 -> 720, 10 digits -> 3628800 permutations.

So - the puzzle is left for you to enjoy (is the brute force approach the best one??)

Generating the Fibonacci sequence is left as an exercise - though Recursion is not a good way to generate them! Use a loop!

Note that a recursive solution can always be converted to a non-recursive function - although it often leads to much shorter and more elegant solutions.

Notes - on the ZX Spectrum I used to allow for up to 10! combinations as a maximum. I used to use a non-recursive algorithm (adjacent-mark) - which I haven't been able to find (if anyone has any info) - the recursive algorithm here I first saw in Wirth's 'Programming in Modula-2'. Now in C++ the 'next_permutation' STL algorithm is very useful.
Another 'easy' algorithm to code as a recursive macro is factorial (Factorial(n) = n * Factorial(n-1), with Factorial(1) = 1 as the end condition) - again a loop is quicker...

Martin

[mnf]

.. and whilst playing with this I came across Heap's algorithm.

This, again, is a recursive algorithm for generating permutations. It is less intuitive but faster than the previous algorithm ('Remove' algorithm) - by several seconds for 10! permutations on an Arduino. For 11! / 12! permutations the difference will be more significant.

I got the algorithm from https://www.topcoder.com/blog/generating-permutations/ though note that there is a typo in it:

Code: Select all

        
	for(int i = 0;i > (n - 1);i++) {
    		heaps_algorithm(a, n-1);
    		...

Should be

Code: Select all

        for(int i = 0;i < (n - 1);i++) {		// '<' rather than '>'
            heaps_algorithm(a, n-1);
            ...

So in Flowcode:

HeapsAlgorithm.fcfx

(14.03 KiB) Downloaded 869 times

It also has a page on Wikipedia https://en.wikipedia.org/wiki/Heap%27s_algorithm

It generates a different ordering of the permutations.

If anyone would like to optimize it a bit then see (the slides of) Sedgewick's lecture at http://www.cs.princeton.edu/~rs/talks/perms.pdf

Martin

[mnf]

... and as a slightly more complicated example:

Sudoku.fcfx

(22.44 KiB) Downloaded 885 times

Which recursively solves a Sudoku puzzle. It is quick - almost instant (on an Arduino) to solve the sample puzzle (results are to UART) Notice how the program 'tries' a digit at each position - after checking if it is available in the row, column and 3x3 cell. If no result is found then it clears the digit - then tries the next. This is known as backtracking.

The example Sudoku is hard coded - left as an exercise to add a input / output method to suit.
The same technique can be used for 16x16 Sudoku (Elektor magazine anyone) - with a little bit of work - left as an exercise (hint: you'll either have to use bits 0..15 for the digits (I use 1..9 here) or extend the size of the masks)

Martin

[mnf]

Currently reading 'Algorithms Illuminated' by Tim Roughgarden - and first algorithm I tried to implement in Flowcode was Quicksort.

This is a great sorting algorithm - quick (as the name suggests) and also light on memory use (although it can use a fair bit on recursion calls...)

So - using a very naïve ChoosePivot (- using a random value works very well, or the first element (probably as good as the middle...) - but scope to experiment )

Quicksort...

qsort.fcfx

(16.3 KiB) Downloaded 732 times

Note that this works nicely in simulation (using either 16 or 32 bit data) - but won't work as is on an Arduino (the data size is too large for RAM)

Martin