Fibonacci Series in C using Recursion

Each number in the Fibonacci series is calculated by adding the two preceding integers. This series was first described by Italian mathematician Fibonacci in the 13th century and appears often in mathematics and nature.

In computer science, calculating the Fibonacci numbers recursively is a common exercise used to teach recursion. This article will focus on implementing a recursive solution to generate the Fibonacci series in C programming language.

Fibonacci Series in C Explained

Each integer in the Fibonacci series after 0 and 1 is the sum of the two before it:

F(0) = 0 
F(1) = 1
F(n) = F(n-1) + F(n-2), n > 1

The first few Fibonacci numbers are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

This sequence exhibits a certain pattern and mathematical properties that make it interesting for analysis.

Recursion Fundamentals in C

Recursion is a technique in programming where a function calls itself to repeat a computational procedure. Recursion requires:

• • Base case(s) – the condition where the recursion stops
  • Recursive call(s) – the function calling itself with different inputs

For example, a recursive function to calculate factorial:

int factorial(int n) {
  if (n == 0) { // base case 
    return 1;
  }
  return n * factorial(n-1); // recursive call
}

Recursive Approach to Fibonacci in C

The Fibonacci sequence can be calculated using recursion by breaking down the problem into smaller subproblems using the recursive definition of Fibonacci numbers.

The steps are:

1. Base cases:

• • F(0) = 0
  • F(1) = 1

2. Recursive step:

• • To find F(n), recursively find F(n-1) and F(n-2)
  • Then compute F(n) as F(n-1) + F(n-2)

This way, larger Fibonacci numbers are solved by recursively reducing the problem to smaller Fibonacci numbers until a base case is reached.

The base cases provide starting values to build up the solution. The recursive step uses previously solved subproblems to solve larger problems.

The computation of fib(5) can be understood as a recursive breakdown. Initially, we divide it into two sub-problems: fib(4) and fib(3).

When we delve into fib(4), it further disassembles into fib(3) and fib(2). Similarly, fib(3) splits into fib(2) and fib(1). This recursive partitioning continues until we reach the fundamental cases of fib(1) with a value of 1 and fib(0) with a value of 0 in both branches.

Subsequently, each computed value is propagated back up the chain to its parent caller. They accumulate these returned values to determine their own result. This iterative summation continues throughout the entire process until we ultimately obtain the final result for fib(5).

C Code Implementation

#include <stdio.h>

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

int main() {
  int n = 6;
  printf("Fibonacci number %d is %d", n, fib(n));
  return 0;
}

The given C code calculates the 6th Fibonacci number using a recursive function and then prints the result.

Let’s walk through the code and determine the output:

1. The fib function is defined to calculate Fibonacci numbers using recursion.

2. In the main function, the variable n is set to 6.

3. The printf statement prints the 6th Fibonacci number, calculated by calling fib(6).

Now, let’s calculate the Fibonacci number for n = 6 using the fib function:

• fib(6) calls fib(5) and fib(4).
• fib(5) calls fib(4) and fib(3).
• fib(4) calls fib(3) and fib(2).
• fib(3) calls fib(2) and fib(1).
• fib(2) calls fib(1) and fib(0).
• fib(1) returns 1.
• fib(0) returns 0.
• fib(2) returns 1 (the sum of fib(1) and fib(0)).
• fib(3) returns 2 (the sum of fib(2) and fib(1)).
• fib(4) returns 3 (the sum of fib(3) and fib(2)).
• fib(5) returns 5 (the sum of fib(4) and fib(3)).
• Finally, fib(6) returns 8 (the sum of fib(5) and fib(4)).

Output:
Fibonacci number 6 is 8

Comparison with Other Approaches in C

1. Iterative approach

int fib(int n) {
  int a = 0, b = 1, c, i;
  if (n == 0) {
    return a;
  }
  for (i = 2; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }
  return b;
}

The recursive approach is simpler and elegant but less efficient than the iterative solution. Recursion provides a natural way to express the Fibonacci definition. However, iteration avoids call stack overflows for large n.

2. Fibonacci Matrix Method

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

// Define a matrix structure
typedef struct {
    long long int data[2][2];
} Matrix;

// Initialize the identity matrix
Matrix identityMatrix() {
    Matrix mat;
    mat.data[0][0] = 1;
    mat.data[0][1] = 1;
    mat.data[1][0] = 1;
    mat.data[1][1] = 0;
    return mat;
}

Multiply two matrices

Matrix multiply(Matrix a, Matrix b) {
    Matrix result;
    int i, j, k;
    for (i = 0; i < 2; i++) {
        for (j = 0; j < 2; j++) {
            result.data[i][j] = 0;
            for (k = 0; k < 2; k++) {
                result.data[i][j] += a.data[i][k] * b.data[k][j];
            }
        }
    }
    return result;
}

Calculate the Nth power of a matrix

Matrix matrixPower(Matrix mat, int n) {
    Matrix result = identityMatrix();
    while (n > 0) {
        if (n % 2 == 1) {
            result = multiply(result, mat);
        }
        mat = multiply(mat, mat);
        n /= 2;
    }
    return result;
}

Find the Nth Fibonacci number using the matrix approach

long long int nthFibonacci(int n) {
    if (n <= 0) return 0;
    Matrix fibMatrix = matrixPower(identityMatrix(), n - 1);
    return fibMatrix.data[0][0];
}

int main() {
    int n;
    printf("Enter the value of N: ");
    scanf("%d", &n);

    long long int result = nthFibonacci(n);
    printf("The %dth Fibonacci number is: %lld\n", n, result);

    return 0;
}

Conclusion

This article covered a recursive algorithm for generating Fibonacci numbers and its implementation in C. Recursion in C is an important concept in programming. The Fibonacci sequence presents a good introductory example of applying recursion principles. Further exploration of topics like recursion runtime analysis and optimizations can build stronger foundations in computer science.