C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Master recursion in C: base cases, recursive cases, stack frames, factorial, Fibonacci, tower of Hanoi, and more. Understand when recursion beats iteration and common pitfalls.
Recursion is when a function calls itself to solve a smaller version of the same problem. It's one of those concepts that feels magical when it clicks — and deeply confusing before it does. Recursion is the natural approach for problems that have a self-similar structure: trees, mathematical sequences, divide-and-conquer algorithms, and anything that can be defined in terms of smaller instances of itself.
How Recursion Works
Every recursive function needs two things:
- Base case — A condition that stops the recursion (prevents infinite calls)
- Recursive case — The function calls itself with a "smaller" problem
c example
#include <stdio.h>
void countdown(int n) {
// Base case: stop when n reaches 0
if (n == 0) {
printf("Blast off!\n");
return;
}
// Recursive case: print n, then countdown from n-1
printf("%d... ", n);
countdown(n - 1); // Function calls itself
}
int main() {
countdown(5);
return 0;
}Output
5... 4... 3... 2... 1... Blast off!
Classic Example: Factorial
The mathematical definition of factorial is inherently recursive:
0! = 1(base case)n! = n × (n-1)!(recursive case)
Example
#include <stdio.h>
int factorial(int n) {
// Base case
if (n == 0 || n == 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
int main() {
for (int i = 0; i <= 10; i++) {
printf("%2d! = %d\n", i, factorial(i));
}
return 0;
}
Output
0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120 6! = 720 7! = 5040 8! = 40320 9! = 362880 10! = 3628800
How the Call Stack Unfolds
For factorial(4):
Example
factorial(4) → 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ returns 1 (base case)
→ returns 2 * 1 = 2
→ returns 3 * 2 = 6
→ returns 4 * 6 = 24
Fibonacci Sequence
Example
#include <stdio.h>
int fibonacci(int n) {
// Base cases
if (n == 0) return 0;
if (n == 1) return 1;
// Recursive case: fib(n) = fib(n-1) + fib(n-2)
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
printf("Fibonacci sequence:\n");
for (int i = 0; i <= 12; i++) {
printf("F(%d) = %d\n", i, fibonacci(i));
}
return 0;
}
Output
Fibonacci sequence: F(0) = 0 F(1) = 1 F(2) = 1 F(3) = 2 F(4) = 3 F(5) = 5 F(6) = 8 F(7) = 13 F(8) = 21 F(9) = 34 F(10) = 55 F(11) = 89 F(12) = 144
Warning: This naive recursive Fibonacci is extremely inefficient — O(2^n) time complexity. For large n, use iteration or memoization.
Power Function
c example
#include <stdio.h>
// Simple recursion: O(n)
double power(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / power(base, -exp);
return base * power(base, exp - 1);
}
// Efficient recursion: O(log n) using divide-and-conquer
double fastPower(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / fastPower(base, -exp);
double half = fastPower(base, exp / 2);
if (exp % 2 == 0)
return half * half;
else
return base * half * half;
}
int main() {
printf("2^10 = %.0f\n", power(2, 10));
printf("3^5 = %.0f\n", power(3, 5));
printf("2^-3 = %f\n", power(2, -3));
printf("Fast: 2^20 = %.0f\n", fastPower(2, 20));
return 0;
}Output
2^10 = 1024 3^5 = 243 2^-3 = 0.125000 Fast: 2^20 = 1048576
Sum of Digits
c example
#include <stdio.h>
int sumOfDigits(int n) {
if (n < 0) n = -n; // Handle negative
if (n < 10) return n; // Base case: single digit
return (n % 10) + sumOfDigits(n / 10);
}
int countDigits(int n) {
if (n < 0) n = -n;
if (n < 10) return 1;
return 1 + countDigits(n / 10);
}
int main() {
printf("Sum of digits of 12345: %d\n", sumOfDigits(12345));
printf("Sum of digits of 999: %d\n", sumOfDigits(999));
printf("Digits in 12345: %d\n", countDigits(12345));
printf("Digits in 7: %d\n", countDigits(7));
return 0;
}Output
Sum of digits of 12345: 15 Sum of digits of 999: 27 Digits in 12345: 5 Digits in 7: 1
Tower of Hanoi
The classic recursion problem — move n disks from source to destination using an auxiliary peg:
Example
#include <stdio.h>
int moveCount = 0;
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
moveCount++;
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to); // Move n-1 disks to auxiliary
moveCount++;
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, aux, to, from); // Move n-1 disks from auxiliary to destination
}
int main() {
int disks = 3;
printf("Tower of Hanoi with %d disks:\n\n", disks);
hanoi(disks, 'A', 'C', 'B');
printf("\nTotal moves: %d\n", moveCount);
return 0;
}
Output
Tower of Hanoi with 3 disks: Move disk 1 from A to C Move disk 2 from A to B Move disk 1 from C to B Move disk 3 from A to C Move disk 1 from B to A Move disk 2 from B to C Move disk 1 from A to C Total moves: 7
Binary Search (Recursive)
Example
#include <stdio.h>
int binarySearch(int arr[], int low, int high, int target) {
if (low > high) return -1; // Base case: not found
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] > target)
return binarySearch(arr, low, mid - 1, target);
else
return binarySearch(arr, mid + 1, high, target);
}
int main() {
int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
int size = 11;
int target = 23;
int index = binarySearch(arr, 0, size - 1, target);
if (index != -1)
printf("Found %d at index %d\n", target, index);
else
printf("%d not found\n", target);
target = 50;
index = binarySearch(arr, 0, size - 1, target);
if (index != -1)
printf("Found %d at index %d\n", target, index);
else
printf("%d not found\n", target);
return 0;
}
Output
Found 23 at index 5 50 not found
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Memory | Uses stack frames (O(n) space) | Constant space (O(1)) |
| Speed | Slower (function call overhead) | Faster |
| Readability | Often cleaner for recursive problems | Better for simple loops |
| Risk | Stack overflow for deep recursion | No stack risk |
| Best for | Trees, divide-and-conquer, self-similar | Linear sequences, simple counts |
Same Problem: Iterative vs Recursive
Example
#include <stdio.h>
// Iterative factorial
int factorialIter(int n) {
int result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
// Recursive factorial
int factorialRec(int n) {
if (n <= 1) return 1;
return n * factorialRec(n - 1);
}
int main() {
printf("Iterative: 10! = %d\n", factorialIter(10));
printf("Recursive: 10! = %d\n", factorialRec(10));
return 0;
}
Output
Iterative: 10! = 3628800 Recursive: 10! = 3628800
Tail Recursion
A recursive call is "tail recursive" when it's the very last operation in the function. Some compilers can optimize tail recursion into iteration (eliminating stack growth):
c example
#include <stdio.h>
// Not tail recursive (multiplication AFTER the recursive call)
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // Must multiply after call returns
}
// Tail recursive (result accumulates in parameter)
int factorialTail(int n, int accumulator) {
if (n <= 1) return accumulator;
return factorialTail(n - 1, n * accumulator); // Nothing after this call
}
int main() {
printf("Regular: 10! = %d\n", factorial(10));
printf("Tail: 10! = %d\n", factorialTail(10, 1));
return 0;
}Output
Regular: 10! = 3628800 Tail: 10! = 3628800
Common Pitfalls
Missing Base Case (Infinite Recursion)
c example
// WRONG: No base case — infinite recursion!
void infinite(int n) {
printf("%d ", n);
infinite(n + 1); // Never stops! → Stack Overflow
}
// CORRECT: Has a stopping condition
void finite(int n) {
if (n > 5) return; // Base case
printf("%d ", n);
finite(n + 1);
}Stack Overflow
Each recursive call adds a frame to the call stack. Too many calls exhaust stack memory:
c example
#include <stdio.h>
// This will crash for large n (stack overflow)
int badRecursion(int n) {
if (n == 0) return 0;
return n + badRecursion(n - 1);
}
int main() {
// printf("%d\n", badRecursion(1000000)); // Stack overflow!
printf("%d\n", badRecursion(1000)); // OK for small n
return 0;
}Interview Questions
Q1: What are the two essential components of a recursive function?
Every recursive function needs: (1) A base case — a condition that stops the recursion and returns a value directly without further recursive calls; (2) A recursive case — the function calls itself with a modified (usually smaller) problem that progresses toward the base case.
Q2: What is stack overflow and how does recursion cause it?
Each recursive call creates a new stack frame (storing parameters, local variables, and return address). If recursion goes too deep (no base case reached, or problem is too large), the call stack exceeds its memory limit and the program crashes with a stack overflow. Default stack size is typically 1-8 MB.
Q3: What is the time complexity of naive recursive Fibonacci?
O(2^n) — exponential. Each call branches into two more calls, creating a binary tree of calls. fib(30) makes over a million calls. The fix is memoization (storing previously computed results) or converting to iteration, both achieving O(n).
Q4: What is tail recursion and why is it important?
Tail recursion is when the recursive call is the last operation in the function — nothing happens after it returns. Compilers can optimize tail recursion into a loop (tail call optimization), eliminating stack growth and making it as efficient as iteration. Not all compilers do this in C.
Q5: Can every recursive function be converted to iterative?
Yes, theoretically every recursive algorithm can be implemented iteratively, sometimes using an explicit stack data structure. However, some problems (like tree traversals, Tower of Hanoi, quicksort) are much more naturally and cleanly expressed with recursion.
Summary
- Recursion is a function calling itself with a smaller sub-problem
- Every recursive function needs a base case (stopping condition) and a recursive case
- Each call creates a stack frame — deep recursion can cause stack overflow
- Classic examples: factorial, Fibonacci, Tower of Hanoi, binary search
- Recursion is ideal for tree structures, divide-and-conquer, and self-similar problems
- Tail recursion can be optimized by compilers to eliminate stack growth
- For simple linear problems, iteration is usually more efficient
- Always ensure the recursive case makes progress toward the base case
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Recursion in C Programming.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, functions, recursion, recursion in c programming
Related C Programming Topics
Continue learning this concept
FunctionsFunction Arguments in C - Pass by Value vs Pass by ReferenceUnderstand how arguments are passed to functions in C: pass by value vs pass by reference (using pointers). Learn when to use each approach with practical examples and common patterns.FunctionsFunction Call in C ProgrammingLearn how to call functions in C: passing arguments, receiving return values, actual vs formal parameters, nested function calls, and the function call mechanism with stack frames.FunctionsFunction Declaration (Prototype) in CLearn function declarations and prototypes in C programming. Understand why prototypes are needed, syntax rules, implicit declarations, and best practices for declaring functions before use.FunctionsFunction Definition in C ProgrammingLearn how to define functions in C: syntax, return types, parameters, function body, local variables, and the complete anatomy of a function definition with practical examples.FunctionsIntroduction to Functions in C ProgrammingLearn what functions are in C, why theyFunctionsReturn Statement in C ProgrammingLearn the return statement in C: returning values from functions, void functions, multiple return points, returning pointers, and common mistakes. Complete guide with practical examples.