Recursive Program to Print All Numbers Less Than N with Digits 1 or 3 Only

Table of Contents#

1. Understanding the Problem
2. Recursive Approach: Intuition
3. Code Implementation
4. Code Explanation
5. Best Practices in Recursion
6. Example Usage
7. Optimizations (Iterative Alternative)
8. Conclusion
9. References

1. Understanding the Problem#

We need to generate and print all numbers less than ( N ) that use only the digits 1 or 3. For example:

• If ( N = 20 ), the valid numbers are 1, 3, 11, 13 (all less than 20 and composed of 1/3).
• If ( N = 10 ), the valid numbers are 1, 3 (since 11 ≥ 10).

Key Requirements:#

• Numbers must be less than ( N ).
• Each digit in the number must be either 1 or 3 (no other digits allowed).

2. Recursive Approach: Intuition#

Recursion works by breaking a problem into smaller subproblems. For this task:

• Base Case: A number is invalid (or complete) if it is ≥ ( N ).
• Recursive Case: For a valid number ( \text{current} ) (less than ( N )):
  • Print ( \text{current} ).
  • Generate new numbers by appending 1 or 3 to ( \text{current} ) (i.e., ( \text{current} \times 10 + 1 ) and ( \text{current} \times 10 + 3 )).
  • Recursively check these new numbers.

3. Code Implementation#

We implement the solution in Python. The code uses a nested recursive function to generate numbers incrementally:

def printNumbersWith1Or3(N):
    """
    Print all numbers < N with digits 1 or 3 only, using recursion.
    """
    def recursive(current):
        # Base case: if current >= N, stop recursion
        if current >= N:
            return
        # Print the valid number
        print(current)
        # Generate next numbers by appending 1 and 3
        recursive(current * 10 + 1)
        recursive(current * 10 + 3)
    
    # Start with 1 and 3 (since numbers can't have leading zeros)
    if 1 < N:
        recursive(1)
    if 3 < N:
        recursive(3)

4. Code Explanation#

Step-by-Step Breakdown:#

1. Outer Function (printNumbersWith1Or3):

   • Accepts ( N ) as input.
   • Calls the inner recursive function recursive() with initial values 1 and 3 (only if they are less than ( N )).

2. Inner Recursive Function (recursive):

   • Base Case Check: If current ≥ N, the number is invalid—return (terminate recursion).
   • Print Valid Number: If current < N, print it.
   • Generate Next Numbers: Append 1 or 3 to current (e.g., current * 10 + 1 and current * 10 + 3), and recurse on these new numbers.

How Recursion Unfolds (Example: ( N = 20 )):#

• Start with recursive(1):
  • 1 < 20 → print 1.
  • Recurse on 1 * 10 + 1 = 11 and 1 * 10 + 3 = 13.
• For recursive(11):
  • 11 < 20 → print 11.
  • Recurse on 11 * 10 + 1 = 111 (≥20 → return) and 11 * 10 + 3 = 113 (≥20 → return).
• For recursive(13):
  • 13 < 20 → print 13.
  • Recurse on 13 * 10 + 1 = 131 (≥20 → return) and 13 * 10 + 3 = 133 (≥20 → return).
• Then, recursive(3):
  • 3 < 20 → print 3.
  • Recurse on 3 * 10 + 1 = 31 (≥20 → return) and 3 * 10 + 3 = 33 (≥20 → return).

5. Best Practices in Recursion#

1. Base Case Handling:#

• Always define a clear base case (e.g., current ≥ N) to terminate recursion. Without it, the function will run infinitely (stack overflow).

2. Avoiding Stack Overflow:#

• Recursion depth is limited by the number of digits in ( N ). For ( N = 10^6 ), the maximum recursion depth is 6 (e.g., 333333 has 6 digits), which is safe.

3. Input Validation:#

• Check if the initial numbers (1 and 3) are less than ( N ) before calling the recursive function (e.g., if 1 < N: recursive(1)).

6. Example Usage#

Testing with Different ( N ):#

• Case 1: ( N = 10 )
  Output: 1, 3 (since 11 ≥ 10).

• Case 2: ( N = 30 )
  Output: 1, 11, 13, 3 (order depends on recursion, but all valid numbers are printed).

• Case 3: ( N = 1 )
  Output: (no numbers, since 1 and 3 are not less than ( 1 )).

Edge Cases:#

• ( N = 2 ): Only 1 is printed (since 3 ≥ 2).
• ( N = 100 ): Prints numbers like 1, 11, 13, 3, 31, 33, 111, 113, 131, 133, 311, 313, 331, 333 (all < 100 and with digits 1/3).

7. Optimizations (Iterative Alternative)#

For large ( N ), an iterative approach (using a queue for BFS) can be more memory-efficient:

from collections import deque
 
def printNumbersWith1Or3Iterative(N):
    """
    Iterative (BFS) approach to print all numbers < N with digits 1 or 3.
    """
    result = []
    queue = deque()
    # Initialize with 1 and 3 (if valid)
    if 1 < N:
        queue.append(1)
    if 3 < N:
        queue.append(3)
    
    while queue:
        current = queue.popleft()
        result.append(current)
        # Generate next numbers
        next1 = current * 10 + 1
        next3 = current * 10 + 3
        if next1 < N:
            queue.append(next1)
        if next3 < N:
            queue.append(next3)
    
    # Print in sorted order
    for num in sorted(result):
        print(num)

8. Conclusion#

Recursion provides a clean, intuitive solution to generate numbers with specific digit constraints. By building numbers incrementally (digit by digit) and using recursion to explore all possibilities, we efficiently print all valid numbers less than ( N ). Best practices like base case handling and input validation ensure the solution is robust. For larger ( N ), an iterative (BFS) approach can be used for optimization.

References#

1. Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (for recursion concepts).
2. Python Documentation on Recursion: Python Recursion FAQ.
3. Competitive Programming resources (e.g., Codeforces, LeetCode) for digit-based number generation problems.

This blog aimed to demystify the recursive approach to generate numbers with digits 1 or 3 less than ( N ). Recursion’s ability to break problems into smaller subproblems makes it ideal for this task, while best practices and optimizations ensure efficiency and correctness.