Understanding recursion in c is essential for any programmer learning C or C++. A c recursive function calls itself repeatedly -directly or indirectly -until a base condition terminates the chain. Recursion elegantly solves problems that have natural self-similar structure: factorials, Fibonacci, tree traversal, backtracking, and parsing.
This guide covers all types of recursion in c, working code for fibonacci using recursion in c, c programming recursion examples for classic problems, recursion in c++ differences, c# recursion, and a complete recursive descent parser program in c.
What is Recursion in C?
Recursion in c is a programming technique where a function calls itself to solve progressively smaller sub-problems until a base case terminates the chain. Every c recursive function must have: (1) a base case that returns without calling itself, and (2) a recursive case that moves toward the base case.
Component |
Description |
Example (Factorial) |
Base Case |
Terminates recursion -returns a direct value |
if (n == 0) return 1; |
Recursive Case |
Calls itself with a smaller / simpler input |
return n * factorial(n-1); |
Convergence |
Each recursive call must move closer to the base case |
n decreases by 1 each call |
Return Value |
Each call uses the return value of the next call |
factorial(4) uses factorial(3) |
Note: Without a properly defined base case, a recursive function will call itself indefinitely -consuming stack memory until a stack overflow crash occurs. |
Learn More: Advantages and Disadvantages of Arrays in C, C++, and Java
POSTGRADUATE PROGRAM IN
Multi Cloud Architecture & DevOps
Master cloud architecture, DevOps practices, and automation to build scalable, resilient systems.
How Does C Recursion Work?
When a c recursive function is called, the operating system pushes a new stack frame onto the call stack. This frame stores the function’s local variables, parameters, and return address. Each recursive call adds another frame. When the base case is hit, frames unwind in LIFO order -each returning its value to the caller above it.
|
Syntax and Examples of C Recursion
General Syntax
|
Example: Factorial
// c recursion examples -factorial
int factorial(int n) {
if (n == 0) return 1; // Base case
return n * factorial(n - 1); // Recursive case
}
int main() {
printf("%d\n", factorial(5)); // Output: 120
printf("%d\n", factorial(0)); // Output: 1
return 0;
}
Example: Sum of Natural Numbers
// c recursive function examples -sum of 1 to n
int sum(int n) {
if (n == 0) return 0; // Base case
return n + sum(n - 1); // Recursive case
}
int main() {
printf("%d\n", sum(10)); // Output: 55
return 0;
}
Types of Recursion in C
The types of recursion in c are classified by the call pattern and whether the recursive call is the last operation in the function. Understanding all types of recursion in c is essential for choosing the right pattern and optimising performance.
Type |
Description |
Optimisable? |
Example Use Case |
Direct Recursion |
Function calls itself directly |
Yes (tail call) |
Factorial, Fibonacci, sum |
Indirect Recursion |
Functions call each other in a cycle |
Limited |
State machines, mutual recursion |
Tail Recursion |
Recursive call is the last operation |
Yes -compiler optimises to loop |
Accumulator patterns, linear search |
Non-Tail Recursion |
Operations performed after recursive call returns |
No |
Factorial, Fibonacci (standard) |
Linear Recursion |
One recursive call per invocation |
Yes (tail form) |
Factorial, sum, reverse |
Tree/Binary Recursion |
Two or more recursive calls per invocation |
No |
Fibonacci, merge sort, tree traversal |
1. Direct Recursion
A c recursive function that calls itself directly within its own body.
|
2. Indirect Recursion
Two or more functions call each other in a circular chain -none calls itself directly.
|
3. Tail Recursion vs Non-Tail Recursion
In tail recursion, the recursive call is the very last operation -allowing compilers to optimise it into a loop (tail-call optimisation). In non-tail recursion, operations are performed after the recursive call returns, requiring the call stack to be maintained.
|
Dimension |
Tail Recursion |
Non-Tail Recursion |
Recursive call position |
Last statement in function |
Not the last -operations follow |
Compiler optimisation |
Yes -converted to iterative loop |
No -full stack maintained |
Stack usage |
O(1) with optimisation |
O(n) -one frame per call |
Performance |
More efficient |
Less efficient at deep depths |
Example |
factTail(n, acc) |
factNonTail(n) |
82.9%
of professionals don't believe their degree can help them get ahead at work.
Memory Allocation of Recursive Method in C
Each c recursive function call creates a new stack frame containing local variables, parameters, and the return address. Frames are stacked (LIFO) and popped as calls return. Deep recursion in c with large input can exhaust stack memory -causing a stack overflow.
// Memory allocation example -c programming recursion examples
int display(int n) {
if (n == 0) return 0; // Terminating condition
printf("%d ", n);
return display(n - 1); // Recursive call
}
// Stack frames for display(3):
// Frame 1: n=3 → prints 3, calls display(2)
// Frame 2: n=2 → prints 2, calls display(1)
// Frame 3: n=1 → prints 1, calls display(0)
// Frame 4: n=0 → returns 0 (base case -unwinding begins)
// Output: 3 2 1
Event |
Stack Action |
Memory Impact |
Function call |
New frame pushed |
Stack grows by 1 frame |
Local variable declared |
Stored in current frame |
Part of current frame’s memory |
Base case reached |
No new frame -returns immediately |
Maximum stack depth reached |
Return from recursive call |
Frame popped |
Stack shrinks by 1 frame |
Stack overflow |
Stack exhausted |
Program crash -increase stack or use iteration |
Fibonacci Using Recursion in C
Fibonacci using recursion in c is one of the most studied c recursion examples because it demonstrates both the elegance and the performance cost of naive recursion. The Fibonacci sequence is defined as F(n) = F(n-1) + F(n-2), with base cases F(0)=0 and F(1)=1.
Basic Fibonacci Using Recursion in C
// fibonacci using recursion in c -basic version
int fibonacci(int n) {
if (n == 0) return 0; // Base case 1
if (n == 1) return 1; // Base case 2
return fibonacci(n-1) + fibonacci(n-2); // Tree recursion
}
int main() {
int n = 10;
printf("Fibonacci sequence up to F(%d):\n", n);
for (int i = 0; i <= n; i++)
printf("F(%d) = %d\n", i, fibonacci(i));
return 0;
}
// Output (first 6):
// F(0)=0 F(1)=1 F(2)=1 F(3)=2 F(4)=3 F(5)=5 ...
Time complexity of naive Fibonacci: O(2^n) -exponential. Each call branches into two more, creating a binary recursion tree with massive repeated computation.
Optimised Fibonacci Using Recursion in C -Memoisation
// fibonacci using recursion in c -with memoisation O(n)
#define MAX 100
int memo[MAX];
int fibMemo(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
if (memo[n] != -1) return memo[n]; // Return cached result
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
memset(memo, -1, sizeof(memo)); // Initialise cache
printf("F(10) = %d\n", fibMemo(10)); // Output: 55
printf("F(20) = %d\n", fibMemo(20)); // Output: 6765
return 0;
}
Approach |
Time Complexity |
Space Complexity |
Notes |
Naive Recursion |
O(2^n) |
O(n) stack depth |
Exponential -impractical for n > 40 |
Memoised Recursion |
O(n) |
O(n) -memo array + stack |
Each sub-problem solved exactly once |
Iterative (Bottom-Up) |
O(n) |
O(1) |
Most efficient -no recursion overhead |
C Programming Recursion Examples -Classic Problems
The following c programming recursion examples cover the most commonly tested recursive algorithms in DSA interviews and coursework. Each c recursive function examples includes complete code and output.
1. Power Function (x^n)
// c recursion examples -power function
double power(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / power(base, -exp);
if (exp % 2 == 0) // Fast exponentiation
return power(base * base, exp / 2);
return base * power(base, exp - 1);
}
int main() {
printf("2^10 = %.0f\n", power(2, 10)); // Output: 1024
printf("3^5 = %.0f\n", power(3, 5)); // Output: 243
}
2. Binary Search Using Recursion
// c recursive function examples -binary search
int binarySearch(int arr[], int left, int right, int target) {
if (left > right) return -1; // Base case: not found
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid; // Base case: found
if (arr[mid] < target)
return binarySearch(arr, mid+1, right, target);
return binarySearch(arr, left, mid-1, target);
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 56};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Index of 23: %d\n", binarySearch(arr, 0, n-1, 23)); // 5
printf("Index of 10: %d\n", binarySearch(arr, 0, n-1, 10)); // -1
}
3. Tower of Hanoi
// c programming recursion examples -Tower of Hanoi
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
hanoi(n-1, from, aux, to);
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n-1, aux, to, from);
}
int main() {
hanoi(3, 'A', 'C', 'B');
// Output: 7 moves for 3 disks (2^n - 1)
}
4. Reverse a String Using Recursion
// c recursive function examples -reverse string
void reverseString(char str[], int left, int right) {
if (left >= right) return; // Base case
char temp = str[left];
str[left] = str[right];
str[right] = temp;
reverseString(str, left+1, right-1); // Recursive case
}
int main() {
char s[] = "HeroVired";
reverseString(s, 0, strlen(s)-1);
printf("%s\n", s); // Output: deriVoreH
}
Recursion in C++ vs C
Recursion in c++ follows the same principles as C recursion but with additional language features -function overloading, default parameters, templates, and lambda expressions -that make recursive code more expressive. The recursive function in c++ can also be defined as a class method, allowing recursive object-oriented algorithms.
Recursive Function in C++ -Fibonacci with Templates
// recursive function in c++ -templated factorial
using namespace std;
T factorial(T n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main() {
cout << factorial(5) << endl; // Output: 120
cout << factorial(10LL) << endl; // Output: 3628800 (long long)
}
Recursive Function in C++ -Lambda Recursion (C++14+)
// recursive function in c++ -recursive lambda
using namespace std;
int main() {
// Recursive lambda using std::function
function
if (n <= 1) return n;
return fib(n-1) + fib(n-2);
};
for (int i = 0; i <= 8; i++)
cout << fib(i) << " ";
// Output: 0 1 1 2 3 5 8 13 21
}
Feature |
Recursion in C |
Recursion in C++ |
Function type |
Standard functions only |
Functions, methods, templates, lambdas |
Default parameters |
Not supported |
Supported -simplifies base case defaults |
Template recursion |
Not supported |
Compile-time recursion via templates |
STL integration |
Manual |
Works naturally with STL algorithms |
Tail call optimisation |
GCC -O2 flag |
GCC/Clang -O2 flag; same behaviour |
Object-oriented recursion |
Not applicable |
Class methods can be recursive |
Lambda recursion |
Not applicable |
Supported via std::function (C++14+) |
C# Recursion
C# recursion follows the same fundamental structure as C and C++ recursion but benefits from C#'s managed memory environment, LINQ, and async programming model. C# recursion is commonly used in tree traversal, parsing, divide-and-conquer algorithms, and directory traversal in .NET applications.
C# Recursion -Factorial
|
C# Recursion -Directory Tree Traversal
|
C# recursion in .NET benefits from the garbage collector managing heap allocations, but the call stack is still finite -deeply recursive c# recursion can still cause StackOverflowException. For deeply nested recursion, use an explicit stack (iterative DFS) or increase the thread stack size via Thread.
Recursive Descent Parser Program in C
A recursive descent parser program in c is a top-down parser that directly mirrors a formal grammar using mutually recursive functions -one function per grammar rule. It is one of the most practical and elegant applications of recursion in c in compiler design and language processing. The recursive descent parser program in c is widely used for parsing arithmetic expressions, JSON, XML, and custom domain-specific languages.
Grammar for Arithmetic Expressions
|
Recursive Descent Parser Program in C -Implementation
// recursive descent parser program in c
// Parses and evaluates arithmetic expressions
const char *input;
double parseExpr();
double parseTerm();
double parseFactor();
void skipSpaces() {
while (*input == ' ') input++;
}
double parseFactor() {
skipSpaces();
if (*input == '(') {
input++; // Consume '('
double val = parseExpr(); // Recursive: nested expression
if (*input == ')') input++;
return val;
}
// Parse a number
char *end;
double val = strtod(input, &end);
input = end;
return val;
}
double parseTerm() {
double left = parseFactor();
skipSpaces();
while (*input == '*' || *input == '/') {
char op = *input++;
double right = parseFactor(); // Recursive call
left = (op == '*') ? left * right : left / right;
skipSpaces();
}
return left;
}
double parseExpr() {
double left = parseTerm();
skipSpaces();
while (*input == '+' || *input == '-') {
char op = *input++;
double right = parseTerm(); // Recursive call
left = (op == '+') ? left + right : left - right;
skipSpaces();
}
return left;
}
int main() {
const char *expressions[] = {
"3 + 4 * 2",
"(3 + 4) * 2",
"10 / (2 + 3) - 1"
};
for (int i = 0; i < 3; i++) {
input = expressions[i];
printf("%s = %.2f\n", expressions[i], parseExpr());
}
return 0;
}
// Output:
// 3 + 4 * 2 = 11.00 (operator precedence respected)
// (3 + 4) * 2 = 14.00 (parentheses respected)
// 10 / (2 + 3) - 1 = 1.00
This recursive descent parser program in c demonstrates mutual indirect recursion -parseExpr calls parseTerm, which calls parseFactor, which may call parseExpr again for parenthesised sub-expressions. This mirrors the BNF grammar structure directly and is the defining characteristic of recursive descent parsing.
Properties, Advantages & Disadvantages of C Recursion
Properties
• Self-Similar Sub-problems: Each recursive call works on a smaller version of the same problem
• Base Case Required: Every recursive function must have a termination condition -without it, recursion is infinite
• Stack-Based Execution: Each call frame is stored on the call stack -depth limited by available stack memory
• Convergence: Each call must move closer to the base case -guaranteed termination
Advantage |
Disadvantage |
Clean, concise code for self-similar problems |
Stack overflow risk for deep recursion (large n) |
Natural fit for trees, graphs, parsing |
Higher memory usage than iterative solutions |
Elegant divide-and-conquer implementation |
Function call overhead reduces performance |
Code reusability -same function, different inputs |
Harder to debug -call stack can be complex |
Direct translation of mathematical definitions |
Not all problems benefit from recursive approach |
Real Applications of C Recursion
Application |
Recursive Approach |
Example |
Tree & Graph Traversal |
DFS uses recursion to explore each branch fully before backtracking |
File system traversal, XML/JSON parsing, org chart navigation |
Divide-and-Conquer Algorithms |
Problem split into halves -each half solved recursively |
Merge sort, quick sort, binary search |
Fibonacci & Mathematical Series |
Natural recursive definition maps directly to code |
Financial modelling, biological growth patterns |
Recursive Descent Parsing |
Each grammar rule = one recursive function |
Compilers, interpreters, expression evaluators |
Backtracking Algorithms |
Explore paths recursively; backtrack on dead ends |
Sudoku solver, N-Queens, maze solving |
Fractal Generation |
Shapes defined by recursive self-similarity |
Mandelbrot set, Sierpinski triangle, fractal terrain |
Dynamic Programming |
Top-down DP uses memoised recursion |
Knapsack, edit distance, longest common subsequence |
Conclusion
Recursion in c is one of the most powerful techniques in programming -enabling elegant solutions to problems that have natural self-similar structure. From the basic c recursive function pattern (base case + recursive case) to complex applications like fibonacci using recursion in c, binary search, Tower of Hanoi, and the recursive descent parser program in c -recursion underpins a vast range of algorithms.
Understanding all types of recursion in c -direct, indirect, tail, non-tail -and knowing when to apply recursion in c++ or c# recursion gives you a complete toolkit for recursive algorithm design across the C language family.
To build complete expertise in C, algorithms, and data structures, explore the Certificate Program in Application Development powered by Hero Vired.
People Also Ask
What is recursion in C?
Recursion in c: a programming technique where a function calls itself with a smaller input until a base case terminates the chain. Every c recursive function requires a base case (stops recursion) and a recursive case (calls itself with reduced input). Classic examples include factorial, Fibonacci, and binary search.
How does Fibonacci using recursion in C work?
Fibonacci using recursion in c: define F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). The C function calls itself twice per invocation -creating tree recursion. Naive implementation is O(2^n); add memoisation (cache results in an array) to reduce to O(n). Full code with both versions is provided in this article.
What is the difference between recursion in C and recursion in C++?
Recursion in c++ supports all C recursion patterns plus templates (compile-time recursion), class method recursion, recursive lambdas, and default parameters. Both compile to identical machine code for standard recursive functions -the difference is in language features available for structuring the recursive function in c++, not in the recursion mechanism itself.
What is a recursive descent parser program in C?
A recursive descent parser program in c: a top-down parser that uses one function per grammar rule, with functions calling each other recursively to process nested syntax structures. It implements indirect recursion -parseExpr calls parseTerm, which calls parseFactor, which may call parseExpr again. This is the standard approach for building expression evaluators and custom language parsers.
What are the types of recursion in C?
The main types of recursion in c: Direct (function calls itself), Indirect (functions call each other cyclically), Tail (recursive call is the last operation -compiler-optimisable), Non-Tail (operations after recursive return -stack maintained), Linear (one recursive call per invocation), and Tree/Binary (two or more recursive calls -used in Fibonacci, merge sort).
What is Recursion in C?
How do we use recursion in C?
Why Do We Need Recursion in C?
What are the major types of Recursion in C?
- Direct Recursion: In direct recursion, a function calls itself directly. It is the most common form of recursion, where a function invokes itself during its execution.
- Indirect Recursion: In indirect recursion, multiple functions call each other in a circular manner. A function calls another function, which in turn may call the first one or another function, creating a chain of recursive calls.
Updated on April 16, 2026