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
Valued Contributor
Posts: 482
Joined: Wed May 31, 2017 11:57 am
Has thanked: 52 times
Been thanked: 267 times
Contact:

Recursion in Flowcode

Postby mnf » Mon Nov 12, 2018 11:10 pm

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 :D - though depending on the target MCU you need to be careful about stack overflows (depth of recursion)

permute.fcfx
(14.03 KiB) Downloaded 52 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
These users thanked the author mnf for the post (total 4):
Steve (Tue Nov 13, 2018 9:56 am) • DavidA (Tue Nov 13, 2018 10:41 am) • Benj (Tue Nov 13, 2018 10:42 am) • jgu1 (Tue Nov 13, 2018 7:57 pm)
Rating: 22.22%
 

mnf
Valued Contributor
Valued Contributor
Posts: 482
Joined: Wed May 31, 2017 11:57 am
Has thanked: 52 times
Been thanked: 267 times
Contact:

Re: Recursion in Flowcode

Postby mnf » Sat Nov 17, 2018 9:46 pm

.. 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 43 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
Valued Contributor
Valued Contributor
Posts: 482
Joined: Wed May 31, 2017 11:57 am
Has thanked: 52 times
Been thanked: 267 times
Contact:

Re: Recursion in Flowcode

Postby mnf » Sun Nov 18, 2018 12:08 am

... and as a slightly more complicated example:

Sudoku.fcfx
(22.44 KiB) Downloaded 50 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