Given a non-negative integer n, print all numbers from n down to 1 in strictly decreasing order using recursion.
Example 1
Input: n = 4
Output: 4 3 2 1
Explanation: The sequence begins at the maximum target integer 4 and decrements sequentially until it hits 1.
Example 2
Input: n = 2
Output: 2 1
Explanation: The sequence counts downward from 2 and stops cleanly after outputting 1.
Approach
To print the numbers in decreasing order, the current value should be printed before moving to the next smaller value.
After printing n, the same task remains for the range from n - 1 down to 1. This smaller task can be handled by calling the function again with n - 1.
The value keeps decreasing with every call, and the recursion stops once it reaches 0.
Algorithm
Define a recursive function that receives
n, wherenrepresents the current number in the countdown.When
n <= 0, return from the function because every positive number has already been printed. This also prevents further calls for zero or negative input.Print the current value of
nbefore making the recursive call, ensuring that the larger number appears first.Call the function with
n - 1so the countdown continues with the next smaller number.
Dry Run
Print N to 1 Dry Run .png
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: void printNToOne(int n) { // Base case: stop after printing all positive numbers. if (n <= 0) { return; } cout << n << " "; // Continue the countdown with the next smaller number. printNToOne(n - 1); }};int main() { int n = 4; Solution solution; solution.printNToOne(n); cout << endl; return 0;}Complexity Analysis
Time Complexity: O(N), because one recursive call is made for every number from N down to 1.
Space Complexity: O(N), because each recursive call adds a new frame to the call stack before the base case is reached.
FAQs
Q1. Why is the number printed before the recursive call?
Printing before the recursive call displays the current larger value first. The function then moves to the next smaller number, producing decreasing order.
Q2. What happens if the print statement is placed after the recursive call?
The function first reaches the base case and then prints while returning. This changes the output order to 1, 2, 3, ..., N.
Q3. What happens when n = 0?
The base case is reached immediately, so nothing is printed.
Q4. Why is n <= 0 used as the base case?
It stops the recursion after all positive numbers have been printed and also handles negative input safely.
Q5. Is this a tail-recursive function?
Yes. The recursive call is the last operation performed by the function. However, not every programming language or compiler guarantees tail-call optimization, so the usual recursive space complexity is still considered O(N).
Q6. Can this problem be solved using a loop?
Yes. A loop can print the same sequence using O(1) auxiliary space. Recursion is used here to practise base cases, recursive calls, and execution order.
Be the first to add a comment.