Recursion occurs when a function invokes itself directly or indirectly to solve smaller sub-problems. In Unit 5 of MAKAUT C Programming (PPS-II), recursive algorithms, stack allocation frames, tail-call optimization, and call-tree traces are primary examination topics.

This guide provides deep structural clarity on stack call frames, recurrence relation derivations, and recursive implementations of Factorial, Fibonacci, GCD, and Indirect Recursion.

---

1. Mechanics of Recursion: Base Case & Stack Frames

Every valid recursive function must have two components:

  1. Base Case (Termination Condition): Halts recursion. Missing base cases cause Stack Overflow runtime crashes (Segmentation Fault).
  2. Recursive Step: Decreases problem size toward base case.

Stack Activation Trace for factorial(3):

c
1[Stack Push Phase]                      [Stack Pop / Return Phase]
2factorial(3) = 3 * factorial(2)   -->   returns 3 * 2 = 6
3factorial(2) = 2 * factorial(1)   -->   returns 2 * 1 = 2
4factorial(1) = 1 (Base Case)      -->   returns 1

---

2. Types of Recursion

  • Direct Recursion: Function A calls A.
  • Indirect Recursion: Function A calls B, and function B calls A.
  • Tail Recursion: The recursive call is the final statement executed. Compilers optimize tail recursion into simple loops to save memory.
  • Tree Recursion: Function makes multiple recursive calls per invocation (e.g., Fibonacci).

---

3. Recursion vs Iteration Comparison Table

AttributeRecursionIteration
Code StructureCompact & elegantMore verbose
Memory UsageHigh (O(N) call stack frames)Low (O(1) auxiliary space)
Execution OverheadFunction push/pop overheadSimple loop condition check

---

4. Solved Classic Recursive Programs

1. Recursive Factorial

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3long long factorial(int n) {
4    if (n == 0 || n == 1) return 1; // Base case
5    return n * factorial(n - 1);    // Recursive step
6}
7 
8int main() {
9    int num = 5;
10    printf("Factorial of %d = %lld\n", num, factorial(num));
11    return 0;
12}

---

2. Recursive Fibonacci & Call Tree Derivation

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3int fibonacci(int n) {
4    if (n == 0) return 0;
5    if (n == 1) return 1;
6    return fibonacci(n - 1) + fibonacci(n - 2);
7}
8 
9int main() {
10    int n = 6;
11    printf("Fibonacci term %d = %d\n", n, fibonacci(n));
12    return 0;
13}

Recursive Call Tree for fibonacci(4):

c
1fib(4)
2               /      \
3          fib(3)      fib(2)
4          /    \       /   \
5      fib(2)  fib(1) fib(1) fib(0)
6      /   \
7  fib(1) fib(0)

*Complexity*: Time O(2^N), Space O(N).

---

3. Indirect Recursion Example

c
1"text-[#cf222e] dark:text-[#c586c0] font-semibold">#include "text-[#0a3069] dark:text-[#ce9178]"><stdio.h>
2 
3void functionB(int n);
4 
5void functionA(int n) {
6    if (n > 0) {
7        printf("%d ", n);
8        functionB(n - 1); // A calls B
9    }
10}
11 
12void functionB(int n) {
13    if (n > 0) {
14        printf("%d ", n);
15        functionA(n / 2); // B calls A
16    }
17}
18 
19int main() {
20    printf("Indirect Recursion Sequence: ");
21    functionA(20);
22    printf("\n");
23    return 0;
24}