Printing the digits in order, recursively

Original: Afișarea cifrelor în ordine, recursiv

O(n)C++1746 lines1 example

The idea

Where we print relative to the recursive call matters. In inOrdine we print AFTER the recursive call: first the call for n / 10 finishes (printing the leading digits), and only then do we print the last digit, so the digits come out from left to right. In invers we print BEFORE the recursive call, so the last digit appears first. With no array at all, the call stack 'remembers' the digits for us.

Original description (Romanian)

Contează unde punem afișarea față de autoapel. În inOrdine afișăm DUPĂ autoapel: întâi se termină apelul pentru n / 10 (care afișează cifrele din față), abia apoi afișăm ultima cifră, deci cifrele ies de la stânga la dreapta. În invers afișăm ÎNAINTE de autoapel, deci ultima cifră apare prima. Fără niciun vector, stiva de apeluri „ține minte” cifrele pentru noi.

Complexity: O(k), where k is the number of digits
Grade: Grade 10 (Clasa a X-a)
Chapter: Recursion

Examples

Example 1

Input

Expected output

4 0 9 6
6 9 0 4

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

afisarea-cifrelor-in-ordine.cpp

/*
 * Titlu: Afișarea cifrelor în ordine, recursiv
 * Clasa: 10
 * Capitol: Recursivitate
 * Descriere: Contează unde punem afișarea față de autoapel. În inOrdine afișăm
 *            DUPĂ autoapel: întâi se termină apelul pentru n / 10 (care afișează
 *            cifrele din față), abia apoi afișăm ultima cifră, deci cifrele ies de
 *            la stânga la dreapta. În invers afișăm ÎNAINTE de autoapel, deci ultima
 *            cifră apare prima. Fără niciun vector, stiva de apeluri „ține minte”
 *            cifrele pentru noi.
 * Complexitate: O(k), unde k este numărul de cifre
 *
 * Exemplu
 * Intrare: 4096
 * Ieșire:
 * 4 0 9 6
 * 6 9 0 4
 */
#include <iostream>
using namespace std;

void inOrdine(int n)
{
    if (n > 9)
        inOrdine(n / 10);
    cout << n % 10 << ' ';     // după autoapel
}

void invers(int n)
{
    cout << n % 10 << ' ';     // înainte de autoapel
    if (n > 9)
        invers(n / 10);
}

int main()
{
    int n;
    cin >> n;
    inOrdine(n);
    cout << '\n';
    invers(n);
    cout << '\n';
    return 0;
}

Input (stdin)

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.