Print N times with Recursion | GFG

The “Print N times with Recursion” problem on GeeksforGeeks asks you to output the string "GFG" exactly N times, using only recursive function calls (no loops).

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

Typical interview follow-ups include:

• Showing a straightforward recursive call that prints on the way down the call stack (no backtracking).
• Demonstrating a backtracking version that defers printing until the stack unwinds.

Both variants illustrate how the position of work in a recursive routine (before vs. after the recursive call) changes the order of operations, an essential concept for DFS, tree traversals, and more.

Without Backtracking Solution

Intuition & Approach

1. Base Case: Stop recursion when the current index i exceeds n.
2. Work Before Recursive Call: Print "GFG" immediately, then recurse with i + 1.
3. Because the print happens on the way down, the output appears left-to-right (GFG GFG …) without delay.

Code Implementation

class Solution:
    def func(self, i, n):
        # Base case: once i exceeds n, stop recursion
        if i > n:
            return
        print("GFG", end=" ")   # work done before deeper call
        self.func(i + 1, n)     # recursive call with next index

    def printGfg(self, n):
        # Kick-off with i = 1
        self.func(1, n)

Code Explanation

• print("GFG", end=" ") executes first; the recursive call happens after.
• Each call’s local variables (i, n) live on the call stack until that call returns, but printing is unaffected by the eventual unwinding.

Dry Run (n = 3)

Time & Space Complexity

• Time: O(N) — one print and one recursive call per value of i.
• Space: O(N) — call stack depth equals N (tail-recursion isn’t optimized in Python).

Conclusion

Printing on the forward path is simple and intuitive. The order is natural, but the call stack still grows linearly with N.

With Backtracking Solution

Intuition & Approach

1. Base Case: End recursion when i drops below 1.
2. Work After Recursive Call: First recurse with i − 1; after the deeper call returns, print "GFG".
3. This deferral means printing happens while backtracking, producing the same repeated string but emphasizing the concept of post-order work.

Code Implementation

class Solution:
    def func(self, i):
        # Base case: once i is less than 1, stop recursion
        if i < 1:
            return
        self.func(i - 1)        # recurse first (go deeper)
        print("GFG", end=" ")   # ✍️ work done after returning

    def printGfg(self, n):
        # Kick-off with the original n
        self.func(n)

Code Explanation

• The recursive descent builds up the stack until i hits zero.
• As each frame returns, its print executes—so the output is still "GFG" repeated N times, but the work occurs during backtracking.

Dry Run (n = 3)

Time & Space Complexity

• Time: O(N) — identical to forward recursion.
• Space: O(N) — same call-stack depth.

Conclusion

Moving the print statement below the recursive call highlights backtracking: the same result, but with the action delayed until the stack unwinds. This pattern is a stepping-stone to in-order/post-order traversals in trees and graphs.

Final Thoughts

• Both techniques satisfy the requirement to print "GFG" exactly N times using recursion alone.
• The key lesson isn’t speed—both run in linear time—but understanding where the “work” sits relative to the recursive call:
  • Forward recursion (no backtracking) for pre-order-style tasks.
  • Backtracking for post-order patterns.

Master these tiny examples and you’ll recognize the same shape in bigger recursive problems, from generating subsets to traversing binary trees. Happy recursing!

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