...
Recursivitate

Recursivitate: ce este și cum funcționează, cu exemple

Pe scurt

O funcție recursivă este o funcție care se apelează pe ea însăși, de fiecare dată pentru o problemă mai mică, până ajunge la un caz atât de simplu încât știe răspunsul direct: cazul de bază. Exemplul clasic e factorialul: 5! = 5 × 4!, iar 1! = 1. Fiecare apel așteaptă pe stiva de apeluri până primește rezultatul celui de sub el.

  • 2părți: cazul de bază și apelul recursiv
  • 1stivă de apeluri, câte un nivel pentru fiecare apel
  • O(n)apeluri pentru factorial(n)
  • 2lecții gratuite, fără card
STIVA DE APELURI factorial(4) 4 * f(3) factorial(3) 3 * f(2) factorial(2) 2 * f(1) factorial(1) return 1 apeluri ↑ 1, 2, 6, 24 rezultate ↓ caz de bază factorial(n)

Stiva de apeluri, în animație

Alege n și apasă „Pornește”. Fiecare apel se pune deasupra celui care l-a chemat; la cazul de bază, apelurile se întorc pe rând cu rezultatul.

Cele două părți ale unei funcții recursive

1. Cazul de bază este condiția în care funcția răspunde direct, fără să se mai apeleze. Fără el, funcția s-ar apela la nesfârșit, până când programul se oprește cu eroare (stack overflow în C++ și Java, RecursionError în Python).

2. Apelul recursiv rezolvă o versiune mai mică a aceleiași probleme și o folosește ca să construiască răspunsul. Fiecare apel trebuie să se apropie de cazul de bază: factorial(n) cheamă factorial(n - 1), nu factorial(n).

Cum se execută factorial(4): apelul pentru 4 așteaptă rezultatul lui 3, care îl așteaptă pe al lui 2, care îl așteaptă pe al lui 1. factorial(1) e cazul de bază și întoarce 1; apoi 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24. Exact asta vezi în animația de mai sus.

Factorial recursiv în C++, Python și Java

Plus Fibonacci cu memoizare: aceeași recursivitate, dar fiecare valoare se calculează o singură dată.

def factorial(n):
    if n <= 1:                  # cazul de bază: aici se oprește
        return 1
    return n * factorial(n - 1) # apel recursiv pe o problemă mai mică


print(factorial(5))   # 120

Încearcă: suma unei liste, scrisă recursiv

Problema din lecția 66 a cursului de algoritmi. Scrii funcțiile în Python, fără bucle, și primești verificarea pe loc.

Exercițiu din lecția 66 · cursul de algoritmi

Recursivitatea: cazul de bază și stiva de apeluri

Scrie recursiv (fără for, while, sum sau count) funcțiile suma_recursiva(lista) și numara_aparitii(lista, x) (de câte ori apare x în listă).

  1. Cazul de bază în ambele: lista goală -> 0.
  2. Pasul recursiv: primul element + apelul pe lista[1:] (la numărare adaugi 1 doar dacă lista[0] == x).
  3. Trebuie să apară: 10, 0, 3, 0.
Indiciu: Nu uita return în fața apelului recursiv.
def suma_recursiva(lista):
    if not lista:
        return 0
    return lista[0] + suma_recursiva(lista[1:])


def numara_aparitii(lista, x):
    if not lista:
        return 0
    if lista[0] == x:
        return 1 + numara_aparitii(lista[1:], x)
    return numara_aparitii(lista[1:], x)


print(suma_recursiva([1, 2, 3, 4]))
print(suma_recursiva([]))
print(numara_aparitii([1, 2, 1, 1], 1))
print(numara_aparitii([5, 6], 7))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Recursiv sau iterativ?

RecursivIterativ (cu bucle)
Codscurt, apropiat de definiția matematicăde obicei mai lung
Memorieun nivel pe stivă pentru fiecare apelO(1) în plus, de cele mai multe ori
Potrivit pentruarbori, backtracking, divide et impera (merge sort, quicksort)parcurgeri simple, sume, numărări
Riscstack overflow la adâncimi mari, calcule repetatebucle infinite

Fibonacci scris naiv recursiv face un număr exponențial de apeluri, pentru că recalculează aceleași valori. Cu memoizare (ții minte rezultatele) devine O(n). Aici începe programarea dinamică.

Recursivitatea la BAC

La BAC Informatică recursivitatea apare aproape în fiecare an la Subiectul II: primești un subprogram recursiv și trebuie să spui ce valoare întoarce sau ce afișează pentru un apel dat. Metoda sigură: scrii pe hârtie stiva de apeluri, ca în animație, de sus în jos, apoi calculezi rezultatele de jos în sus. La Subiectul III poți scrie subprograme recursive pentru cifrele unui număr, CMMDC (algoritmul lui Euclid) sau sume.

Pentru Java, vezi și articolul despre metode recursive în Java.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Am participat la cursul C# incepatori. Pentru mine a fost o experienta eficienta. Nu stiam nimic despre programare, insa, acest lucru nu a fost o problema. Structura cursului a fost pe intelesul oricui, iar Gabi a avut rabdarea sa explice pas cu pas. Si de mai muuulte ori cand era cazul :)

Fotografia lui Sorin, cursant al Academiei ProgramatorilorSorinRecenzie pe Google

Foarte profi si utile cursurile. Trainer-ii sunt foarte rabdatori. Cursurile sunt aplicate si cu multe exercitii fapt ce m-a ajutat sa invat destul de repede desi nu aveam cunostinte de programare.

Fotografia lui Marina Pahom, cursant al Academiei ProgramatorilorMarina PahomRecenzie pe Google

Am parcurs cursul de java pentru incepatori si cursul de sql si sunt super multumita. Daca doresti sa inveti programare, recomand!

Fotografia lui Alexandra Zbant, cursant al Academiei ProgramatorilorAlexandra ZbantRecenzie pe Google

Întrebări frecvente

Ce este recursivitatea?

Recursivitatea este tehnica prin care o funcție se apelează pe ea însăși pentru a rezolva o versiune mai mică a aceleiași probleme. Se oprește la un caz de bază, pentru care răspunsul e cunoscut direct.

Ce este cazul de bază?

Cazul de bază este condiția în care funcția recursivă nu se mai apelează și întoarce direct un rezultat, de exemplu factorial(1) = 1. Fără caz de bază, funcția se apelează la infinit și programul se oprește cu eroare de tip stack overflow.

Ce este stiva de apeluri?

Stiva de apeluri este zona de memorie în care programul ține minte fiecare apel de funcție care nu s-a terminat încă, cu parametrii și variabilele lui. La recursivitate, fiecare apel nou se pune deasupra, iar când se termină, se scoate și rezultatul lui ajunge la apelul de dedesubt.

Care e diferența dintre recursivitate directă și indirectă?

La recursivitatea directă funcția se apelează pe ea însăși. La cea indirectă, funcția A apelează funcția B, iar B o apelează din nou pe A.

Este recursivitatea mai lentă decât iterația?

De obicei puțin, pentru că fiecare apel costă timp și memorie pe stivă. Diferența mare apare când recursivitatea recalculează aceleași valori, ca la Fibonacci naiv; acolo memoizarea sau o variantă iterativă rezolvă problema.

Unde exersez recursivitatea?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai lecții despre cazul de bază, Fibonacci cu memoizare și recursivitate pe texte, cu probleme rezolvate în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.