Print N to 1 without loop | Normal Recursion and Backtracking

The “Print N to 1 without loop” problem on GeeksforGeeks challenges you to output the integers from N down to 1 strictly with recursion, no for or while loops allowed.

Here’s the [Problem Link] to begin with.

Why is this useful?

• Strengthens your grasp of recursive control flow.
• Demonstrates how the position of work (before or after the recursive call) controls output order, an idea that extends to DFS, tree traversals, and backtracking algorithms.

Example

Below are two clean recursive patterns: a straightforward top-down call and a backtracking variation.

Simple Recursion Solution

Intuition & Approach

1. Base Case: Stop once num drops below 1.
2. Work Before Recursive Call: Print num immediately, then recurse with num - 1.
3. Because printing happens on the way down the call stack, numbers naturally appear in descending order.

Code Implementation

class Solution:
    def func(self, num):
        # Base Case: when num goes below 1, stop recursion
        if num < 1:
            return
        print(num, end=" ")    # ✍️ print current number
        self.func(num - 1)     # 🔁 recurse on the next smaller number

    def printNos(self, n):
        # Driver method that kicks off recursion
        self.func(n)

Code Explanation

• print(num, end=" ") executes first in every frame, emitting num as the call stack deepens.
• The recursion depth equals N, so the call stack size grows linearly with input.

Dry Run (N = 3)

Time & Space Complexity

• Time: O(N) – one function call and one print per integer.
• Space: O(N) – the maximum call-stack depth.

Conclusion

This direct version is easy to remember: “do the work first, then recurse.” It’s perfect for any pre-order output pattern.

Backtracking Solution

Intuition & Approach

1. Base Case: End recursion when the index i exceeds num.
2. Work After Recursive Call: First recurse with i + 1, then print i while backtracking.
3. Because printing happens on the way up, we must start i at 1 and let the recursion unwind to produce num, …, 1.

Code Implementation

class Solution:
    def func(self, i, num):
        # Base Case: once the index surpasses num, end recursion
        if i > num:
            return
        self.func(i + 1, num)  # 🔁 dive deeper first
        print(i, end=" ")      # ✍️ print while backtracking

    def printNos(self, n):
        # Start from 1 so backtracking prints n down to 1
        self.func(1, n)

Code Explanation

• The recursive calls build the stack until i exceeds num.
• As frames return, each prints its own i, resulting in descending output.

Dry Run (N = 3)

Descent Phase

func(1,3) → func(2,3) → func(3,3) → func(4,3)  (base case)

Backtracking Phase

Time & Space Complexity

• Time: O(N) – identical to the simple version.
• Space: O(N) – call-stack depth remains N.

Conclusion

Placing the print after the recursive call turns the function into a post-order printer. This pattern is the backbone of algorithms that need to process children before parents (e.g., post-order tree traversals).

Final Thoughts

• Both approaches satisfy the “no loop” requirement in O(N) time.
• The difference lies in when the work is done:
  • Simple Recursion: print on the way down.
  • Backtracking: print on the way up.
• Understanding this placement is crucial for mastering recursion-driven algorithms across data structures and problem domains.

Happy coding, and may your recursive calls always find their base case!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.