斐波那契数列的递归函数

题目描述

f(1)=1，f(2)=1；当n>2时，f(n)=f(n-1)+f(n-2)，求斐波那契数列的第n项。

要求使用C和java语言代码实现

1、C语言

#include <stdio.h>
#include <stdlib.h>

int main()
{
	int n,i;
	int num;	
	int Fib(int i);  //声明Fib函数 
	
	printf("您想输出多长的斐波那契数列：");
	scanf("%d",&n);
	printf("\n");
	
	for(i = 1; i <= n ; i++){
		
	num = Fib(i);   //通过一个递归函数获取第n个斐波那契数 
	printf("第%d个斐波那契数是%d\n",i,num);
	
	}

	return 0;
}

//斐波那契数列的递归函数 
int Fib(int i)
{
	if(i == 1)
		return 0;		//第一个数返回 0 
		else if(i == 2)
		return 1;		//第二个数返回 1 
		else 
		return Fib(i-1)+Fib(i-2); //利用递归来求第三个数之后的数 
		
}

2、java语言

 public static void main(String[] args) {
        // 斐波那契数列 1,1,2,3,5,8…
            System.out.println(fun(5));
    }
     
    // //使用递归
    // //i=求第几个数值
    private static int fun(int i) {
        System.out.println("当前数字："+i);
        if (i == 1 || i == 2) {//如果i=1或2，则表示计算第一个和第二个数值，直接返回1。
            return 1;//递归出口
        }
       
        //否则递归调用当前方法，例如i=3 求第三个数值的话 就等于 第二个数值f(3-1)加上第一个数值f(3-2)的和
        return fun(i - 1) + fun(i - 2);
    }

总结

斐波那契数列（Fibonacci sequence），又称黄金分割数列，以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为：1、1、2、3、5、8、13、21、34……在数学上，这一数列以如下递推的方法定义：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。