Recursivitatea în limbajul de programare Python

Recursivitatea

În Python, o funcție recursivă este o funcție care se autoinvocă.

Introducere la recursivitate

Până acum, în Python, am văzut funcții care apelează alte funcții. Cu toate acestea, este posibil ca o funcție să se autoapeleze singură. Să ne uităm la un exemplu simplu.


# Program by Mitchell Aikens
# No Copyright
# 2010

num = 0

def main():
    counter(num)

def counter(num):
    print(num)
    num += 1
    counter(num)

main()

Dacă ar fi să rulați acest program în IDLE, ar rula pentru totdeauna. Singura modalitate de a opri bucla ar fi să întrerupeți execuția apăsând Ctrl + C de pe tastatură. Acesta este un exemplu de recursivitate infinită. (Unii utilizatori au raportat o eroare în sistemul IDLE actual, care face ca excepția creată de Ctrl + C să înceapă și ea în buclă. Dacă se întâmplă acest lucru, apăsați Ctrl + F6, iar shell IDLE ar trebui să repornească.)

Este discutabil dacă recursivitatea este doar o altă modalitate de a realiza același lucru ca o buclă while. În unele cazuri, acest lucru este absolut corect. Cu toate acestea, există și alte utilizări pentru recursivitate care sunt foarte valide, unde buclele while sau buclele for pot să nu fie optime.

Recursivitatea poate fi controlată, la fel ca buclele. Să ne uităm la un exemplu de buclă controlată.


# Program by Mitchell Aikens
# No copyright
# 2012
def main():
    loopnum = int(input("How many times would you like to loop?\n"))
    counter = 1
    recurr(loopnum,counter)

def recurr(loopnum,counter):
    if loopnum > 0:
        print("This is loop iteration",counter)
        recurr(loopnum - 1,counter + 1)
    else:
        print("The loop is complete.")

main()

Cele de mai sus folosesc argumente/parametri pentru a controla numărul de recursiuni. Pur și simplu utilizați ceea ce știți deja despre funcții și urmăriți fluxul programului. Este simplu de înțeles. Dacă întâmpinați probleme, vă rugăm să consultați Exemplu de funcții avansate.

Aplicații practice ale recursivității

Adesea, recursivitatea este studiată la un nivel avansat de informatică. Recursivitatea este de obicei folosită pentru a rezolva probleme complexe care pot fi împărțite în probleme mai mici, identice. Recursivitatea nu este necesară pentru a rezolva o problemă. Probleme care pot fi rezolvate cu recursivitate, cel mai probabil pot fi rezolvate cu bucle. De asemenea, o buclă poate fi mai eficientă decât o funcție recursivă. Funcțiile recursive necesită mai multă memorie și resurse decât buclele, ceea ce le face mai puțin eficiente în multe cazuri. Această cerință de utilizare este uneori denumită overhead. S-ar putea să vă gândiți: „Ei bine, de ce să vă deranjați cu recursiunea. Voi folosi doar o buclă. Știu deja cum să fac bucla deși aceasta presupune mult mai multă muncă.” Acest gând este de înțeles, dar nu în întregime ideal. Când rezolvați probleme complexe, o funcție recursivă este uneori mai ușor, mai rapid și mai simplu de construit și codificat.

Gândiți-vă la aceste două „reguli”:

Dacă pot rezolva problema acum, fără recursivitate, funcția returnează pur și simplu o valoare.
Dacă nu pot rezolva problema acum fără recursivitate, funcția reduce problema la ceva mai mic și similar și se autoinvocă pentru a rezolva problema.

Să aplicăm aceasta folosind un concept matematic comun, factoriali:

Factorialul unui număr n, se notează cu n!.

Iată câteva reguli de bază ale factoriale.

Dacă n = 0 atunci n! = 1 Dacă n > 0 atunci n! = 1 x 2 x 3 x … x n

De exemplu, să ne uităm la factorialul numărului 9.

9! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9

Să ne uităm la un program care calculează factorialul oricărui număr introdus de utilizator, prin metoda recursivității.


def main():
    num = int(input("Please enter a non-negative integer.\n"))
    fact = factorial(num)
    print("The factorial of",num,"is",fact)

def factorial(num):
    if num == 0:
        return  1
    else:
        return num * factorial(num - 1)

main()