Fibonacci Using Recursion in DSA C - Build from Scratch

Fibonacci Using Recursion

📖 Scenario: You are helping a friend understand how to calculate Fibonacci numbers using a simple function that calls itself.The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.

🎯 Goal: Build a C program that uses a recursive function to find the Fibonacci number at a given position.

📋 What You'll Learn

Create a recursive function called fibonacci that takes an integer n and returns the Fibonacci number at position n.

Use base cases for n == 0 and n == 1.

Call the fibonacci function from main to find the Fibonacci number for n = 6.

Print the result using printf.

💡 Why This Matters

🌍 Real World

Fibonacci numbers appear in nature, computer algorithms, and financial models. Understanding recursion helps solve many problems.

💼 Career

Knowing recursion and how to implement it in C is important for software development, especially in algorithm design and problem solving.

1

Create the main function and variable

Write a main function and create an integer variable called n set to 6.

DSA C

int main() {
    // Your code here
}

Hint

The main function is where the program starts. Declare int n = 6; inside it.

2

Write the recursive fibonacci function

Write a recursive function called fibonacci that takes an integer n and returns an integer. Use these rules: if n == 0, return 0; if n == 1, return 1; otherwise return fibonacci(n - 1) + fibonacci(n - 2).

DSA C

int main() {
    int n = 6;
    return 0;
}

// Your code here

Hint

The function calls itself with smaller values until it reaches 0 or 1.

3

Call fibonacci function and store result

Inside main, create an integer variable called result and set it to the value returned by calling fibonacci(n).

DSA C

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

int main() {
    int n = 6;
    // Your code here
    return 0;
}

Hint

Call fibonacci(n) and save it in result.

4

Print the Fibonacci result

Add #include <stdio.h> at the top. Inside main, use printf to print the text "Fibonacci number at position 6 is: %d\n" with the value of result.

DSA C

#include 

int fibonacci(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2];
    }
}

int main() {
    int n = 6;
    int result = fibonacci(n);
    // Your code here
    return 0;
}

Hint

Use printf with the format string and result to show the answer.