斐波那契数列（递归及非递归）C/C++实现

野性酷女 2022-04-03 05:23 302阅读 0赞

# 递归实现斐波那契数列 #

## 以下是正确C++源代码： ##

### 1.递归实现Fibonacci数列： ###

#include<iostream> 
    #include<stdio.h>
    using namespace std;
    
    //Fibonacci数列递归解法 C++ 实现
    int Fib(int n) 
    {
    	if(n==0) 
    		return 0;
    	else if(n==1)
    		return 1;
    	else
    		return Fib(n-1)+Fib(n-2);
    }
    int main()
    {
    	int n;
    	cout<<"请输入一个数：";
    	cout<<endl;
    	cin>>n;
    	cout<<Fib(n)<<endl;
    	return 0;
    }

### 2.非递归实现Fibonacci数列： ###

#include<stdio.h> 
    #include<iostream>
    
    //Fibonacci数列非递归 C++ 实现 
    using namespace std;
    
    int fib(int n)
    {
    	if(n==0)
    		return 0;
    	if(n==1)
    		return 1;
    	int f1=1;
    	int f2=0;
    	int fn=0;
    	for(int i=2;i<=n;i++) 
    	{
    		fn=f2+f1;
    		f2=f1;
    		f1=fn;
    	}
    	return fn;
    }
    
    int main()
    {
    	int n;
    	cout<<"请输入一个整数：";		//表示要求的是数列中的第几个数。 
    	cout<<endl; 
    	cin>>n;
    	cout<<fib(n)<<endl;
    	return 0;
    }

### 以下是正确C++源代码： ###

### 1.递归实现Fibonacci数列： ###

#include<stdio.h>
    int fib(int n);
    int main(){
    	int n;
    	scanf("%d",&n);
    	printf("%d\n",fib(n));
    	return 0;
    }
    int fib(int n){
    	int s;
    	if(n==1||n==2)  s=1;
    	else{
    		s=fib(n-1)+fib(n-2);
    	}
    	return s;
    }

###  2.非递归实现Fibonacci数列： ###

#include<stdio.h>
    int fib(int n);
    int main(){
    	int n;
    	scanf("%d",&n);
    	printf("%d\n",fib(n));
    	return 0;
    }
    int fib(int n){
    	int f1=1;
    	int f2=1;
    	int s;
    	if(n==1||n==2)  return 1;
    	else{
    		for(int i=3;i<=n;i++){
    			s=f1+f2;
    			f1=f2;
    			f2=s;
    		}
    		return s;
    	}
    }

### **注：** ###

斐波那契数列：

1   1   2   3   5   8   。。。

即后一个数是前面两个数据之和。