What is Fibonacci Recursion in C- Embedded C Programming Training In Hyderabad

Need Help or More Information?

Questions about this free C programming course, embedded C training or career guidance? Get in touch.

Free C Programming Course | Functions | Lecture 36

Fibonacci Recursion in C

See why Fibonacci recursion in C looks elegant but explodes into millions of calls, then fix it with memoization and a loop that suits embedded systems.

This lecture of our free C programming course is about Fibonacci recursion in C, the example that teaches the most important lesson about recursion: a function can be perfectly correct and still be painfully slow. Factorial and power called themselves once. Fibonacci calls itself twice, and that single difference changes everything. As in the rest of this free C tutorial, we keep C programming for embedded systems in focus by counting calls, measuring RAM and choosing the right technique for a small microcontroller.

By the end you will be able to explain tree recursion, draw the call tree of any small input, and pick between the naive, memoized and iterative versions in your own embedded C programming work.

What You Will Learn

  • The Fibonacci definition and the two conventions used in textbooks
  • How to write Fibonacci recursion in C and print a series
  • What tree recursion is and how to draw a call tree
  • How to count redundant calls and why the count grows exponentially
  • How memoization removes repeated work at the cost of a little RAM
  • Why an iterative loop is usually the best answer in firmware

Prerequisites

  • The earlier lectures on factorial and the recursive power function
  • Arrays and static variables in C
  • Basic use of for and while loops

The Fibonacci Sequence and Its Recursive Definition

Each Fibonacci number is the sum of the two numbers before it. Two starting values are needed, and here textbooks disagree. Many mathematics sources begin with 0 and 1. Some programming books begin with 1 and 1, which simply shifts the sequence by one position. In this course we use the 0, 1 convention, so the first terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Always check which convention a question or interview expects.

Recursive definition used in this lecture
ConditionValue of fib(n)Role
n is 00Base case one
n is 11Base case two
n greater than 1fib(n – 1) + fib(n – 2)Recursive case with two self-calls

Notice there are two base cases. Because the rule reaches back two steps, one base case is not enough: fib(2) would ask for fib(0), which must therefore be defined as well.

Fibonacci Recursion in C: Program with a Call Counter

Instead of only printing numbers, this program also counts how many times the function is entered. That counter is the key to understanding the cost.

#include <stdio.h>
#include <stdint.h>

static unsigned long call_count;

static uint32_t fib_naive(uint32_t n)
{
    call_count++;
    if (n < 2u) {                       /* both base cases: 0 and 1 */
        return n;
    }
    return fib_naive(n - 1u) + fib_naive(n - 2u);
}

int main(void)
{
    const uint32_t samples[] = { 5u, 10u, 20u };
    unsigned i;

    for (i = 0u; i < sizeof samples / sizeof samples[0]; i++) {
        call_count = 0ul;
        uint32_t value = fib_naive(samples[i]);
        printf("n=%2lu  fib=%5lu  calls=%lu\n",
               (unsigned long)samples[i], (unsigned long)value, call_count);
    }
    return 0;
}
$ gcc -Wall -Wextra -std=c99 -o fibn fibn.c
$ ./fibn
n= 5  fib=    5  calls=15
n=10  fib=   55  calls=177
n=20  fib= 6765  calls=21891

Raising n from 10 to 20 doubles the input but multiplies the work by more than a hundred. That is the signature of exponential growth.

Understanding Tree Recursion Through the Call Tree

When a function calls itself twice, the calls branch like a tree instead of forming a single chain. The table below lists every call made while computing fib_naive(5), grouped by depth level. Each row is one level of the tree, read left to right.

Call tree of fib(5) shown level by level
LevelCalls at this levelCount
0fib(5)1
1fib(4), fib(3)2
2fib(3), fib(2), fib(2), fib(1)4
3fib(2), fib(1), fib(1), fib(0), fib(1), fib(0)6
4fib(1), fib(0)2
TotalAll levels together15

Spotting the Wasted Work

Look at how often the same question is asked again. The function has no memory, so fib(2) is recomputed from scratch every time some caller needs it.

How many times each value is computed inside fib(5)
CallTimes computedComment
fib(5)1The request itself
fib(4)1Needed once
fib(3)2Already duplicated
fib(2)3Triplicated
fib(1)5Computed five times
fib(0)3Computed three times

Growth of the Call Count

The number of calls follows its own recurrence: calls(n) equals calls(n – 1) plus calls(n – 2) plus one. The result is roughly proportional to the Fibonacci number itself, so it grows by a factor of about 1.6 for every step in n.

nfib(n)Calls made by naive recursion
5515
1055177
20676521,891
308320402,692,537
40102334155331,160,281

Good News About Stack

Although the time is exponential, the stack depth is only about n. The deepest chain is fib(n) calling fib(n – 1) calling fib(n – 2) down to the base case, and the other branches only start after that chain unwinds. So naive Fibonacci is slow, not necessarily out of memory.

Printing a Fibonacci Series with Recursion

To print the first several terms you can call the function in a loop. Each term restarts its own tree, which is wasteful, but it is fine for small counts.

#include <stdio.h>
#include <stdint.h>

static uint32_t fib_naive(uint32_t n)
{
    return (n < 2u) ? n : fib_naive(n - 1u) + fib_naive(n - 2u);
}

int main(void)
{
    unsigned terms, k;

    printf("How many terms? ");
    if (scanf("%u", &terms) != 1 || terms > 30u) {
        puts("Please enter 0 to 30");
        return 1;
    }
    for (k = 0u; k < terms; k++) {
        printf("%lu ", (unsigned long)fib_naive(k));
    }
    putchar('\n');
    return 0;
}
How many terms? 10
0 1 1 2 3 5 8 13 21 34

Fixing Fibonacci Recursion in C with Memoization

Memoization means remembering answers you have already computed. Before doing real work the function checks a table. If the answer is there, it returns immediately. Otherwise it computes, stores and returns. Every value is calculated exactly once, so the number of calls drops from exponential to roughly 2n.

#include <stdio.h>
#include <stdint.h>

#define FIB_MAX_U32  47u   /* largest term that fits in 32 bits */

static uint32_t memo[FIB_MAX_U32 + 1u];   /* zero means "not computed yet" */

static uint32_t fib_memo(uint32_t n)
{
    if (n < 2u) {
        return n;
    }
    if (memo[n] != 0u) {
        return memo[n];                     /* answer already known */
    }
    memo[n] = fib_memo(n - 1u) + fib_memo(n - 2u);
    return memo[n];
}

int main(void)
{
    printf("fib(40) = %lu\n", (unsigned long)fib_memo(40u));
    return 0;
}
fib(40) = 102334155

The marker value zero is safe because every Fibonacci number from index 1 onward is non-zero. The table costs 48 entries of 4 bytes, which is 192 bytes of RAM, a fair price for turning hundreds of millions of calls into about eighty.

The Embedded Choice: Iterative Fibonacci

When you only need the nth value, a loop that carries two running numbers is the best fit for firmware. It uses constant stack, constant RAM and linear time.

static uint32_t fib_iter(uint32_t n)
{
    uint32_t prev = 0u, curr = 1u, next;

    while (n-- > 0u) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return prev;
}
TechniqueTimeExtra RAMStack depthBest for
Naive recursionExponentialNoneAbout nTeaching, tiny n
Memoized recursionLinearTable of n entriesAbout nRepeated queries on a PC
IterationLinearNoneConstantFirmware and real-time code

Overflow Limits for Fibonacci

Unsigned typeLargest index that fitsValue
uint16_t2446368
uint32_t472971215073
uint64_t9312200160415121876738

Real-World Use Cases

  • Back-off timers that grow by Fibonacci steps when retrying a failed connection
  • Test-data generation for algorithm and overflow testing
  • Understanding any divide-and-conquer algorithm that branches twice, such as merge sort or tree traversal
  • Interview preparation, since Fibonacci is among the most common recursion questions

Common Mistakes and Troubleshooting

SymptomCauseFix
Program seems to hang at n around 45Exponential call count of naive recursionUse memoization or a loop
Off-by-one compared with a textbookDifferent starting convention (0,1 versus 1,1)Confirm the convention first
Wrong value past index 4732-bit overflowSwitch to uint64_t and limit the index
Memo table returns zerosTable not static, or marker clashes with a real valueKeep it static and pick a safe marker
Infinite recursionOnly one base case for a two-step ruleHandle both n equal to 0 and n equal to 1

Best Practices, Performance and Security

  • Count calls before trusting a recursive algorithm that branches more than once.
  • Use memoization when the same sub-answers recur, and size the table at compile time.
  • In embedded C programming prefer iteration unless the data itself is recursive, like a tree.
  • Performance: naive Fibonacci can burn millions of CPU cycles for a modest input, which can break real-time deadlines.
  • Security: an unchecked index from a user or a network message could make the function run for minutes or overflow the table. Validate it against a constant limit.

Summary and Key Takeaways

  • Fibonacci recursion in C uses two base cases and two self-calls.
  • Two self-calls create a call tree and a huge amount of repeated work.
  • Calls grow exponentially: 15 for n equal to 5 and over 331 million for n equal to 40.
  • Memoization and iteration both reduce the work to linear time.
  • Loops are the usual choice for firmware because they need no extra stack.

Conclusion

Fibonacci recursion in C is short to write and expensive to run, and that contrast is the reason it appears in nearly every programming course and interview. You learned to read a call tree, to count repeated calls, and to fix the problem in two different ways. Next in this free embedded C course we meet the Tower of Hanoi, a puzzle where recursion is not just convenient but is the most natural way to think about the solution.

Frequently Asked Questions

Why is Fibonacci recursion in C so slow?

Each call spawns two more calls, and the same sub-problems are solved again and again, so the total number of calls grows exponentially with n.

What is the time complexity of naive recursive Fibonacci?

It is exponential, roughly proportional to 1.618 raised to the power n. Memoized and iterative versions run in linear time.

What is memoization in C?

It is a technique where results of earlier calls are stored in a table, often a static array, so repeated requests are answered without recomputation.

Does Fibonacci start with 0 and 1 or 1 and 1?

Both conventions exist. Mathematics usually starts with 0 and 1, while some programming books start with 1 and 1. State your convention clearly.

Is recursive Fibonacci suitable for microcontrollers?

Rarely. The runtime is unpredictable for larger inputs. An iterative loop gives constant stack use and predictable timing.

How deep does the stack go for naive recursive Fibonacci?

About n frames at most, because the longest chain of nested calls goes from fib(n) down to the base case.

Free C Tutorial for Embedded Engineers

Continue through the free embedded C course on EmbeddedPathashala and practise every concept with examples and interview questions.

Need Help or More Information?

Questions about this free C programming course, embedded C training or career guidance? Get in touch.

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *