Recursivitate pe texte
Un text este o problemă recursivă naturală: dacă știi să rezolvi pentru textul fără primul (sau fără primul și ultimul) caracter, rezolvi și pentru textul întreg. Azi verifici palindroame și inversezi texte recursiv, apoi vezi de ce felierea textului ascunde un cost O(n²).
Palindromul, recursiv
Un palindrom se citește la fel în ambele sensuri: radar, cojoc. Observația recursivă: un text este palindrom dacă primul și ultimul caracter sunt egale și ce rămâne la mijloc este tot palindrom.
def palindrom(text, nivel=0):
print(' ' * nivel + repr(text))
if len(text) <= 1:
return True
if text[0] != text[-1]:
return False Scrie recursiv funcțiile palindrom_recursiv(text) (returnează True/False) și inverseaza_recursiv(text) (returnează textul inversat). Fără bucle, fără [::-1] și fără reversed.
- Palindrom: caz de bază len(text) <= 1, compară capetele, apoi apel pe text[1:-1].
- Inversare: caz de bază textul gol, apoi inverseaza_recursiv(text[1:]) + text[0].
- Trebuie să apară: True, False, True, True, 'cba', ''.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Recursivitate, backtracking, sortare și căutare binară.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan