写一个递归函数，returns一堆斐波那契数列

Question

我的老师刚刚在考试中问了这个问题，我不知道该从哪里继续。更多细节，函数原型如下：

stack<int> Fibonacci_sequence(int n); //fibonacci numbers count up to n

关键是这个函数是递归的，它应该 return 堆栈数据类型。在我看来，我不认为这是可能的事情，但我的老师问了！！

P.s: 抱歉，我的语言是 C++

Answer 1

function stack<int> Fibonacci_sequence(int n) {
    if n == 0 {
        var a stack<int>;
        a.push(0);
        return a
    } else if n == 1 {
        var a stack<int>;
        a.push(0);
        a.push(1);
        return a
    } else
        var temp int;
        var seq int;
        seq = Fibonacci_sequence(n-1);
        temp = seq.pop;  
        seq.push(temp);
        seq.push(temp);
        //above: the top element of the stack must be duplicated because it
        //is popped off in the process of calculating the sum.
        seq.push(seq.pop()+Fibonacci_sequence(n-2).pop());
        return seq
    }
}

上面是一个函数，它只是用伪代码编写的，因为您没有指定语言。希望这会有所帮助，提出来很有趣！感谢您提出有趣的问题。

Answer 2

由于您没有指定语言，并且您指定它是考试，这里是Ruby。 Ruby 为数组提供堆栈操作，但我在下文中仅使用 push 和 pop 操作，因此您应该能够轻松地将其翻译成您选择的语言。

def fib(n)  # no explicit return type, since everything's an object in Ruby
  fail "negative argument not allowed" if n < 0
  if n > 1
    stack = fib(n - 1)
    # grab the last two values...
    f_n_1 = stack.pop
    f_n_2 = stack.pop
    # ...and use them to calculate the next.
    # The value of this expression is the resulting stack, return it
    return stack.push(f_n_2).push(f_n_1).push(f_n_1 + f_n_2)
  elsif n == 1
    return fib(0).push(1)
  else
    return [].push(0)
  end
end

p fib(10)     # => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

您可能需要将其翻译成您的考试语言，但这是合适的。

Answer 3

这是我基于@Elliot pseudo 的 C++ 代码，它出现了错误，我在代码中指定了这些错误。我刚刚发现 pop() 没有 return 值，我要解决这个问题。

stack<int> Fibonacci_sequence(int n)
{
    if (n == 0) {
        stack<int> a;
        a.push(0);
        return a;
    }
    else if (n == 1) {
        stack<int> a;
        a.push(0);
        a.push(1);
        return a;
    }
    else
    {
        int temp;
        temp = Fibonacci_sequence(n - 1).pop(); //error C2440: '=': cannot convert from 'void' to 'int'
        Fibonacci_sequence(n - 1).push(temp);
        Fibonacci_sequence(n - 1).push(temp);
    //above: the top element of the stack must be duplicated because it
    //is popped off in the process of calculating the sum.
        return Fibonacci_sequence(n - 1).push(Fibonacci_sequence(n - 1).pop() + Fibonacci_sequence(n - 2).pop());//error C2186: '+': illegal operand of type 'void'
    }
}

写一个递归函数，returns一堆斐波那契数列

Write a recursive function that returns a stack of Fibonacci sequence

recursion

stack

fibonacci