Stop Cursing at Recursion

A recursive function⁽¹⁾ is a function that calls itself until an exit condition is met ⁽²⁾ or until a bounded number of iterations has passed. ⁽³⁾ This is extremely useful when the problem involves a nested branch searching with an unknown number of branches.

Meanwhile⁽⁴⁾ in Model-Based Design…

In general, safety standards⁽⁵⁾ frown upon recursive functions due to their unbounded nature. Determining if recursion can be used in your algorithm is a 2 step process (with some recursion involved).

Determine the memory use and execution time of the recursive function
Determine the “worst case to solution” input data
- Calculate time and memory usage
- If this is acceptable for your system then exit
  Otherwise
- Go back to step 2…

Note, in this example, worst case means that you are looking at how many interactions are required to reach an acceptable solution. Acceptable is not the same as fully converged; you want a solution that is close enough to correct for your controller’s requirement.

When?

Most traditional control problems do not require recursion to solve; however with the onset of adaptive controls and more importantly networked controllers, the need to exhaustively cover all branches in the solution come into play. Again, it comes down to 3 questions

Is there a closed form solution: Can you mathematically solve the problem in either a known number of steps or directly?
If “no” continue on
Is there an unknown depth or branch issue: Is the final path known ahead of time?
If “no” continue
Do you need it now: In some cases you can perform recursion the slow way, e.g. the same function is called once per time step maintaining state information.
If you “need it now” you need recursion!

Footnotes

I had multiple typos (and misleading auto-corrections) when writing this
- re-cursive: a note about handwriting
- re-cur-son: a note about a dog’s puppy
- …
When you meet an exit condition do you say hello or goodbye? Perhaps Aloha, or Ciao, or Shalom, or Annyeong or Salām is the correct word to use.
This is critical in an embedded system where consistent timing and memory limitations are critical.
While loops are similar to recursion in that they execute until an exit condition is reached, they do not enable branching determination.
By default in Simulink the recursive code generation is prohibited for this reason. It can be enabled as shown here; the rest of this blog is about when to consider using it.