Basic Recursion: Print N to 1
Counting down recursively from $N$ to $1$ is another fundamental exercise. In this configuration, we initialize the loop parameter $i$ to $N$, and decrement it towards the base case of $0$.
The recursive function signature is:
printNTo1(i)
The parameters and cases work as follows:
- Base Case:
i < 1. Once our counter goes below 1, we exit. - Recursive Step: Decrement the counter and invoke `printNTo1(i - 1)`.
Complexity Analysis
Time Complexity: O(N)
The function makes exactly $N+1$ recursive calls to print numbers from N down to 1.
Space Complexity: O(N)
Just like printing 1 to N, there are at most $N+1$ active stack frames on the Call Stack. Thus, auxiliary space is linear, $O(N)$.