Problem Statement

Write a program that prints numbers form 1 to n in a linear fashion, using recursion. The program should prompt user the user to input a positive integer n, and then prints numbers from 1 to n sequentially.

Problem Understanding

To solve this problem recursively, we need to understand that printing numbers from 1 to n linearly means printing each number one after the other without skipping any. Recursion involves breaking down a problem into smaller instances until reaching a base case. In this case, the base case occurs when we reach the number n, at which point we stop recursing.

Examples

Example 1:

Input: n = 5
Output: 1 2 3 4 5

Example 2:

Input: n = 10
Output: 1 2 3 4 5 6 7 8 9 10

Different Approaches

1️⃣ Top-Down Approach (Basic Recursion)

In this approach, we will call the function recursively to print numbers from 1 to N.

At each step, we will print the current number and then call the function recursively with N-1.

Recursion Tree:

printLinear(5)
    |
    --> printLinear(4)
            |
            --> printLinear(3)
                    |
                    --> printLinear(2)
                            |
                            --> printLinear(1)
                                    |
                                    --> printLinear(0)

Code Implementation in C++:

#include <iostream>
using namespace std;

void printLinear(int n) {
    if (n == 0)
        return;
    printLinear(n - 1);
    cout << n << " ";
}

int main() {
    int n;
    cout << "Enter the value of N: ";
    cin >> n;
    cout << "Numbers from 1 to " << n << " are: ";
    printLinear(n);
    return 0;
}

Complexity Analysis:

Let's analyze the time complexity of the solution:

Time Complexity:

• The function printNumbersLinearly is called recursively n times.
• Each recursive call performs a constant amount of work (printing the current number), which can be considered O(1) time complexity.
• Therefore, the overall time complexity of the solution is O(n) as well, where n is the input number.

Space Complexity:

• The space complexity of the solution is O(n) as well, considering the recursive calls create a call stack with n times, each storing information about the function call.

2️⃣ Bottom-Up Approach (Tail Recursion):

In this approach, we will use tail recursion to print numbers from 1 to N.

We will pass the current number and N to the recursive function and print the current number before making the recursive call.

Recursion Tree:

printLinearUtil(1, 5)
    |
    --> printLinearUtil(2, 5)
            |
            --> printLinearUtil(3, 5)
                    |
                    --> printLinearUtil(4, 5)
                            |
                            --> printLinearUtil(5, 5)

Code Implementation in C++:

#include <iostream>

void printNumbersLinearly(int current, int n) {
    // Base case: If current exceeds n, return without printing anything
    if (current > n) {
        return;
    }
    
    // Print the current number
    std::cout << current << std::endl;
    
    // Recursively call printNumbersLinearly with the next number
    printNumbersLinearly(current + 1, n);
}

int main() {
    int n;

    // Prompt the user to enter a positive integer
    std::cout << "Enter a positive integer (n): ";
    std::cin >> n;

    // Call the recursive function to print numbers from 1 to n
    printNumbersLinearly(1, n);

    return 0;
}

Complexity Analysis:

Let's analyze the time complexity of the solution:

Time Complexity:

• The function printNumbersLinearly is called recursively n times.
• Each recursive call performs a constant amount of work (printing the current number), which can be considered O(1) time complexity.
• Therefore, the overall time complexity of the solution is O(n) as well, where n is the input number.

Space Complexity:

• The space complexity of the solution is O(1) because tail recursion is optimized by most modern compilers. The compiler optimizes tail recursive calls by reusing the stack frame for each recursive call. Therefore, only a single stack frame is used throughout the recursion, leading to constant space complexity.