如何使用递归获得斐波那契数列？

Question

我正在尝试使用递归查找 fib 序列，但我的函数一直给我一个错误。

function y = r_nFib(seq, n)
y = zeros(1,n);
for m = 1:n
    y(m) = r_nFib(m);
end
if seq == 0
    y = [0 y];
else
    y = [seq, seq, y];
function y = r_nFib(seq, n)
if n<3
   y(1:n) = 1;
else
    y(n) = r_nFib(n-2) + r_nFib(n-1);
end
    y = y(n);
end
end

n是fib序列的长度，seq是起始数。如果 seq 为 0 那么序列将如何开始

y = [0 1 1 2 3 5 8] % first two number will be the 0 and 1

如果 seq 不是 0，则

如果序列=2；

y = [2 2 4 6 10] % first two number will be the seq

如何更正我的函数以得到正确的答案。我从未使用过递归，而且我是新手。任何帮助将不胜感激。

y = r_nFib(4,10)
y = [4 4 8 12 20 32 52 84 136 220];

谢谢。

Answer 1

这是我为 matlab 输入的解决方案，解释了递归：

递归方法的工作原理是在每次调用该方法时将一个较大的问题分解成较小的问题。这使您可以分解一个困难的问题；阶乘求和，转化为一系列更小的问题。

每个递归函数有两部分：
1) 基本情况：我们关心评估的最低值。通常这会变为零或一。

if (num == 1)
  out = 1;
end

2) 一般情况：一般情况是我们在到达基本情况之前要调用的情况。我们再次调用该函数，但这次比上一个函数开始时少 1。这使我们能够朝着基本情况努力。

out = num + factorial(num-1);

这个语句意味着我们要首先调用比this函数少1的函数；我们从 3 开始，下一次调用从 2 开始，之后的调用从 1 开始（这触发了我们的基本情况！）

一旦达到我们的基本情况，方法"recurse-out"。这意味着它们向后反弹，回到调用它的函数中，从它下面的函数中获取所有数据！
正是在这一点上我们的求和实际上发生了。

一旦达到原始函数，我们就有了最终的求和。

例如，假设您想要前 3 个整数的总和。第一个递归调用传递了数字 3.

  function [out] = factorial(num)
     %//Base case
     if (num == 1)
        out = 1;
     end
  %//General case
  out = num + factorial(num-1);

遍历函数调用：

factorial(3); //Initial function call

//Becomes..
factorial(1) + factorial(2) + factorial(3) = returned value

结果是 6！

Answer 2

function y = r_nFib(seq, n)

if length(seq) == 1
    if seq == 0
        seq = [0, 1];
    else
        seq = [seq, seq];
    end
end

if length(seq) >= n
    y = seq;
else
    y = r_nFib([seq (seq(end - 1) + seq(end))], n);
end

如何使用递归获得斐波那契数列？

How to get fibonacci sequence using recursion?

recursion

matlab

fibonacci