MATLAB - 递归函数

递归是一种强大的编程概念，函数通过调用自身来解决问题。这种技术对于可以分解为更小、自相似子问题的问题（例如遍历树结构或计算数学序列）特别优雅。

递归函数的组成

每个结构良好的递归函数都必须至少包含两个基本组成部分：

基本情况（Base Case）：一个停止递归的条件。如果没有基本情况，函数将无限期地调用自身，导致“堆栈溢出”错误。
递归步骤（Recursive Step）：函数调用自身的部分，但使用修改后的输入，使其更接近基本情况。

示例 1：阶乘

非负整数 n 的阶乘，记作 n!，是所有小于或等于 n 的正整数的乘积。它有一个自然的递归定义：n! = n * (n-1)!，基本情况是 0! = 1。

要创建此函数，请将以下代码保存到名为 factorial_recursive.m 的文件中：

function result = factorial_recursive(n)
    % 一个计算 n 的阶乘的递归函数。

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

    % 基本情况：停止递归的条件
    if n == 0
        result = 1;
    else
        % 递归步骤：函数使用更小的问题调用自身
        result = n * factorial_recursive(n - 1);
    end
end

然后您可以在 MATLAB 命令行窗口中调用此函数：

fact = factorial_recursive(5)

fact =
   120

fact = factorial_recursive(10)

fact =
   3628800

示例 2：斐波那契数列与性能

斐波那契数列定义为 F(n) = F(n-1) + F(n-2)，基本情况是 F(0) = 0 和 F(1) = 1。一个朴素的递归实现直接遵循此定义。

将以下代码保存到名为 fibonacci_recursive.m 的文件中：

function result = fibonacci_recursive(n)
    % 一个计算第 n 个斐波那契数的朴素递归函数。

    % 基本情况
    if n == 0
        result = 0;
    elseif n == 1
        result = 1;
    else
        % 递归步骤
        result = fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
    end
end

调用此函数：

fib = fibonacci_recursive(10)

fib =
    55

常见陷阱：性能低下

尽管优雅，但 fibonacci_recursive 函数极其低效。为了计算 fib(5)，它会重复计算 fib(3) 两次，fib(2) 三次，依此类推。这是一个经典的例子，说明递归会导致冗余计算和指数时间复杂度。

当 n > 30 时，此函数将明显变慢。更好的方法是采用迭代解决方案或使用记忆化（memoization）。

更好的替代方案：迭代方法

迭代解决方案避免了重复函数调用和冗余计算的开销，使其更快且更节省内存。

% 保存为 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

调试递归函数

dbstop if error：在命令行窗口中输入此命令。MATLAB 将在导致错误的行（例如无限递归导致的堆栈溢出）自动进入调试模式。
断点：在递归函数内部设置断点。然后您可以单步执行每次调用，并在工作区面板中检查函数调用堆栈上变量的状态。
打印语句：在函数开头使用简单的 fprintf 或 disp 可以帮助您追踪调用序列和输入值。

使用 MATLAB Coder 生成代码

MATLAB Coder 可以将您的 MATLAB 代码（包括递归函数）转换为独立的 C/C++ 代码。这对于在嵌入式硬件上部署算法或将其与更大的系统集成非常有用。

编译时递归：如果递归深度可以在编译时确定（例如，输入 n 是一个常量），Coder 通常可以“展开”递归，用高效的顺序代码替换它。
运行时递归：如果递归深度取决于变量输入，Coder 将生成使用系统堆栈管理递归调用的 C 代码，类似于标准的 C 实现。请注意，这可能会受到目标系统堆栈大小的限制。