斐波那契递归值跟踪器 [英] Fibonacci Recursion Value tracer

问题描述

所以我需要编写一个程序，该程序使用递归函数按输入参数的创建顺序存储它们的值.

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

  [f trace] = fibo_trace(6，[])f =8跟踪=6 4 2 3 1 2 5 3 1 2 4 2 3 1 2 

trace 是用来初始化递归调用的值，而 f 是斐波那契数列中的第六个元素.

这是我的代码

 函数[f，trace] = fibo_trace(n，v)持久性％必须指定永久v = n;ptrace = cat(2，ptrace，v);如果n< = 2f = 1；别的f = fibo_trace(n-2)+ fibo_trace(n-1);结尾trace = ptrace;结尾 

但是，如果测试了多个条件，则使用持久变量将无法提供正确的输出.我需要在不使用持久变量或全局变量的情况下进行计算，有人可以在这里帮助我吗?

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

解决方案

首先，请注意，从未使用输入的 v ，您总是用 n 覆盖它./p>

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

这两点意味着您可以摆脱持久变量，并稍微简化代码.对于前面的两个迭代，我们只需要分别调用 fibo_trace .

 函数[f，trace] = fibo_trace(n)如果n< = 2％起始元素f = 1的迹线应仅为'n'f = 1；trace = n;别的％获取以前的值及其踪迹[f1，t1] = fibo_trace(n-1);[f2，t2] = fibo_trace(n-2)；％计算输出f = f1 + f2;迹线= [n，t2，t1];结尾结尾 

结果:

  [f，trace] = fibo_trace(6)f =8跟踪=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)分别乘以计算时间.

So I need to write a program which uses a recursive function to store the value of input arguments in the order they were made.

e.g. If my function is [f trace]=fibo_trace(6,[]) it should return

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

With trace being the values with which the recursive call is being initialized and f being the 6th element in the fibonacci series.

Here is my code

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

But using a persistent variable does not give proper output if multiple conditions are tested. I need to compute this without using a persistent or global variable, can anyone help me out here?

When I don't use a persistent variable only the latest value of n is stored in vector v instead of the entire set of values.

解决方案

First, note that your input v is never used, you always overwrite it with n.

Next, note that your calls to fibo_trace(n-1) and (n-2) could return trace, you're just choosing not to. We can take advantage of the 2nd output to build the trace array.

These two points mean you can get rid of the persistent variable, and simplify the code a bit. We just need to make separate calls to fibo_trace for the two previous iterations.

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

Result:

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

There's some optimisation to be had here, since fibo_trace(n-1) will itself call fibo_trace(n-1), so computing fibo_trace(n-2) separately is multiplying the computation time.

这篇关于斐波那契递归值跟踪器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！