C语言 在 C 中递归计算斐波那契数

Calculating Fibonacci Numbers Recursively in C

提问by Nick Heiner

I'm trying to learn C by writing a simple program to output Fibonacci numbers. It isn't working.

我试图通过编写一个简单的程序来输出斐波那契数来学习 C。它不起作用。

fibonacci.h

斐波那契数

unsigned int fibonacci_recursive(unsigned int n);

fibonacci.c

斐波那契数列

#include <stdio.h>
#include "fibonacci.h"

main() {
    unsigned int i;
    for (i = 0; i < 10; i++) {
        printf("%d\t%n", fibonacci_recursive(i));
    }
    getchar();
}

fibonacci_recursive.c

fibonacci_recursive.c

unsigned int fib_rec(unsigned int n);

main(unsigned int n) {
     return fib_rec(n);
}

unsigned int fib_rec(unsigned int n) {
    if (n == 0) {
        return 0;
     } 
     if (n == 1) {
           return 1;
     }
     return fib_rec(n - 1) + fib_rec(n - 2);
}

This is the error message VS 2010 gives me when I try to build the project:

这是我尝试构建项目时 VS 2010 给我的错误消息：

1>ClCompile:
1>  fibonacci_recursive.c
1>fibonacci_recursive.obj : error LNK2005: _main already defined in fibonacci.obj
1>fibonacci.obj : error LNK2019: unresolved external symbol _fibonacci_recursive referenced in function _main
1>c:\users\odp\documents\visual studio 2010\Projects\Fibonacci\Debug\Fibonacci.exe : fatal error LNK1120: 1 unresolved externals
1>
1>Build FAILED.
1>

What am I doing wrong here? Thanks for helping someone new to C.

我在这里做错了什么？感谢您帮助刚接触 C 的人。

回答by Hyman

Your approach seems strange, you should have:

您的方法似乎很奇怪，您应该：

• a main file (example main.c) with the main method and that includes fibonacci.h
• a fibonacci.hwith the prototype unsigned int fibonacci_recursive(unsigned int n);
• a fibonacci.cwith the implementation of the method, and it should include fibonacci.htoo

• main.c带有 main 方法的主文件（示例），其中包括fibonacci.h
• afibonacci.h与原型unsigned int fibonacci_recursive(unsigned int n);
• 一个fibonacci.c与方法的实现，它应该包括fibonacci.h太

Actually you define mainfunction twice too..

其实你也定义了main两次函数..

main.c

主文件

#include <stdio.h>
#include "fibonacci.h"

main()
{
    unsigned int i;
    for (i = 0; i < 10; i++)
    {
        printf("%d\t%n", fibonacci_recursive(i));
    }
    getchar();
}

fibonacci.h

斐波那契数

unsigned int fibonacci_recursive(unsigned int n);

fibonacci.c

斐波那契数列

#include "fibonacci.h"
unsigned int fibonacci_recursive(unsigned int n)
{
    if (n == 0) 
    {
        return 0;
     } 
     if (n == 1) {
           return 1;
     }
     return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

回答by Ramashalanka

You need \n not %n for your printf. Also, you can simplify as:

您的 printf 需要 \n 而不是 %n。此外，您可以简化为：

#include "fibonacci.h"

unsigned int fibonacci_recursive(unsigned int n) {
if (n < 2) 
    return n;
else
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

回答by andri

You have the main()function defined twice in your project. This is the entry point of your program, and you only need one.

您main()在项目中定义了两次函数。这是您的程序的入口点，您只需要一个。

回答by Tor Valamo

You haven't created a fibonacci_recursive function that you declared in fibonacci.h.

您尚未创建在 fibonacci.h 中声明的 fibonacci_recursive 函数。

回答by Edward Karak

You declared two main()functions, and the new line character is '\n'.

您声明了两个main()函数，换行符是'\n'。

回答by gabolander

Well, I preface that recursive function is not an efficient method to calculate Fibonacci and it may be used for dev training/demonstrations purposes only, because every recursion is stored in stack, and it may also overflow for large fibonacci numbers. It is rather worth the effort to write down a more efficient Fibonacci function that uses a loop, like following code:

好吧，我先说递归函数不是计算斐波那契数的有效方法，它可能仅用于开发培训/演示目的，因为每个递归都存储在堆栈中，并且对于大的斐波那契数也可能溢出。写一个使用循环的更有效的斐波那契函数是相当值得的，例如以下代码：

#include <stdio.h>

#define MAX_ITERS 20


int fibonacci(int);

int main(int argc, char *argv[])
{
    unsigned int iters;

    if(argc>1) {
        iters=atoi(argv[1]);
    } else
        iters=MAX_ITERS;

    fibonacci(iters);

    return 0;
}

int fibonacci(int iterations)
{
   unsigned register int i;
   double first=0.0, second = 1.0, lastsum;
   printf("First %d iterations of Fibonacci series are :\n",iterations);

   for ( i = 0 ; i < iterations ; i++ )
   {
      if ( i <= 1 )
         lastsum = (double)i;
      else
      {
         lastsum = first + second;
         first = second;
         second = lastsum;
      }
      printf("%.0f\n",lastsum);
   }

}

Try to compare by your own, running ./fibonacci 50with this method, for instance on a low cost processor (eg. on a Raspberry PI), and the one with the recursive functionsand 50 first numbers as well, and see the difference! ,-)

尝试自己比较，使用这种方法运行./fibonacci 50，例如在低成本处理器上（例如在 Raspberry PI 上），以及具有递归函数和 50 个第一个数字的处理器，看看有什么不同！,-)