A structured lesson workspace with readable content, hands-on examples, and a clean path to completion.
In tail recursion, the recursive call is the last operation in the function. Nothing happens after it returns. In head recursion, the recursive call happens first, and work is done after it returns. The distinction matters because a tail-recursive function can theoretically be optimized into a loop by the compiler, reusing the same stack frame for every call. C compilers sometimes do this. They are not required to. The C standard says nothing about tail-call optimization.
#include <stdio.h>void print_forward(int n) {if (n <= 0) return;print_forward(n - 1);printf("%d ", n);}int main(void) {print_forward(5);printf("\n");return 0;}
The printf happens after the recursive call returns. The function must keep its stack frame alive while the deeper calls execute, because it still needs to run printf on the way back up. Five frames exist simultaneously. The printing happens during the unwind phase.
#include <stdio.h>void print_reverse(int n) {if (n <= 0) return;printf("%d ", n);print_reverse(n - 1);}int main(void) {print_reverse(5);printf("\n");return 0;}
The printf happens before the recursive call. After print_reverse calls itself, there is nothing left to do. The current frame is no longer needed. With -O2, GCC may convert this into a jump back to the function's entry point, reusing the same frame. The stack depth stays at 1 regardless of n. Without optimization, you still get n frames.
#include <stdio.h>long factorial_tail(int n, long acc) {if (n <= 1) return acc;return factorial_tail(n - 1, n * acc);}long factorial_head(int n) {if (n <= 1) return 1;return n * factorial_head(n - 1);}int main(void) {printf("Tail: %ld\n", factorial_tail(10, 1));printf("Head: %ld\n", factorial_head(10));return 0;}
The head-recursive version multiplies on the way back up. It must keep every frame alive to remember the pending multiplications. The tail-recursive version carries the accumulated result as a parameter. Nothing is pending when the recursive call happens. The compiler can replace the call with a jump. In practice, GCC at -O2 often does this for simple cases. At -O0, it never does.
Do not rely on tail-call optimization in C for correctness. The standard does not mandate it. If your recursion depth could exceed the stack, convert to iteration explicitly. Tail-call optimization is a bonus, not a guarantee.
Recursion module complete. You now understand call stacks, base cases, branching factors, mutual recursion, and the optimization implications of call position. These concepts transfer directly to tree algorithms, graph traversal, and compiler design. Next module: pointers and memory management, the heart of C and the source of its power and its pain.
Finish the lesson once you have worked through the material. This awards ★ 30 XP.