C++ Recursion: Implementing recursive function for fibonacci numbers

Last update on December 20 2024 12:31:35 (UTC/GMT +8 hours)

Write a C++ program to implement a recursive function to get the n^th Fibonacci number.

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers. Starting from 0 and 1, the first few values in the sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144.

Sample Solution:

C Code:

// Recursive function to calculate the nth Fibonacci number
#include <iostream> // Including the Input/Output Stream Library

int fibonacci(int n) {
  // Initial: Fibonacci of 0 is 0, Fibonacci of 1 is 1
  if (n == 0)
    return 0;
  else if (n == 1)
    return 1;

  // Recursive case: Fibonacci of n is the sum of the previous two Fibonacci numbers
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  int n;
  std::cout << "Input a number: "; // Prompting the user to input a number
  std::cin >> n; // Reading the input number from the user

  // Find the nth Fibonacci number using recursion
  int fib_num = fibonacci(n); // Calling the recursive function to calculate Fibonacci number

  std::cout << "The " << n << "th Fibonacci number is: " << fib_num << std::endl; // Displaying the Fibonacci number

  return 0; // Returning 0 to indicate successful execution of the program
}

Sample Output:

Input a number: 1
The 1th Fibonacci number is: 1

Input a number: 9
The 9th Fibonacci number is: 34

Input a number: 14
The 14th Fibonacci number is: 377

Input a number: 19
The 19th Fibonacci number is: 4181

Flowchart:

CPP Code Editor:

Contribute your code and comments through Disqus.

Previous C++ Exercise: Calculating factorial using recursive function.
Next C++ Exercise: Implementing recursive function for sum of digits.