Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Number Series Without Loops

EASYProblemSolveExternal Links

Description

You are given two positive integers N and K. Your task is to generate a number series as follows:

  1. Start with N
  2. Repeatedly subtract K from the current number, printing each value along the way, until the number becomes zero or negative
  3. Once the number reaches zero or goes negative, start adding K back, printing each value, until you reach the original number N again

The result is a "V-shaped" number sequence that counts down by K and then counts back up by K.

Important constraint: You must accomplish this without using any loops — recursion only.

This problem tests your ability to use recursion with a direction-switching mechanism (a flag or conditional logic) to simulate two distinct phases of computation within a single recursive function.

Examples

Example 1

Input: N = 15, K = 5

Output: 15 10 5 0 5 10 15

Explanation: Starting from 15, we subtract 5 repeatedly: 15 → 10 → 5 → 0. Once we hit 0 (which is ≤ 0), we switch direction and add 5 repeatedly: 0 → 5 → 10 → 15. We stop when we reach the original value 15. The full series is: 15, 10, 5, 0, 5, 10, 15.

Example 2

Input: N = 20, K = 6

Output: 20 14 8 2 -4 2 8 14 20

Explanation: Starting from 20, we subtract 6 repeatedly: 20 → 14 → 8 → 2 → -4. The value -4 is negative (≤ 0), so we switch direction and add 6 repeatedly: -4 → 2 → 8 → 14 → 20. We stop at 20 (the original N). Notice that when N is not perfectly divisible by K, the series goes into negative territory before bouncing back.

Example 3

Input: N = 5, K = 3

Output: 5 2 -1 2 5

Explanation: Starting from 5, subtract 3: 5 → 2 → -1. The value -1 is negative, so switch and add 3: -1 → 2 → 5. Stop at the original value 5.

Constraints

  • 1 ≤ N ≤ 10^6
  • 1 ≤ K ≤ N
  • No loops allowed — recursion only

Editorial

Brute Force

Intuition

The most straightforward recursive approach is to use a boolean flag to track the current direction of the series. When the flag is true, we are in subtraction mode (counting down). When the flag is false, we are in addition mode (counting back up).

Think of it like a ball bouncing: you throw it down a staircase (subtract K each step), it hits the ground (reaches ≤ 0), and then it bounces back up the same staircase (add K each step) until it reaches the height you threw it from.

The function takes four parameters:

  • The current value of the number
  • The original value of N (so we know when to stop on the way back up)
  • The step size K
  • A boolean flag indicating whether we're subtracting or adding

At each call, we print the current number, check if we need to flip the flag (when the number goes to zero or below), and then recurse with the updated value.

Step-by-Step Explanation

Let's trace through with N = 20, K = 6:

Step 1: Call with current=20, original=20, K=6, subtracting=true. Print 20. Since 20 > 0, stay in subtract mode. Recurse with current=14.

Step 2: Call with current=14, subtracting=true. Print 14. Since 14 > 0, keep subtracting. Recurse with current=8.

Step 3: Call with current=8, subtracting=true. Print 8. Since 8 > 0, keep subtracting. Recurse with current=2.

Step 4: Call with current=2, subtracting=true. Print 2. Since 2 > 0, keep subtracting. Recurse with current=-4.

Step 5: Call with current=-4, subtracting=true. Print -4. Since -4 ≤ 0, FLIP the flag to subtracting=false. Now we're adding. Recurse with current=-4+6=2.

Step 6: Call with current=2, subtracting=false. Print 2. Since current (2) ≠ original (20), keep adding. Recurse with current=8.

Step 7: Call with current=8, subtracting=false. Print 8. Since 8 ≠ 20, keep adding. Recurse with current=14.

Step 8: Call with current=14, subtracting=false. Print 14. Since 14 ≠ 20, keep adding. Recurse with current=20.

Step 9: Call with current=20, subtracting=false. Print 20. Since current (20) == original (20) and we're in addition mode, this is our termination condition. Return.

Result: Output is "20 14 8 2 -4 2 8 14 20".

Flag-Based Recursion: N=20, K=6 — Watch the series build step by step as the function subtracts K until hitting zero or below, then flips direction and adds K back to the original value.

Algorithm

  1. Define a recursive function printSeries(current, original, K, subtracting) with four parameters
  2. Print the current value
  3. If current ≤ 0, flip the subtracting flag to false (switch to addition mode)
  4. Termination check: If current == original AND subtracting == false, return (we've completed the full V-shape)
  5. If subtracting is true, recurse with current - K
  6. If subtracting is false, recurse with current + K
  7. Initial call: printSeries(N, N, K, true)

Code

#include <iostream>
using namespace std;

class Solution {
public:
    void printSeries(int current, int original, int K, bool subtracting) {
        // Print the current number
        cout << current << " ";
        
        // Flip direction when we go to zero or below
        if (current <= 0)
            subtracting = false;
        
        // Termination: reached original on the way back up
        if (current == original && !subtracting)
            return;
        
        // Recurse in the appropriate direction
        if (subtracting)
            printSeries(current - K, original, K, subtracting);
        else
            printSeries(current + K, original, K, subtracting);
    }
    
    void solve(int N, int K) {
        printSeries(N, N, K, true);
    }
};

int main() {
    Solution sol;
    sol.solve(20, 6);
    return 0;
}
import sys
sys.setrecursionlimit(10**6 + 10)

class Solution:
    def printSeries(self, current: int, original: int, K: int, subtracting: bool) -> None:
        # Print the current number
        print(current, end=" ")
        
        # Flip direction when we go to zero or below
        if current <= 0:
            subtracting = False
        
        # Termination: reached original on the way back up
        if current == original and not subtracting:
            return
        
        # Recurse in the appropriate direction
        if subtracting:
            self.printSeries(current - K, original, K, subtracting)
        else:
            self.printSeries(current + K, original, K, subtracting)
    
    def solve(self, N: int, K: int) -> None:
        self.printSeries(N, N, K, True)

# Driver code
if __name__ == "__main__":
    sol = Solution()
    sol.solve(20, 6)
class Solution {
    private void printSeries(int current, int original, int K, boolean subtracting) {
        // Print the current number
        System.out.print(current + " ");
        
        // Flip direction when we go to zero or below
        if (current <= 0)
            subtracting = false;
        
        // Termination: reached original on the way back up
        if (current == original && !subtracting)
            return;
        
        // Recurse in the appropriate direction
        if (subtracting)
            printSeries(current - K, original, K, subtracting);
        else
            printSeries(current + K, original, K, subtracting);
    }
    
    public void solve(int N, int K) {
        printSeries(N, N, K, true);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.solve(20, 6);
    }
}

Complexity Analysis

Time Complexity: O(N/K)

The series has approximately 2 × ⌈N/K⌉ + 1 elements: about ⌈N/K⌉ subtractions to go from N down past zero, then about ⌈N/K⌉ additions to climb back to N. Each recursive call does O(1) work (one print, one comparison). So total time is O(N/K).

Space Complexity: O(N/K)

The recursion depth matches the number of elements in the series, which is approximately 2 × ⌈N/K⌉. Each recursive call adds one frame to the call stack, so space usage is O(N/K).

Why This Approach Is Not Efficient

The flag-based approach works correctly but has a design weakness: it requires four parameters (current value, original value, step size, and direction flag). The flag variable adds conceptual overhead — the caller must remember to initialize it as true.

More importantly, the function uses tail recursion in a linear chain: each call makes exactly one recursive call and does nothing after it returns. This is essentially a loop disguised as recursion.

A more elegant approach uses the natural structure of the call stack to avoid the flag entirely. By printing the current value, recursing with the subtracted value, and then printing the current value again after the recursion returns, we can generate the V-shape using the call stack's unwinding behavior. This eliminates the need for a direction flag and reduces the parameter count from four to three.

Optimal Approach - Stack-Based Unwinding

Intuition

Here is the key insight: the output series is symmetric — the values going down are mirrored by the values going back up (except for the bottom value which appears only once). For example, with N=20, K=6:

Down:  20  14  8  2
Bottom:           -4
Up:           2  8  14  20

This mirror structure maps perfectly to how recursion works. If we:

  1. Print the current value (this handles the "going down" part)
  2. Recurse with current - K (this goes deeper)
  3. Print the current value again after the recursion returns (this handles the "going up" part)

The "going down" prints happen as we recurse deeper. The "going up" prints happen as the call stack unwinds. The bottom value (where current ≤ 0) is the base case — it prints only once.

Imagine walking down into a cave with numbered rooms. You announce each room number as you enter. At the bottom, you turn around. As you climb back up, you announce each room number again. Every room gets called out twice — once on the way down, once on the way up — except the deepest room which you only announce once before turning around.

Step-by-Step Explanation

Let's trace through with N = 20, K = 6:

Step 1: Call f(20). Print 20 (pre-recursion). Since 20 > 0, recurse with f(14). Output so far: "20".

Step 2: Call f(14). Print 14 (pre-recursion). Since 14 > 0, recurse with f(8). Output so far: "20 14".

Step 3: Call f(8). Print 8 (pre-recursion). Since 8 > 0, recurse with f(2). Output so far: "20 14 8".

Step 4: Call f(2). Print 2 (pre-recursion). Since 2 > 0, recurse with f(-4). Output so far: "20 14 8 2".

Step 5: Call f(-4). Print -4 (this is the bottom). Since -4 ≤ 0, this is the BASE CASE. Return WITHOUT the post-recursion print. Output so far: "20 14 8 2 -4".

Step 6: Back in f(2): the recursive call returned. Now execute the post-recursion print: print 2. Output so far: "20 14 8 2 -4 2".

Step 7: Back in f(8): post-recursion print: print 8. Output so far: "20 14 8 2 -4 2 8".

Step 8: Back in f(14): post-recursion print: print 14. Output so far: "20 14 8 2 -4 2 8 14".

Step 9: Back in f(20): post-recursion print: print 20. Final output: "20 14 8 2 -4 2 8 14 20".

Stack Unwinding: Print Before AND After Recursion — Watch how each recursive call prints its value on the way down, and then prints it again on the way back up during stack unwinding, creating the symmetric V-shaped series.

Algorithm

  1. Define a recursive function printSeries(current, N, K) with three parameters
  2. Print the current value (pre-recursion print — this builds the descending part)
  3. Base case: If current ≤ 0, return immediately (the bottom of the V)
  4. Recursive step: Call printSeries(current - K, N, K) to go deeper
  5. Post-recursion action: After the recursive call returns, print current again (this builds the ascending part)
  6. Initial call: printSeries(N, N, K)

Code

#include <iostream>
using namespace std;

class Solution {
public:
    void printSeries(int current, int N, int K) {
        // Print current value (descending part)
        cout << current << " ";
        
        // Base case: reached zero or below — bottom of the V
        if (current <= 0)
            return;
        
        // Recurse deeper (subtract K)
        printSeries(current - K, N, K);
        
        // Post-recursion print (ascending part)
        cout << current << " ";
    }
    
    void solve(int N, int K) {
        printSeries(N, N, K);
    }
};

int main() {
    Solution sol;
    sol.solve(20, 6);
    return 0;
}
import sys
sys.setrecursionlimit(10**6 + 10)

class Solution:
    def printSeries(self, current: int, N: int, K: int) -> None:
        # Print current value (descending part)
        print(current, end=" ")
        
        # Base case: reached zero or below — bottom of the V
        if current <= 0:
            return
        
        # Recurse deeper (subtract K)
        self.printSeries(current - K, N, K)
        
        # Post-recursion print (ascending part)
        print(current, end=" ")
    
    def solve(self, N: int, K: int) -> None:
        self.printSeries(N, N, K)

# Driver code
if __name__ == "__main__":
    sol = Solution()
    sol.solve(20, 6)
class Solution {
    private void printSeries(int current, int N, int K) {
        // Print current value (descending part)
        System.out.print(current + " ");
        
        // Base case: reached zero or below — bottom of the V
        if (current <= 0)
            return;
        
        // Recurse deeper (subtract K)
        printSeries(current - K, N, K);
        
        // Post-recursion print (ascending part)
        System.out.print(current + " ");
    }
    
    public void solve(int N, int K) {
        printSeries(N, N, K);
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.solve(20, 6);
    }
}

Complexity Analysis

Time Complexity: O(N/K)

The recursion depth is ⌈N/K⌉ + 1 (the number of subtractions needed to go from N past zero, plus the base case). Each call does O(1) work (two prints for non-base calls, one print for the base case). Total time is O(N/K).

Space Complexity: O(N/K)

The maximum recursion depth is ⌈N/K⌉ + 1 stack frames. Each frame stores the local value of current. This is O(N/K) space.

Compared to the flag-based brute force: both approaches have the same asymptotic complexity, but this approach is superior because:

  • It uses 3 parameters instead of 4 (no flag needed)
  • The logic is more concise — a single print-recurse-print pattern replaces conditional flag switching
  • It leverages the call stack's natural unwinding behavior, which is the idiomatic way to solve symmetric-output recursion problems
  • It teaches the important concept of pre-recursion vs. post-recursion operations, which appears in many algorithms (e.g., inorder tree traversal, palindrome checking)