使用递归的斐波那契数列

使用递归的斐波那契数列

斐波那契数列通过将两个前导数相加来生成后续数。斐波那契数列从两个数开始 - F₀ 和 F₁。F₀ 和 F₁ 的初始值是 1。 F₁ 可以分别取 0、1 或 1、1。

斐波那契数列满足以下条件 −

Fn = Fn-1 + Fn-2

因此，斐波那契数列可以表示为 −

F₈ = 0 1 1 2 3 5 8 13

或者，这样 −

F₈ = 1 1 2 3 5 8 13 21

为了便于说明，F₈ 的斐波那契数列显示为 −

斐波那契迭代算法

首先，我们尝试编写斐波那契数列的迭代算法。

Procedure Fibonacci(n)
   declare f0, f1, fib, loop 
   
   set f0 to 0
   set f1 to 1
   
   <b>display f0, f1</b>
   
   for loop ← 1 to n
   
      fib ← f0 + f1   
      f0 ← f1
      f1 ← fib

      <b>display fib</b>
   end for
	
end procedure

斐波那契递归算法

让我们学习如何创建斐波那契数列的递归算法。递归的基本准则。

START
Procedure Fibonacci(n)
   declare f0, f1, fib, loop 
   
   set f0 to 0
   set f1 to 1
   
   display f0, f1
   
   for loop ← 1 to n
   
      fib ← f0 + f1   
      f0 ← f1
      f1 ← fib

      display fib
   end for

END

示例

以下是上述方法在各种编程语言中的实现 −

#include <stdio.h>
int fibbonacci(int n) {
   if(n == 0){
      return 0;
   } else if(n == 1) {
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
int main() {
   int n = 5;
   printf("Number is: %d", n);
   printf("
Fibonacci series upto number %d are: ", n);
   for(int i = 0;i<n;i++) {
      printf("%d ",fibbonacci(i));            
   }
}

Number is: 5
Fibonacci series upto number 5 are: 0 1 1 2 3 

// 斐波那契数列的 C++ 代码
#include <iostream>
using namespace std;
int fibbonacci(int n) {
   if(n == 0){
      return 0;
   } else if(n == 1) {
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
int main() {
   int n = 5;
   cout<<"Number is: "<<n;
   cout << "
Fibbonacci series upto number "<<n<< " are: ";
   for(int i = 0;i<n;i++) {
      cout << fibbonacci(i) << " ";            
   }
}

Number is: 5
Fibbonacci series upto number 5 are: 0 1 1 2 3  

// 斐波那契数列的 Java 代码
public class Fibonacci {
    public static int fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    public static void main(String[] args) {
        int n = 5;
        System.out.print("Number is: " + n);
        System.out.print("
Fibonacci series upto number " + n + ": ");

        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

Number is: 5
Fibonacci series upto number 5: 0 1 1 2 3 

# 斐波那契数列的#Python 代码
def fibonacci(n):
   if n == 0:
      return 0
   elif n == 1:
      return 1
   else:
      return fibonacci(n-1) + fibonacci(n-2)

if __name__ == "__main__":
   n = 5
   print("Number is ", n)
   print("Fibonacci series upto number ",n, "are: ")
   for i in range(n):
      print(fibonacci(i) , end = " ")

Number is  5
Fibonacci series upto number  5 are: 
0 1 1 2 3