Matlab Code Generation for Recursive Functions

Question

I'm trying to convert a recursive function in Matlab to C/C++ code using Matlab's Coder app. In general, Coder gives an error saying that recursive functions are not allowed. However, the Matlab help pages say that you can generate code from recursive functions if you follow the below guidelines:

"When you use recursion in MATLAB code that is intended for code generation, follow these restrictions:"

The top-level function in a MATLAB Function block cannot be a recursive function, but it can call a recursive function.
Assign all outputs of a run-time recursive function before the first recursive call in the function.
Assign all elements of cell array outputs of a run-time recursive function.
Inputs and outputs of run-time recursive functions cannot be classes.
The Maximum stack size parameter is ignored for run-time recursion.

I basically understand the conditions but I don't know how to get Matlab to accept the recursive code. I used one of the examples from Matlab:

function y = call_recursive()
   n =35;
   x = 10;
   y = myrecursive(x,n);
end

function y = myrecursive(x,n)
   coder.inline('never')
   if x > 1
       y = n + myrecursive(x-1,n-1); 
   else
       y = n;
   end
end

but I still get the "recursive functions not allowed" error. A stripped version of my own code is:

%------------------------
function recursion_test()
   recursive_fn();
end %recursive caller
%------------------------
%------------------------
function recursive_fn()

persistent mycount;
if isempty(mycount) %initialize the persistent variable
   mycount = 0;
end

counter = 0;
while(counter<300)
   mycount = mycount + 1;
   if mycount<100 %some generic test condition
      recursive_fn();
   end
   if mycount<200 %another generic test condition
      recursive_fn();
   end %if
   counter = counter+1;
end
disp(counter);
end %recursive function
%------------------------

My code gives the same error as Matlab's example. My specific application should never go into recursion more than 300 times...and usually is around 50-90 times. Note that the above code doesn't accurately keep track of the recursion but I do have tracking in the actual code. I could limit recursion to 300 times and force the compiler to make 300 copies of the recursion base code (I don't know how to do that...but that's a different problem for now). First, I would like to be able to generate C/C++ code with the Coder app using the above functions.

So, can anyone explain how to generate C/C++ code for the recursive functions above. Minimally, I would like call time recursion but ideally, I would like to know runtime recursion as well. Note I have gone through Matlab's code generation and recursion help pages and have searched for a solution using my favorite search engine however I haven't been able to find a clear, step-by-step procedure for it. Your help would be greatly appreciated.

You are aware that you never need recursive calls, no? Recursive function calls can very easily lead to a stack overflow. The generally better way is to use a stack data structure containing the necessary parameters per item, and a loop to control pushing and popping from the stack and call a function with the current items. I don't know if matlab's scripting language provides a stack like data structure, in c++ you can use std::stack<T> where T is an item to hold all necessary input and output parameters. — πάντα ῥεῖ
I should have mentioned that I'm aware of the demerits of recursive calls and that it's possible to use stacks (I am not doing it in this program but I have made stacks and deques in Matlab...so it is possible). The examples I provided were shown as simple examples that someone who has experience generating C/C++ code for recursive functions using Matlab's Coder app can easily show me how to do it. The functions themselves aren't meant to make sense. They're just meant to show examples of simple recursive functions. — user70891
There are advantages and disadvantages to recursion and in this case in particular, one main advantage is code maintenance. The form that the code is in is compact and easy to understand. I'm not concerned about stack issues or the inefficiency of the calls. As I mentioned in the original question, we know the max number of recursion calls and the max size of the stack. Debugging was less than pleasant but that comes with the territory and it runs perfectly now. So, to be clear, I'm not looking for a workaround, I want to know how to convert a recursive function using Matlab's Coder app. — user70891
I was able to successfully run codegen recursive_test on that code in MATLAB R2020a. What MATLAB release are you using? Codegen support for recursion was added in R2016b — Ryan Livingston
Nice catch...! I am using R2015(b?). I guess the help I was looking at was for recent versions and I didn't look at when the capability was added. (My bad!) I really wanted to keep 2015(b?) for backward compatibility of some older code but I guess I'll bite the bullet and upgrade Matlab and update the old code. Fun. I'll upgrade Matlab and see what I get and hopefully remember to update on this post. — user70891

user70891 user70891 · Accepted Answer · 2020-09-27T22:58:54

Matlab Coder generates C code for recursive functions in functions in Matlab 2020b and, based on Ryan Livingston's comment, it probably works from Matlab 2016b and later and most likely doesn't work from Matlab 2016a and earlier. It does not work not on Matlab 2015b. Here are Matlab's recursion-related release notes which shows that code generation for recursion was added in Matlab 2016b.

If you are having problems generating code for recursive functions, the Matlab Coder app will generate C code from the following recursive Matlab code (note that the code works but isn't supposed to do anything useful and is only used to give a simple example of recursion). You can use it as a template and build from there.

%------------------------
function recursion_test()
   %clear all %<-uncomment this line to generate a conversion error 
   recursive_fn();
end %recursive caller
%------------------------
%------------------------
function recursive_fn()

persistent mycount;
if isempty(mycount) %initialize the persistent variable
   mycount = 0;
end

counter = 0;
while(counter<300)
   mycount = mycount + 1;
   if mycount<100 %some generic test condition
      recursive_fn();
   end
   if mycount<200 %another generic test condition
      recursive_fn();
   end %if
   counter = counter+1;
end
disp(counter);
end %recursive function
%------------------------

Matlab Code Generation for Recursive Functions

1 Answers