Welcome to the Recursion-and-Types repository! This is a dedicated technical space where I have coded, analyzed, and implemented recursion using C++.
Recursion is one of the most vital paradigms in computer science. Rather than treating it as a simple alternative to loops, this repository breaks down how different algorithmic structures of recursion impact memory allocation, execution order, and the underlying system call stack.
This repository documents hands-on programmatic proofs for the following tracking methodologies:
- Tail Recursion (
tail_recursion.cpp): Designing recursive functions where the recursive call is the absolute final statement. Optimized to understand how compilers handle Tail Call Optimization (TCO) to prevent stack overflows. - Head Recursion (
head_recursion.cpp): Exploring instances where the recursive call happens at the beginning of the function body. This forces processing to occur on the returning phase (during stack unwinding). - Linear Recursion (
linear.cpp): Implementation of functions that make a single, clean call to themselves during execution, generating a straight execution chain. - Tree Recursion (
tree_recursion.cpp): Moving past linear structures to handle functions that make multiple recursive calls inside a single frame, leading to an exponential growth of execution paths (crucial for parsing data structures like graphs and trees).
- Static & Global Variables in Recursion (
static_varoables_recursion.cpp): Analyzing how static storage behaves differently from standard local stack variables when function frames are pushed and popped recursively.
- Recursion vs. Iteration Loop Comparisons (
head_recursion_vs_loops.cpp,tail_recursion_vs_loop.cpp): Direct head-to-head performance comparisons measuring time complexity versus the spatial overhead of the call stack.
Each logical pattern is paired with its compiled executable binary for instant cross-checking:
*_recursion.cpp: The underlying source files detailing the exact call structures and variables.*_recursion_vs_loop.cpp: Benchmark files analyzing iterative loops versus recursive calls.*.exe: Compiled binaries for instant output validation on target systems.
Every recursive function works in two distinct operational phases:
- The Calling Phase (Going Down): Functions keep calling themselves, stacking execution records on top of each other.
- The Returning Phase (Coming Up / Unwinding): Once the base condition is met, the stack begins populating values back down to the original driver call.
Understanding these states is what differentiates writing clean recursive algorithms from triggering a dangerous segmentation fault.
To test these execution traces locally, make sure you have a standard C++ compiler (like g++) ready.
- Clone the repository:
git clone [https://github.com/toqeersheikh/Recursion-and-Types.git](https://github.com/toqeersheikh/Recursion-and-Types.git)