Mis on rekursiivne funktsioon?

Funktsioon kutsub ennast uuesti ja uuesti, kuni see vastab rekursiivsele tingimusele. Rekursioonifunktsioon jaotab probleemi väiksemateks probleemideks ja kutsub väiksema probleemi lahendamiseks välja oma loogika. Seda tehnikat nimetatakse jagamiseks ja vallutamiseks. Seda kasutatakse matemaatikas ja arvutiteaduses.

Rekursiivne funktsioon sisaldab põhi- või lõppjuhtumit ja rekursiivset juhtumit. Algjuhtumis võite kaaluda peamise lahendatava probleemi lahendamist ja rekursiivne juhtum jagab probleemi väiksemateks osadeks, kuni see jõuab tasemeni, kus seda saab hõlpsasti lahendada. Rekursiivne juhtum võib tulemuse anda või võib probleemi edasiseks jaotamiseks uuesti helistada. Iga kord, kui probleem jaguneb väiksemaks probleemiks, salvestab funktsioon, millele helistatakse rekursiivselt, kõne oleku ja oodatakse tulemust ise pärast probleemi lahendamist.

Rekursiivne funktsioon Pythonis

Rekursiooni mõiste jääb Pythonis samaks. Funktsioon kutsub ennast probleemi väiksemateks probleemideks jaotamiseks. Lihtsaim näide, mida võiksime rekursioonist mõelda, oleks arvu faktoraali leidmine.

Ütleme, et peame leidma arvu 5 => 5 teguri! (Meie probleem)

5 leidmiseks! probleemi saab jagada väiksemateks 5! => 5 x 4!

Niisiis, saada 5! Peame leidma 4! ja korruta see 5-ga.

Jätkame probleemi jagamist

5! = 4! x 5

4! = 3! x 4

3! = 3 x 2!

2! = 2 x 1!

1! = 1

Kui see jõuab väikseima tükini, st kui saada koefitsient 1, saame tulemuse tagastada kui:

Võtame pseudokoodi näite: -

Faktoriaalse algoritm

Vaatame faktoriaalide algoritmi:

function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)

Funktsioonikõned

Oletame, et leiame koefitsiendi 5.

get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call

Lõpptulemus on 120, kus alustasime funktsiooni täitmist. Meie rekursioonifunktsioon peatub, kui arv on nii vähenenud, et tulemuse saab.

  • Esimene kõne, mis saab koefitsiendi 5, annab rekursiivse seisundi, kus see lisatakse virna ja pärast numbri vähendamist 4-ni tehakse veel üks kõne.
  • Selle rekursiooniga helistatakse ja probleem jagatakse väiksemateks tükkideks, kuni see jõuab põhitingimusele.
  • Põhitingimus on siin siis, kui arv on 1.
  • Igal rekursiivsel funktsioonil on oma rekursiivne seisund ja baastingimus.

Pythoni rekursiivse funktsiooni plussid ja miinused

  • Rekursiooni teostamine toimub nii, et ta ei tee mingeid arvutusi enne, kui jõuab baastingimusele.
  • Baastingimustesse jõudmisel võib mälu otsa saada.
  • Suures probleemis, kus võib olla miljon sammu või võime öelda, et programmi kordamine võib põhjustada miljoni korduse, mis võib põhjustada mäluvea või segmenteerimisvea.
  • 1000000! = 1000000 * 999999! =?
  • Rekursioon erineb iteratsioonist ja see ei suurene iteratiivse meetodina.
  • Erinevatel keeltel on rekursiooni optimeerimine erinev.
  • Paljudes keeltes toimiks iteratiivne meetod paremini kui rekursioon.
  • Igal keelel on rekursiooni sügavusele teatud piirangud, millega võite silmitsi seista suurte probleemide lahendamisel.
  • Mõnikord on raske mõista rekursiooni keerukaid probleeme, samas kui iteratsiooniga on see üsna lihtne.

Mõned plussid

  • Mõnel juhul on rekursioon mugav ja kiire viis kasutada.
  • Väga palju kasu puu liikumisel ja kahendotsingul.

Pythoni kood - rekursioon vs iteratsioon

Mõistsime, mis on rekursioon ja kuidas see Pythonis töötab, kuna me teame, et kõigil keeltel on mälu rekursiooni erinev rakendamine ja arvutuslikud optimeerimised. Võib esineda juhtumeid, kus iteratsioon oleks kiirem kui rekursioon.

Võrdleme siin nii rekursiooni kui ka iteratsiooni meetodit, et näha, kuidas Python mõlemal juhul töötab.

1. Faktoriaalse rekursiooni kood

def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition

2. Faktoriprobleem iteratsiooni abil (silmus)

def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact

3. Tulemuste printimine

print(get_recursive_factorial(6))
print(get_iterative_factorial(6))

Väljund:

Nagu näeme, annavad mõlemad sama väljundi, nagu oleme kirjutanud sama loogika. Siin ei näe me erinevusi täitmises.

Lisame ajakoodi, et saada rohkem teavet Pythoni rekursiooni ja iteratsiooni täitmise kohta.

Impordime ajaraamatukogu ja kontrollime, kui palju kordus ja iteratsioon tulemuse tagastamiseks kulub.

4. Kood ajaarvestusega

import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))

Teeme korduvaid hukkamisi erineva väärtusega faktoriaalide jaoks ja näeme tulemusi. Allpool toodud tulemused võivad masiniti erineda. Oleme kasutanud MacBook Pro 16 GB RAM i7.

Kasutame täitmiseks Python 3.7

Juhtum 1: - Faktoriaal 6:

Juhtum 2: Faktoriaal 50st:

Juhtum 3: 100 faktoorium:

Juhtum 4: 500 faktoorium:

Juhtum 5: Faktoriaal 1000:

Oleme mõlemat meetodit analüüsinud erineva probleemina. Pealegi on mõlemad, välja arvatud 4. juhtum, sarnased.

Juhtumi 5 puhul saime viga rekursiooniga tehes.

Python sai piirangu maksimaalsele sügavusele, mida saab kasutada rekursiooniga, kuid sama probleem, mille sain iteratsiooniga lahendada.

Pythonil on piirangud ülevoolu probleemile. Python pole saba rekursiooni jaoks optimeeritud ja kontrollimatu rekursioon põhjustab virna ületäitumist.

Funktsioon “sys.getrecursionlimit ()” ütleb teile rekursiooni piiri.

Rekursioonilimiiti saab muuta, kuid ei soovita, see võib olla ohtlik.

Järeldus - Pythoni rekursiivne funktsioon

  • Rekursioon on mugav lahendus mõnele probleemile, näiteks puude liikumine ja muud probleemid.
  • Python ei ole funktsionaalne programmeerimiskeel ja näeme, et rekursioonipakk pole iteratsiooniga võrreldes nii optimeeritud.
  • Peaksime oma algoritmis iteratsiooni kasutama, kuna see on Pythonis optimeeritud ja annab teile parema kiiruse.

Soovitatavad artiklid

See on Pythoni rekursiivse funktsiooni juhend. Siin räägime sellest, mis on rekursiivne funktsioon, Pythoni rekursiivne funktsioon, faktoriaalide algoritm jne. Lisateabe saamiseks võite minna ka meie teistest soovitatud artiklitest -

  1. Faktuur Pythonis
  2. Spark Shelli käsud
  3. Parimad C-kompilaatorid
  4. Algoritmide tüübid
  5. Faktoriprogramm JavaScriptis
  6. Unixi kesta käskude loendi juhend
  7. Vormide tüübid reageerige näidetega

Kategooria:

Tarkvaraarendus