Clasa a X-a · RecursivitateRead in English

Inversarea unui șir de caractere, recursiv în C++

În engleză: Reversing a string, recursively

O(n)C++1739 de linii2 exemple

Ideea

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'.

Descrierea în engleză

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'.

Complexitate
O(L) timp și O(L) memorie pe stivă
Clasa
Clasa a X-a (Grade 10)

Exemple

Exemplul 1

Intrare

recursiv

Ieșire așteptată

visrucer
Exemplul 2

Intrare

a

Ieșire așteptată

a

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

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;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.