Recursion in Flowcode

Tips, Tricks and methods for programming, learn ways of making your programming life easier, and share your knowledge with others.

Moderators: Benj, Mods

mnf
Valued Contributor
Posts: 1052
Joined: Wed May 31, 2017 11:57 am
Contact:

Recursion in Flowcode

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
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
Valued Contributor
Posts: 1052
Joined: Wed May 31, 2017 11:57 am
Contact:

Re: Recursion in Flowcode

.. 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
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
Valued Contributor
Posts: 1052
Joined: Wed May 31, 2017 11:57 am
Contact:

Re: Recursion in Flowcode

... and as a slightly more complicated example:
Sudoku.fcfx
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
Valued Contributor
Posts: 1052
Joined: Wed May 31, 2017 11:57 am
Contact:

Re: Recursion in Flowcode

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