MATLAB - Recursive Functions

MATLAB - Recursive Functions

Recursion is a powerful programming concept where a function solves a problem by calling itself. This technique is particularly elegant for problems that can be broken down into smaller, self-similar subproblems, such as traversing tree structures or calculating mathematical series.

The Anatomy of a Recursive Function

Every well-structured recursive function must have at least two essential components:

• Base Case: A condition that stops the recursion. Without a base case, the function would call itself indefinitely, leading to a “stack overflow” error.
• Recursive Step: The part of the function that calls itself, but with a modified input that moves it closer to the base case.

Example 1: Factorial

The factorial of a non-negative integer n, denoted as n!, is the product of all positive integers up to n. It has a natural recursive definition: n! = n * (n-1)!, with the base case 0! = 1.

To create this function, save the following code in a file named factorial_recursive.m:

function result = factorial_recursive(n)
    % A recursive function to calculate the factorial of n.

    % Input validation
    if ~isnumeric(n) || n < 0 || n ~= floor(n)
        error('Input must be a non-negative integer.');
    end

    % Base Case: The condition to stop recursion
    if n == 0
        result = 1;
    else
        % Recursive Step: The function calls itself with a smaller problem
        result = n * factorial_recursive(n - 1);
    end
end

You can then call this function from the MATLAB command window:

fact = factorial_recursive(5)

fact =
   120

fact = factorial_recursive(10)

fact =
   3628800

Example 2: Fibonacci Sequence and Performance

The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2) with base cases F(0) = 0 and F(1) = 1. A naive recursive implementation directly follows this definition.

Save the following code in a file named fibonacci_recursive.m:

function result = fibonacci_recursive(n)
    % A naive recursive function to calculate the n-th Fibonacci number.

    % Base Cases
    if n == 0
        result = 0;
    elseif n == 1
        result = 1;
    else
        % Recursive Step
        result = fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    end
end

Calling this function:

fib = fibonacci_recursive(10)

fib =
    55

Common Pitfall: Poor Performance

While elegant, the fibonacci_recursive function is extremely inefficient. To calculate fib(5), it recalculates fib(3) twice, fib(2) three times, and so on. This is a classic example of a problem where recursion leads to redundant computations and exponential time complexity.

For n > 30, this function will become noticeably slow. A far better approach is an iterative solution or using memoization.

A Better Alternative: Iterative Approach

An iterative solution avoids the overhead of repeated function calls and redundant calculations, making it much faster and more memory-efficient.

% Save in a file named fibonacci_iterative.m
function result = fibonacci_iterative(n)
    if n <= 1
        result = n;
        return;
    end

    f_minus_2 = 0;
    f_minus_1 = 1;

    for i = 2:n
        result = f_minus_1 + f_minus_2;
        f_minus_2 = f_minus_1;
        f_minus_1 = result;
    end
end

Debugging Recursive Functions

• dbstop if error: Type this in the command window. MATLAB will automatically enter debug mode at the line that causes an error, such as a stack overflow from infinite recursion.
• Breakpoints: Place a breakpoint inside your recursive function. You can then step through each call and examine the state of the variables on the function call stack in the Workspace panel.
• Print Statements: A simple fprintf or disp at the start of your function can help you trace the sequence of calls and the values of the inputs.

Code Generation with MATLAB Coder

MATLAB Coder can convert your MATLAB code, including recursive functions, into standalone C/C++ code. This is useful for deploying algorithms on embedded hardware or integrating them with larger systems.

• Compile-Time Recursion: If the depth of the recursion can be determined at compile time (e.g., the input n is a constant), the Coder can often “unroll” the recursion, replacing it with highly efficient, sequential code.
• Run-Time Recursion: If the recursion depth depends on a variable input, the Coder will generate C code that uses the system stack to manage the recursive calls, similar to a standard C implementation. Be aware that this can be limited by the stack size of the target system.