### Recursion in Flowcode

Posted:

**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

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)

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

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)`

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)

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