Reversing a string, recursively

Original: Inversarea unui șir de caractere, recursiv

O(n)C++1739 lines2 examples

The idea

The function inverseaza(s, i) handles the characters from position i to the end. If s[i] is not '\0', it first calls itself for the rest of the string (i + 1) and only on the way back prints s[i]. This way the last character is printed first. The stopping condition is s[i] == '\0'.

Original description (Romanian)

Funcția inverseaza(s, i) se ocupă de caracterele de la poziția i până la final. Dacă s[i] nu este '\0', întâi se autoapelează pentru restul șirului (i + 1) și abia la întoarcere afișează s[i]. Așa ultimul caracter este afișat primul. Condiția de oprire este s[i] == '\0'.

Complexity: O(L) time and O(L) stack memory
Grade: Grade 10 (Clasa a X-a)
Chapter: Recursion

Examples

Example 1

Input

recursiv

Expected output

visrucer

Example 2

Input

Expected output

The code

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

inversarea-unui-sir-recursiv.cpp

/*
 * Titlu: Inversarea unui șir de caractere, recursiv
 * Clasa: 10
 * Capitol: Recursivitate
 * Descriere: Funcția inverseaza(s, i) se ocupă de caracterele de la poziția i până la
 *            final. Dacă s[i] nu este '\0', întâi se autoapelează pentru restul
 *            șirului (i + 1) și abia la întoarcere afișează s[i]. Așa ultimul
 *            caracter este afișat primul. Condiția de oprire este s[i] == '\0'.
 * Complexitate: O(L) timp și O(L) memorie pe stivă
 *
 * Exemplu
 * Intrare: recursiv
 * Ieșire: visrucer
 *
 * Exemplu
 * Intrare: a
 * Ieșire: a
 */
#include <iostream>
using namespace std;

void inverseaza(char s[], int i)
{
    if (s[i] != '\0')
    {
        inverseaza(s, i + 1);
        cout << s[i];
    }
}

int main()
{
    char s[256];
    cin >> s;
    inverseaza(s, 0);
    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.