Recursivitate:
în termeni de programare, o funcție recursivă poate fi definită ca o rutină care se numește direct sau indirect.
folosind algoritmul recursiv, anumite probleme pot fi rezolvate destul de ușor. Towers of Hanoi (TOH) este un astfel de exercițiu de programare. Încercați să scrieți un algoritm iterativ pentru TOH. Mai mult, fiecare program recursiv poate fi scris folosind metode iterative (consultați structurile de date de Lipschutz).
matematic recursivitate ajută pentru a rezolva câteva puzzle-uri cu ușurință.,
De exemplu, o întrebare de interviu de rutină,
într-o petrecere de n oameni, fiecare persoană își va scutura mâna una cu cealaltă persoană o singură dată. În total, câte strângeri de mână s-ar întâmpla?
soluție:
poate fi rezolvată în moduri diferite, grafice, recursivitate etc. Să vedem, cât de recursiv poate fi rezolvată.
există N persoane. Fiecare persoană se agită cu mâna unul cu celălalt o singură dată. Având în vedere A N-A persoană, trebuie să dea mâna cu (N-1) persoane. Acum, problema redusă la instanță mică de (N-1) persoane. Presupunând TN ca Total shake-hands, acesta poate fi formulat recursiv.,
TN = (N-1) + TN-1
rezolvarea acestuia produce recursiv o serie aritmetică, care poate fi evaluată la N(N-1)/2.
exercițiu: într-o petrecere de cupluri N, un singur gen (bărbat sau femeie) poate da mâna cu fiecare. Câte strângeri de mâini s-ar întâmpla?
De obicei, programe recursive rezultate în dificultăți de timp săraci. Un exemplu este seria Fibonacci. Complexitatea timpului de calcul al numărului n Fibonacci folosind recursivitatea este de aproximativ 1,6 n. înseamnă că același computer are aproape 60% mai mult timp pentru următorul număr Fibonacci. Algoritmul Fibonacci recursiv a suprapus subprobleme., Există și alte tehnici precum programarea dinamică pentru a îmbunătăți astfel de algoritmi suprapuși.
Cu toate acestea, puțini algoritmi (de exemplu, merge sort, quick sort, etc…) au ca rezultat o complexitate optimă a timpului folosind recursivitate.
cazul de bază:
o cerință critică a funcțiilor recursive este punctul de terminare sau cazul de bază. Fiecare program recursiv trebuie să aibă caz de bază pentru a vă asigura că funcția se va termina. Lipsa cazului de bază duce la un comportament neașteptat.,
diferite moduri de a scrie funcții Recursive
funcția de asteptare în sine: (mod Direct)
cei mai mulți dintre noi conștient atleast două moduri diferite de a scrie programe recursive. Având în vedere mai jos este turnuri de cod Hanoi. Este un exemplu de apelare directă.

Output:

Move the disk 1 from S to DMove the disk 2 from S to AMove the disk 1 from D to AMove the disk 3 from S to DMove the disk 1 from A to SMove the disk 2 from A to DMove the disk 1 from S to D

complexitatea timpului TOH poate fi calculată prin formularea numărului de mișcări.
trebuie să mutăm primele discuri N-1 de la sursă la auxiliar și de la auxiliar la destinație, adică primele discuri N-1 necesită două mișcări. Încă o mișcare a ultimului disc de la sursă la destinație., Matematic poate fi definit recursiv.
MN = 2mn-1 + 1.
putem rezolva cu ușurință relația recursivă de mai sus (2n-1), Care este exponențială.
Recursivitate folosind apel funcție reciprocă: (mod Indirect)
apelare indirectă. Deși cel mai puțin pratical, o funcție poate apela o altă funcție care inturn numește funcția anterioară. În acest caz, ambele funcții ar trebui să aibă cazul de bază.
programare defensivă:
putem combina tehnicile de codificare defensivă cu recursivitate pentru funcționalitatea grațioasă a aplicației., De obicei, programarea recursivă nu este permisă în aplicațiile critice de siguranță, cum ar fi controalele de zbor, monitorizarea sănătății etc. Cu toate acestea, se poate utiliza o tehnică de numărare statică pentru a evita apelurile necontrolate (nu în sistemele critice de siguranță, pot fi utilizate în sisteme soft în timp real).adâncimea callDepth depinde de dimensiunea cadrului stivă funcție și dimensiunea maximă stivă.
Recursivitate folosind indicii de funcții: (mod Indirect)
recursivitatea poate fi implementată și cu indicii de funcții. Un exemplu este handler de semnal în sistemele de reclamații POSIX., În cazul în care handler determină să declanșeze același eveniment din cauza căruia handler fiind numit, funcția va reintra.