Need Help or More Information?
Questions about this free C programming course, embedded C training or career guidance? Get in touch.
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
staticvariables in C - Basic use of
forandwhileloops
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.
| Condition | Value of fib(n) | Role |
|---|---|---|
| n is 0 | 0 | Base case one |
| n is 1 | 1 | Base case two |
| n greater than 1 | fib(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.
| Level | Calls at this level | Count |
|---|---|---|
| 0 | fib(5) | 1 |
| 1 | fib(4), fib(3) | 2 |
| 2 | fib(3), fib(2), fib(2), fib(1) | 4 |
| 3 | fib(2), fib(1), fib(1), fib(0), fib(1), fib(0) | 6 |
| 4 | fib(1), fib(0) | 2 |
| Total | All levels together | 15 |
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.
| Call | Times computed | Comment |
|---|---|---|
| fib(5) | 1 | The request itself |
| fib(4) | 1 | Needed once |
| fib(3) | 2 | Already duplicated |
| fib(2) | 3 | Triplicated |
| fib(1) | 5 | Computed five times |
| fib(0) | 3 | Computed 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.
| n | fib(n) | Calls made by naive recursion |
|---|---|---|
| 5 | 5 | 15 |
| 10 | 55 | 177 |
| 20 | 6765 | 21,891 |
| 30 | 832040 | 2,692,537 |
| 40 | 102334155 | 331,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;
}
| Technique | Time | Extra RAM | Stack depth | Best for |
|---|---|---|---|---|
| Naive recursion | Exponential | None | About n | Teaching, tiny n |
| Memoized recursion | Linear | Table of n entries | About n | Repeated queries on a PC |
| Iteration | Linear | None | Constant | Firmware and real-time code |
Overflow Limits for Fibonacci
| Unsigned type | Largest index that fits | Value |
|---|---|---|
| uint16_t | 24 | 46368 |
| uint32_t | 47 | 2971215073 |
| uint64_t | 93 | 12200160415121876738 |
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
| Symptom | Cause | Fix |
|---|---|---|
| Program seems to hang at n around 45 | Exponential call count of naive recursion | Use memoization or a loop |
| Off-by-one compared with a textbook | Different starting convention (0,1 versus 1,1) | Confirm the convention first |
| Wrong value past index 47 | 32-bit overflow | Switch to uint64_t and limit the index |
| Memo table returns zeros | Table not static, or marker clashes with a real value | Keep it static and pick a safe marker |
| Infinite recursion | Only one base case for a two-step rule | Handle 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