递归函数 #

function result = factorial(n)
% FACTORIAL 计算阶乘（递归实现）

    % 基本情况
    if n <= 1
        result = 1;
        return;
    end
    
    % 递归调用
    result = n * factorial(n - 1);
end

function result = recursive_function(params)
    % 1. 基本情况（终止条件）
    if base_condition
        result = base_value;
        return;
    end
    
    % 2. 递归调用
    smaller_problem = reduce(params);
    partial_result = recursive_function(smaller_problem);
    
    % 3. 组合结果
    result = combine(partial_result, params);
end

% 计算累加和
function sum = cumulative_sum(n)
% CUMULATIVE_SUM 计算1到n的和
    
    if n <= 0
        sum = 0;
        return;
    end
    
    sum = n + cumulative_sum(n - 1);
end

cumulative_sum(5)  % 15

function result = my_factorial(n)
% MY_FACTORIAL 计算阶乘
    
    if n < 0
        error('n必须是非负整数');
    end
    
    if n <= 1
        result = 1;
    else
        result = n * my_factorial(n - 1);
    end
end

my_factorial(5)  % 120

function fib = fibonacci(n)
% FIBONACCI 斐波那契数列（递归）
    
    if n <= 0
        fib = 0;
    elseif n == 1
        fib = 1;
    else
        fib = fibonacci(n-1) + fibonacci(n-2);
    end
end

% 优化版本：使用记忆化
function fib = fibonacci_memo(n)
    persistent memo;
    
    if isempty(memo)
        memo = containers.Map('KeyType', 'double', 'ValueType', 'double');
    end
    
    if n <= 0
        fib = 0;
    elseif n == 1
        fib = 1;
    elseif memo.isKey(n)
        fib = memo(n);
    else
        fib = fibonacci_memo(n-1) + fibonacci_memo(n-2);
        memo(n) = fib;
    end
end

function idx = binary_search(arr, target, left, right)
% BINARY_SEARCH 二分查找（递归）
    
    if nargin == 2
        left = 1;
        right = length(arr);
    end
    
    if left > right
        idx = -1;  % 未找到
        return;
    end
    
    mid = floor((left + right) / 2);
    
    if arr(mid) == target
        idx = mid;
    elseif arr(mid) < target
        idx = binary_search(arr, target, mid+1, right);
    else
        idx = binary_search(arr, target, left, mid-1);
    end
end

arr = [1 3 5 7 9 11 13];
idx = binary_search(arr, 7);  % 4

function hanoi(n, from, to, aux)
% HANOI 汉诺塔问题
    
    if n == 1
        fprintf('移动盘子1从%s到%s\n', from, to);
        return;
    end
    
    hanoi(n-1, from, aux, to);
    fprintf('移动盘子%d从%s到%s\n', n, from, to);
    hanoi(n-1, aux, to, from);
end

hanoi(3, 'A', 'C', 'B');

function arr = quick_sort(arr)
% QUICK_SORT 快速排序（递归）
    
    if length(arr) <= 1
        return;
    end
    
    pivot = arr(1);
    less = arr(arr < pivot);
    equal = arr(arr == pivot);
    greater = arr(arr > pivot);
    
    arr = [quick_sort(less), equal, quick_sort(greater)];
end

arr = [3 6 8 10 1 2 1];
sorted = quick_sort(arr);  % [1 1 2 3 6 8 10]

% 递归版本
function result = factorial_recursive(n)
    if n <= 1
        result = 1;
    else
        result = n * factorial_recursive(n - 1);
    end
end

% 迭代版本
function result = factorial_iterative(n)
    result = 1;
    for i = 2:n
        result = result * i;
    end
end

% 递归版本（效率低）
function fib = fib_recursive(n)
    if n <= 1
        fib = n;
    else
        fib = fib_recursive(n-1) + fib_recursive(n-2);
    end
end

% 迭代版本（效率高）
function fib = fib_iterative(n)
    if n <= 1
        fib = n;
        return;
    end
    
    a = 0;
    b = 1;
    for i = 2:n
        fib = a + b;
        a = b;
        b = fib;
    end
end

% 普通递归
function result = factorial(n)
    if n <= 1
        result = 1;
    else
        result = n * factorial(n - 1);  % 递归后还要乘n
    end
end

% 尾递归形式
function result = factorial_tail(n, acc)
    if nargin < 2
        acc = 1;
    end
    
    if n <= 1
        result = acc;
    else
        result = factorial_tail(n - 1, n * acc);  % 尾递归
    end
end

% 累加和尾递归
function sum = sum_tail(n, acc)
    if nargin < 2
        acc = 0;
    end
    
    if n <= 0
        sum = acc;
    else
        sum = sum_tail(n - 1, acc + n);
    end
end

function traverse_tree(node)
% TRAVERSE_TREE 遍历树结构
    
    if isempty(node)
        return;
    end
    
    % 访问当前节点
    disp(node.value);
    
    % 递归遍历子节点
    for i = 1:length(node.children)
        traverse_tree(node.children{i});
    end
end

function draw_fractal(x, y, size, depth)
% DRAW_FRACTAL 绘制分形
    
    if depth == 0
        return;
    end
    
    % 绘制当前图形
    rectangle('Position', [x, y, size, size]);
    
    % 递归绘制四个角
    new_size = size / 3;
    draw_fractal(x, y, new_size, depth-1);
    draw_fractal(x + 2*new_size, y, new_size, depth-1);
    draw_fractal(x, y + 2*new_size, new_size, depth-1);
    draw_fractal(x + 2*new_size, y + 2*new_size, new_size, depth-1);
end

function result = combinations(arr, k)
% COMBINATIONS 生成组合
    
    result = {};
    
    if k == 0
        result = {{}};
        return;
    end
    
    if k > length(arr)
        return;
    end
    
    % 包含第一个元素
    sub_comb = combinations(arr(2:end), k-1);
    for i = 1:length(sub_comb)
        result{end+1} = [{arr(1)}, sub_comb{i}];
    end
    
    % 不包含第一个元素
    sub_comb = combinations(arr(2:end), k);
    result = [result, sub_comb];
end

combs = combinations({'a', 'b', 'c', 'd'}, 2);

% 可能导致栈溢出
function result = deep_recursion(n)
    if n == 0
        result = 0;
    else
        result = 1 + deep_recursion(n - 1);
    end
end

% deep_recursion(100000)  % 可能栈溢出

% 优化：使用迭代
function result = deep_iterative(n)
    result = n;
end

% 斐波那契递归有大量重复计算
% 使用记忆化优化
function fib = fib_memo(n)
    persistent memo;
    
    if isempty(memo)
        memo = containers.Map();
    end
    
    if memo.isKey(n)
        fib = memo(n);
        return;
    end
    
    if n <= 1
        fib = n;
    else
        fib = fib_memo(n-1) + fib_memo(n-2);
    end
    
    memo(n) = fib;
end

function result = safe_recursion(n, max_depth)
    if nargin < 2
        max_depth = 1000;
    end
    
    if n <= 0
        result = 0;
        return;
    end
    
    if max_depth <= 0
        error('递归深度超限');
    end
    
    result = 1 + safe_recursion(n - 1, max_depth - 1);
end

% 递归适用：
% - 问题自然递归定义（树、图）
% - 代码更清晰
% - 递归深度可控

% 迭代适用：
% - 性能要求高
% - 递归深度大
% - 内存受限

function result = safe_recursive(n)
    % 检查输入
    if n < 0
        error('n必须非负');
    end
    
    % 基本情况
    if n == 0
        result = 1;
        return;
    end
    
    % 递归
    result = n * safe_recursive(n - 1);
end