Fibonacci递归值跟踪器

Question

因此，我需要编写一个程序，该程序使用递归函数按照输入参数的生成顺序存储输入参数的值。

例如，如果我的函数是[f trace]=fibo_trace(6,[])，它应该返回

[f trace]=fibo_trace(6,[])
f=
8
trace=
6     4     2     3     1     2     5     3     1     2     4     2     3     1     2

trace是初始化递归调用的值，f是斐波那契级数中的第6个元素。

这是我的代码

function [f,trace] = fibo_trace(n,v)

persistent ptrace;   % must specify persistent

v=n; 
ptrace=cat(2,ptrace,v);


if n <= 2
f = 1;
else
f = fibo_trace(n-2) + fibo_trace(n-1);
end
trace=ptrace;
end

但是，如果测试了多个条件，使用持久变量并不能给出正确的输出。我需要在不使用持久变量或全局变量的情况下计算它，有人能帮我吗？

当我不使用持久变量时，只有n的最新值存储在向量v中，而不是整个值集。

Answer 1

首先，请注意，您的输入v从未使用过，您总是用n覆盖它。

接下来，请注意，您对fibo_trace(n-1)和(n-2)的调用可能会返回trace，您只是选择不返回。我们可以利用第二个输出来构建trace数组。

这两点意味着您可以去掉持久变量，并稍微简化代码。我们只需要为前两次迭代分别调用fibo_trace。

function [f,trace] = fibo_trace(n)     
if n <= 2
% The trace should just be 'n' for the starting elements f=1
f = 1;
trace = n;
else
% Get previous values and their traces
[f1, t1] = fibo_trace(n-1);
[f2, t2] = fibo_trace(n-2);
% Compute the outputs
f = f1 + f2;
trace = [n, t2, t1];
end
end

结果：

[f, trace] = fibo_trace(6)
f =
8
trace =
6     4     2     3     1     2     5     3     1     2     4     2     3     1     2

这里需要进行一些优化，因为fibo_trace(n-1)本身将调用fibo_trace(n-1)，因此单独计算fibo_trace(n-2)是计算时间的乘积。