Main Content

Force Code Generator to Use Run-Time Recursion

When your MATLAB® code includes recursive function calls, the code generator uses compile-time or run-time recursion. With compile-time recursion, the code generator creates multiple versions of the recursive function in the generated code. These versions are known as function specializations. With run-time recursion, the code generator produces a recursive function. If compile-time recursion results in too many function specializations or if you prefer run-time recursion, you can try to force the code generator to use run-time recursion. Try one of these approaches:

Treat the Input to the Recursive Function as a Nonconstant

Consider this function:

function y = call_recfcn(n)
A = ones(1,n);
x = 5;
y = recfcn(A,x);
end

function y = recfcn(A,x)
if size(A,2) == 1 || x == 1
    y = A(1);
else
    y = A(1)+recfcn(A(2:end),x-1);
end
end

call_recfcn calls recfcn with the value 5 for the second argument. recfcn calls itself recursively until x is 1. For each recfcn call, the input argument x has a different value. The code generator produces five specializations of recfcn, one for each call. You can see the specializations in the MATLAB Function report.

This image shows the specializations for recfcn in the report. The report shows the five specializations associated with the function.

To force run-time recursion, in call_recfcn, in the call to recfcn, instruct the code generator to treat the value of the input argument x as a nonconstant value by using coder.ignoreConst.

function y = call_recfcn(n)
A = ones(1,n);
x = coder.ignoreConst(5);
y = recfcn(A,x);
end

function y = recfcn(A,x)
if size(A,2) == 1 || x == 1
    y = A(1);
else
    y = A(1)+recfcn(A(2:end),x-1);
end
end

In the MATLAB Function report, you see only one specialization.

This image shows recfcn after the input argument x is treated as a nonconstant value with coder.ignoreConst. The function specializations do not appear in the report anymore.

Make the Input to the Recursive Function Variable-Size

Consider this code:

function z = call_mysum(A)
%#codegen
z = mysum(A);
end

function y = mysum(A)
coder.inline('never');
if size(A,2) == 1
    y = A(1);
else
    y = A(1)+ mysum(A(2:end));
end
end

If the input to mysum is fixed-size, the code generator uses compile-time recursion. To force the code generator to use run-time conversion, make the input to mysum variable-size by using coder.varsize.

function z = call_mysum(A)
%#codegen
B = A;
coder.varsize('B');
z = mysum(B);
end

function y = mysum(A)
coder.inline('never');
if size(A,2) == 1
    y = A(1);
else
    y = A(1)+ mysum(A(2:end));
end
end

Assign Output Variable Before the Recursive Call

The code generator uses compile-time recursion for this code:

function y = callrecursive(n)
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

To force the code generator to use run-time recursion, modify myrecursive so that the output y is assigned before the recursive call. Place the assignment y = n in the if block and the recursive call in the else block.

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

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

Related Topics