C++函数内的递归计数器

Question

我目前正在做一个关于递归函数的作业。被要求编写一个斐波那契程序，并且没有遇到太多问题。但是我需要为它制作一个计数器，这就是我卡住的地方。

我有这个函数：

int fibonacci(int n)
{
    if( n == 0 )
    {
        //my fibonacci code 
    }
    else if( n == 1 )
    {
        //my fibonacci code
    }
    else 
    { 
        //my fibonacci code
    }
}

所以我如何在这个函数中添加一个计数器呢？每次添加一个计数器它都会返回错误的数字。

编辑：只是为了澄清，我的函数生成斐波那契数列没有问题。我只是想在函数内部添加一个计数器，以便每次生成一个斐波那契数时可以看到它被调用的次数。

我已经尝试过下面的其中一种方法，在主函数中初始化计数器，然后在递归中递增它，但不知道数字是否正确。例如，如果我的斐波那契数是610，它说我调用函数609次，这是正确的吗？

- user2661167

---

你如何添加那个无法正常工作的计数器？ - sharptooth

在函数中使用 static 变量作为计数器。 - lapk

是的，计数只对函数的调用和递归深度有意义。但他仍然需要先添加主要内容。 - mvw

@mvw 我同意，"did so with out much issue"并不清楚是否表示他有一个工作的序列生成器（这段代码肯定不是）。但是，OP们往往认为他们的代码是某种国家机密，并且表现出一种相当奇怪的倾向，不粘贴真正的代码，因此有时直到你真正挤压一段时间才能确定。 - WhozCraig

@PetrBudnik 当 top 函数返回时，您将如何重置计数器？ - Neil Kirk

Answer 1

我猜您只是需要演示目的的计数，对吧？通过传递一个引用计数器变量并在每次调用开始时增加它，应该可以很容易地实现调用计数，如下所示：

#include <iostream>

// ...

int fibonacci(int n, int &count)
{
    ++count;
    // other code ...

    // and every time you call fibonacci recursively,
    // simply pass in the same reference, like so:
    if (...) {
        fibonacci (new_n, count);
    }
}

int main(int argc, char** argv)
{
    // call it with an int variable initialized to 0:
    int fibCnt = 0;
    fibonacci(10, fibCnt);
    std::cout << "Function was called "<<fibCnt<<" times"<<std::endl;
}

- codeling

---

这是我能从OP的问题中看到的唯一逻辑推断。除了阶乘之外，斐波那契数列在大约一百万个网站上以代码形式提供。我很难理解他遇到的问题是实现算法，而更可能是他正在努力应对这个问题。 - WhozCraig

@WhozCraig 恰好和我的想法一致 ;) - codeling

只是为了澄清，我的生成斐波那契数列的函数运行良好。我只是想在函数内部加入一个计数器，以便查看每个生成的斐波那契数列调用了多少次该函数。 - user2661167

@user2661167，这正是我的解决方案所提供的，不是吗？ - codeling

Answer 2

您不需要任何计数器。您的代码已经非常接近了。

int fibonacci(int n)
{
    if( n == 0 )
    {
        return f_0
    }
    else if( n == 1 )
    {
        return f_1
    }
    else 
    { 
        return f_n using recursion
    }
}

由于斐波那契数列是通过递归定义的，最后一个情况很明显。其他两种情况只是为了关闭递归关系，即避免最后一个情况导致无限循环。

- Walter

---

顺便提一下，@mvw，斐波那契数列从(0,1)开始，而不是(1,1)。当询问序列中第N个数字时，这会有所区别。 - WhozCraig

我需要查一下。我有一个版本在脑海中，其中n更像是一个编号（从0开始），但我猜你指的是例如兔子交配的那个版本，其中它表示兔子的数量。 - mvw

@mvw 链接已在先前的评论中提供。 - WhozCraig

@WhozCraig 很有趣，我的错误与任务并不无关，请查看我的更新答案。 - mvw

Answer 3

使用结构体可能是答案。

struct factorial
{
  factorial() : counter(0)
  {}

  uint64_t foo(uint64_t x) {
    ++counter;

    if(x < 2)
      return 1;
    else
      return x * foo(x - 1);
  }

  template <class T>
  T operator()(const T& x) {
    return foo(x);
  }

  uint64_t counter;
} factorial;

在这种情况下，foo 是阶乘函数。但它没有这个名称，因为结构的使用将是如此。

// output and calls
struct factorial foo;
std::cout << foo(5) << "\n";
std::cout << foo.counter << "\n";

// output
std::cout << factorial(5) << "\n";

- Moises Rojo

---

只需将foo更改为斐波那契递归实现，并将名称更改为“fibonacci”。 - Moises Rojo

Answer 4

先完成代码。 我给你递归方程：

fib(0) = *deleted*
fib(1) = *deleted*
fib(n) = *deleted*

你的计数器（你应该在问题中仍然指定）通常可以通过在函数外定义全局变量来实现，但可以在函数内部更改。

参考问题的编辑：

你的数字不好。为了不再破坏你的任务，我会用 Erlang 给你答案，这样你还有一些工作要做，以找出如何在你的 C++ 任务中正确地完成它。 :-)

-module(fib).

-export([f/1]).

%% returns a tupel { fibonacci value, number function calls }
f(0) -> {0, 1};
f(1) -> {1, 1};
f(X) -> 
    {F1, C1} = f(X - 1),  %% decompose tuple
    {F2, C2} = f(X - 2),
    {F1 + F2, C1 + C2}.  %% return value

从shell运行这个程序将会得到:

Eshell V5.10.1  (abort with ^G)
1> c("q:/doc/erlang/fib", [{outdir, "q:/doc/erlang/"}]).
{ok,fib}
2> fib:f(0).
{0,1}
3> fib:f(1).
{1,1}
4> fib:f(2).
{1,2}
5> fib:f(3).
{2,3}
6> fib:f(4).
{3,5}
7> fib:f(5).
{5,8}
8> fib:f(6).
{8,13}
9> fib:f(7).
{13,21}
10> fib:f(15).
{610,987}
11> 

因此，我需要调用 987 次函数才能得到 F(15) = 610 的值。

有趣的是，在注释中我们谈论了 Fibonacci 递归 F 的适当起始条件（情况类似于微分方程，不同的起点会使您进入不同的轨迹/解决方案）。

我错了，F(0) = 1 和 F(1) = 1，而 @WhozCraig 正确指出应该是 F(0) = 0 和 F(1) = 1。

如果您查看上面的 Erlang 代码，您会发现产生函数调用数的系列计算也是 Fibonacci 类型的（将系列的最后两个成员相加），但那个是具有起始值 1 和 1 的那个! :-)

- mvw

---

@Walter 好的，我撤回了 - 我希望他卡在编程上而不是数学上。 - mvw

抱歉，我无法取消我的投票...您必须再次编辑。 - Walter

没事了，我在看到回复之前已经完成了代码。我之前把计数器放错位置了，导致计数出现问题。 - user2661167