Recursivitatea: cazul de bază și stiva de apeluri
O funcție recursivă se apelează pe ea însăși pentru o versiune mai mică a aceleiași probleme. Este baza pentru tot ce urmează în modul: backtracking, merge sort, căutare binară, arbori. Azi înveți cele două ingrediente obligatorii: cazul de bază și pasul recursiv, și vezi ce face Python în spate, pe stiva de apeluri.
Ideea: problema mai mică
Suma listei [1, 2, 3, 4] este 1 + suma([2, 3, 4]). Iar suma lui [2, 3, 4] este 2 + suma([3, 4]), și tot așa, până la lista goală, a cărei sumă este 0. Ai redus problema la o problemă identică, dar mai mică.
def numaratoare(n):
if n == 0:
print('Start!')
return
print(n)
numaratoare(n - 1) 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ă).
- Cazul de bază în ambele: lista goală -> 0.
- Pasul recursiv: primul element + apelul pe lista[1:] (la numărare adaugi 1 doar dacă lista[0] == x).
- Trebuie să apară: 10, 0, 3, 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan