Rekurzija (kompjuterske nauke)

Rekurzija u kompjuterskoj nauci je metod gde rešenje problema zavisi od rešenja manjih slučajeva istog problema (za razliku od  iteracija). Ovaj pristup se može primeniti na mnoge vrste problema, a rekurzija je jedna od centralnih ideja kompjuterskih nauka.

Drvo stvoreno korišćenjem jezika Logo i oslanjajući se na rekurziju

"Snaga rekurzije očigledno leži u mogućnosti definisanja beskonačnog niza objekata do konačnog saopštenja. Na isti način, beskonačan broj izračunavanja može se opisati konačnom rekurzijom programa, čak i ako taj program ne sadrži izričita ponavljanja."

Većina računarskih programskih jezika podržavaju rekurziju dozvoljavajući funkciji da se pozove u tekstu programa. Neki  funkcionalni programski jezici  ne definišu nikakve petlje konstrukcije, ali oslanjaju se isključivo na rekurzije da stalno zovu kod. Rekurzivna teorija dokazuje da ovi strogo rekurzivni jezici su Tjuring - kompletni ; oni su računski jaki kao i Tjuring-kompletni imperativni jezici, što znači da oni mogu da reše istu vrstu problema kao i imperativni jezici čak i bez uobičajenih strukturnih komandi kao što su "dok" i "za".

Rekurzivne funkcije i algoritmi

Zajednička taktika kompjuterskog programiranja je da podelite problem u pod-probleme, istog tipa kao i original, rešiti ove pod-probleme, i kombinovati rezultate. Ovo se često naziva podeli pa vladaj metod; kada se kombinuje sa lukap tabelom koja sadrži rezultate rešavanja pod-problema (da bi se izbeglo njihovo rešavanje u više navrata i stvaranja dodatnog vremena izračunavanja), može se nazvati dinamično programiranje ili memoizacija.

Rekurzivnog funkcija definisana je sa jedan ili više baznih predmeta, što znači ulaz za koje funkcija daje rezultat trivijalno (bez ponavljanja), i jedan ili više rekurzivnih slučajeva, što znači ulaz za koji se program vraća (pozivi se) . Na primer, funkcija faktorijel fse može rekurzivno definisati jednačinama  0! = 1, a za sve n > 0, n! = n(n − 1)!. Nijedna jednačina po sebi predstavlja potpunu definiciju; prvi je osnovni slučaj, a drugi je rekurzivni slučaj. Budući da osnovni slučaj prekida lanac rekurzije, ponekad se takođe naziva i "završen slučaj".

Posao rekurzivnih slučajeva može se posmatrati kao razbijanje složenih ulaza u jednostavnije. U pravilno dizajniranoj rekurzivnoj funkciji, sa svakim rekurzivnim pozivom, problem ulaza mora biti pojednostavljen na takav način da na kraju osnovnog slučaja mora biti postignut. (Funkcije koje nisu namenjene da dovrše pod normalnim okolnostima, na primer, neki sistem i server procesi-su izuzetak). Zanemariti da se napiše osnovni slučaj, ili testirati za to pogrešno, može izazvati beskonačnu petlju.

Za neke funkcije (kao što je ona koja izračunava red za e = 1/0! + 1/1! + 1/2! + 1/3! + ...) ne postoji očigledan osnovni slučaj podrazumevan od strane ulaznih podataka; za ovo se može dodati parametar (kao što je broj uslova koji se dodaje, u našem primeru serije) da obezbedi 'zaustavljanje kriterijuma' koji uspostavlja osnovni slučaj. Takav primer je prirodno više tretirati ko-rekurzije, gde uzastopni termini u izlazu su parcijalne sume; ovo se može konvertovati u rekurzije koristeći indeksiranja parametara "izračunati n-ti termin (n-ti parcijalni zbir)".

Rekurzivni tipovi podataka

Mnogi kompjuterski programi  moraju obraditi ili generisati proizvoljno velike količine podataka. Rekurzija je jedina tehnika za predstavljanje podataka čiju tačnu veličinu programer ne zna: programer može navesti ove podatke sa samoreferentne definicije. Postoje dve vrste samoreferentnih definicija: induktivne i koinduktivne definicije.

Induktivno definisani podaci

Induktivno definisan rekurzivni podatak je onaj koji određuje kako izgraditi primer podataka. Na primer,  povezana lista se može definisati indutivno (korišćenjem Haskelove sintakse):

data ListOfStrings = EmptyList | Cons String ListOfStrings

Kod iznad određuje listu strigova da bude prazna, ili struktura koja sadrži string i listu stringova. Samo-referenca u definiciji dozvoljava izgradnju lista nekog (konačniog) broja stringova.

Drugi primer induktivne definicije je prirodan broj (ili pozitivni ceo broj):

Природан број је 1 или n+1, где је n природан број.

Slično, rekurzivne definicije se često koriste za modeliranje strukture izraza i izjava u programiramskom jeziku. Jezički dizajneri često izražavaju gramatiku u sintaksi kao što je  Bakus-Naurova forma; ovde je takva gramatika, za jednostavnim jezikom aritmetičkih izraza sa množenjem i sabiranjem:

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Ovo kaže da je izraz ili broj, proizvod dva izraza, ili zbir dva izraza. Rekurzija koja se odnosi na izraze u drugoj i trećoj linija, gramatika dozvoljava proizvoljno složene aritmetičke izraze kao što su   (5 * ((3 * 6) + 8)), sa više od jednog proizvoda ili zbira operacija u jednom izražavanju.

Koinduktivno definisani podaci i korekurzija

Koinduktivna definicija podataka je ona koja određuje operacije koje se mogu obavljati na delu podataka; tipično, samoreferencijalna koinduktivna definicija se koristi za strukture podataka beskonačne veličine.

Koinduktivna definicija bezbroj tokova stringova, neformalno, može da izgleda ovako:

Ток стрингова је објекат s тако да:
 глава(s) је стринг, а    
 реп(s) је ток стрингова.

Ovo je veoma slično induktivnoj definiciji liste stringova; razlika je u tome što ova defiicija određuje kako da pristupite sadržaju podataka strukture naime, preko aksesor funkcija глава i реп— i koji to sadržaji mogu biti, dok induktivna definicija određuje kako da kreirate strukturu i šta može biti kreirano od.

Korekurzija odnosi se na koindukciju, i može se koristiti za računanje posebnih slučajeva (eventualno) beskonačnih objekata.  Kao tehnika programiranja, koristi se najčešće u kontekstu lenjih programskih jezika, i može biti bolje da rekurzija kada željena veličina ili preciznost programa  izlaz je nepoznat. U takvim slučajevima program zahteva i definiciju za beskonačno veliki (ili beskonačno precizan) rezultat, i mehanizam za uzimanje konačnog dela tog rezultata. Problem izračunavanja prvih n prostih brojeva je onaj koji se može rešiti sa korekurzivnim programom.

Vrste rekurzije

Jednostruka i višestruka rekurzija

Rekurzija koja sadrži samo jednu referencu poznata je kao jednostruka rekurzija, dok rekurzija koja sadrži više samo-referenca je poznata kao višestruka rekurzija. Standardni primeri jednostruke rekurzije uključuju listu nošenja, kao što su linearno traženje, ili računanje faktorijela, dok standardni primeri višestruke rekurzije uključuju  obilazak stabla, kao što u dubini prvog traženja, ili računanja Fibonačijevog niza.

Jednostruka rekurzija je često mnogo efikasnija od višestruke rekurzije, i generalno se mogu zameniti iterativnim računanjem, radi u linearnom vremenu i zahteva stalni prostor. Višestruka recurzija, s druge strane, može da zahteva eksponencijalno vreme i prostor, i važnije rekurzivni, ne mogu da budu zamenjeni iteracijom bez eksplicitnog steka.

Višestruka rekurzija ponekad može biti konvertovana u jednostruku rekurziju (i, ako se želi, odatle u iteraciju). Na primer, dok računanje Fibonačijevog niza je višestruka iteracija, svaka vrednost zahteva dve prethodne vrednosti, to može da se izračuna jednostrukom rekurzijom korišćenjem dve uzastopne vrednosti kao parametre. Ovo je više prirodno uramljeno kao korekurzija, izgradnja od početnih vrednosti, praćenje na svakom koraku dve uzastopne vrednoste - vidi korekurzija: primeri. Sofisticirani primer koristi binarno stablo niti, koje omogućava iterativni obilazak stabla, pre nego višestruka rekurzija.

Indirektna rekurzija

Većina osnovnih primera rekurzije, i većina od primera koji su ovde, pokazuju direktnu rekurziju, u kojoj se funkcija zove. Indirektna rekurzija nastaje kada se funkcija ne zove samo po sebi već drugu funkciju da se zove (direktno ili indirektno). Na primer, ako  f poziva f , to je direktna rekurzija, ali ako f poziva g kojom se poziva f, onda je to indirektna rekurzija f . Lanci od tri ili više funkcija su moguće; na primer, funkcija 1 poziva funkciju 2, funkcija 2 poziva funkciju 3, i funkcija 3 poziva funkciju 1 ponovo.

Indirektna rekurzija se takođe naziva i  uzajamna rekurzija, što je više simetrična terminu, mada to je jednostavno razlika naglaska, a ne razlikuje pojam. To je, ako f poziva g, a zatim g poziva f, što zauzvrat opet poziva g, sa tačke gledišta f , f je posredno rekurzija, dok sa tačke gledišta  g, to je indirektna rekurzija, dok sa tačke gledišta oba f i g je višestruka rekurzija jedna na druge. Slično set od tri ili više funkcija koje pozivaju jedni druge može se nazvati skup međusobno rekurzivnih funkcija.

Anonimna rekurzija

Rekurzija se obično vrši pozivanjem funkcija po imenu. Međutim, rekurzija može da se uradi preko implicitnog pozivanja funkcija zasnovana na trenutnom kontekstu, što je posebno korisno anonimne funkcije, i poznat je kao  anonimna rekurzija.

Strukturna u odnosu na generativne rekurzije

Neki autori klasifikuju rekurziju kao  "strukturnu" ili "generativnu". Razlika se odnosi na koji rekurzivni postupak dobije podatke na koji radi, i kako se obrađuju te podatke:

[Funkcije koje konzumiraju strukturirani podatak] obično razlaže svoje argumente u svoje neposredne strukturne komponente, a zatim obrađuje te komponente. Ako jedan od neposrednih komponenti pripada istoj klasi podataka kao ulaz, funkcija je rekurzivna. Iz tog razloga, govorimo o ovim funkcijama kao (strukturno) rekurzivnim funkcijama.

Dakle, definisanje karakteristika strukturalno rekurzivnih funkcija je da argument za svaki rekurzivni poziv je sadržaj polja originalnog ulaza. Strukturna rekurzija obuhvata skoro sve obilaske stabla, uključujući XML prerade, binarnog stabla kreiranja i pretrage, itd. Uzimajući u obzir algebarsku strukturu prirodnih brojeva (koji je, prirodan broj je ili nula ili naslednik prirodnog broja), funkcija kao faktorijel se takođe može smatrati strukturnom rekurzijom.

Generativna rekurzija  je alternativa. Mnogi poznati rekurzivni algoritmi generišu potpuno novi podatak iz datih podataka i vraćamo na nju. HtDP (Kako osmisliti program) se odnosi na ovu vrstu kao generativne rekurzije. Primeri generativnih rekurzija uključuju Euklidov algoritam, kviksort, binarna pretraga, sortiranje sa spajanjem, Njutnova metoda, fraktal, i prilagodljiva integracija.

Ova razlika je važna za dokazivanje prestanka funkcije.  

• Sve strukturno rekurzivne funkcije na konačne (induktivno definisano) strukture podataka se lako može pokazati da dovrši, preko strukturne indukcije: intuitivno, svaki rekurzivni poziv dobija manji deo ulaznih podataka, dok se ne postigne osnovni slučaj.
• Generativne rekurzivne funkcije, nasuprot tome, ne moraju hraniti manji ulaz svojim rekurzivnim pozivima, tako da govoriti o njihovom raskidu nije nužno tako jednostavno, i izbegavanje beskonačne petlje zahteva veću brigu. Ove generativne rekurzivne funkcije često se mogu tumačiti kao korekurzivne funkcije - svaki korak generiše nove podatke, kao što su sukcesivna aproksimacija u Njutnovoj metodi - i dovršetak ove korekurzije zahteva  da podaci na kraju zadovolje neke uslove, nije garantovano.
• Što se tiče varijanti petlje, strukturna rekurzija je kada postoji očigledna varijanta petlje, odnosno veličina ili kompleksnost, koja počinje konačano i smanjuje se na svakom rekurzivnom koraku. 
• Nasuprot tome, generativna rekurzija je kad ne postoji takva očigledna varijanta petlje, i prestanak zavisi od funkcije, kao što je  "greška približavanja", to ne mora da se smanji na nulu, i na taj način raskid nije zagarantovan bez daljih analiza.

Rekurzivni programi

Rekurzivne procedure

Faktorijel

Klasičan primer rekurzivne procedure je funkcija korišćena za računanje  faktorijela prirodnog broja:

$\operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}$

Pseukod (rekurzivno:
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ] end factorial

Funkcija se može zapisati i kao rekurzivni odnos:

$b_{n}=nb_{n-1}$

$b_{0}=1$

Ova procena ponavljanja odnosa pokazuje računanje koje će se obaviti u proceni Pseudokoda iznad:

Izračunavanje ponavljanja odnosa za n = 4:
b4 = 4 * b3 = 4 * (3 * b2) = 4 * (3 * (2 * b1)) = 4 * (3 * (2 * (1 * b0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

Ova funkcija faktorijela može biti opisana bez upotrebe rekurzije tako što koriste tipične petlje konstrukcije koje se nalaze u imperativnim programskim jezicima:

Pseukod (iterativno)
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. create new variable called running_total with a value of 1 2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop 3. return running_total end factorial

Imperativ kod iznad je ekvivalent za ovu matematičku definiciju koristeći akumulacionu romenljivu t:

${\begin{array}{rcl}\operatorname {fact} (n)&=&\operatorname {fact_{acc}} (n,1)\\\operatorname {fact_{acc}} (n,t)&=&{\begin{cases}t&{\mbox{if }}n=0\\\operatorname {fact_{acc}} (n-1,nt)&{\mbox{if }}n>0\\\end{cases}}\end{array}}$

Definicija iznad direktno prevodi  funkcionalnim programskim jezikom kao što su Šeme;  ovo je primer iteracije koja se sprovodi rekurzivno.

Najveći zajednički delilac

Euklidov algoritam, koji računa najveći zajednički delilac dva cela broja, može se zapisati rekurzivno.

Definicija funkcije:

$\gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}$

Pseukod (rekurzivno):
function gcd is: input: integer x, integer y such that x > 0 and y >= 0 1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ] end gcd

Ponavljanje odnosa za najveći zajednički delilac $x\%y$ izražava ostatak od $x/y$:

$\gcd(x,y)=\gcd(y,x\%y)$ if $y\neq 0$

$\gcd(x,0)=x$

Izračunavanje ponavljanja odnosa za x = 27 i y = 9:
gcd(27, 9) = gcd(9, 27% 9) = gcd(9, 0) = 9
Izračunavanje ponavljanja odnosa za x = 111 i           y = 259:
gcd(111, 259) = gcd(259, 111% 259) = gcd(259, 111) = gcd(111, 259% 111) = gcd(111, 37) = gcd(37, 111% 37) = gcd(37, 0) = 37

Rekurzivni program gore je rep-rekurzije; to je ekvivalentno iterativni algoritam i računanje prikazano gore pokazuje korake procene da će da se obavljaju na jeziku koji eliminiše zadnje pozive. Ispod je verzija istog algoritma koristeći eksplicitnu iteraciju, pogodan za jezik koji ne otkloni zadnje pozive. Po održavanju svojih stanja u potpunosti. promenljive x i y i korišćenje konstruktivne petlje, program izbegava donošenje rekurzivnih poziva i raste poziv steka.

Pseukod (iterativno):
function gcd is: input: integer x, integer y such that x >= y and y >= 0 1. create new variable called remainder 2. begin loop 1. if y is zero, exit loop 2. set remainder to the remainder of x/y 3. set x to y 4. set y to remainder 5. repeat loop 3. return x end gcd

Iterativni algoritam zahteva privremenu promenljivu, pa čak i dato znanje Euklidovog algoritma je teže da razumeju proces prostom kontrolom, iako su dva algoritma veoma slična u svojim koracima.

Hanojska kula

Hanoi kula

Hanojska kula je matematička zagonetka čije rešenje ilustruje rekurziju. Postoje tri štapa koji mogu da čuvaju gomilu diskova različitih prečnika. Veći diska nikad ne može biti složen na vrhu manjeg. Počevši sa n diskovima na jednom štapu, oni moraju biti premešteni na drugi štap jedan po jedan. Koji je najmanji broj koraka da biste pomerili sve?

Definicija funkcije:

$\operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}$

Ponavljanje odnosa za hanoi:

$h_{n}=2h_{n-1}+1$

$h_{1}=1$

Izračunavanje ponavljanja odnosa za n = 4:
hanoi(4) = 2*hanoi(3) + 1 = 2*(2*hanoi(2) + 1) + 1 = 2*(2*(2*hanoi(1) + 1) + 1) + 1 = 2*(2*(2*1 + 1) + 1) + 1 = 2*(2*(3) + 1) + 1 = 2*(7) + 1 = 15

Primer implementacije:

Pseukod (rekurzivno):
function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi

Iako nisu svi rekurzivne funkcije imaju eksplicitan rešenje, Hanojska kula sekvenca može da se svede na eksplicitne formule .

Eksplicitna formula za Hanoi kulu:
h1 = 1 = 21 - 1 h2 = 3 = 2² - 1 h3 = 7 = 2³ - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1 In general: hn = 2n - 1, for all n >= 1

Binarna pretraga

Binarna pretraga je metod u potrazi  sortiranog niza za jedan elementa smanjenjem niz na pola sa svakim rekurzivnim prolazom. Trik je da izaberete središte u blizini centra niza, uporedimo podatke u tom trenutku sa podacima koji se pretresaju i onda odgovor na jedan od tri moguća stanja: podaci se nalaze na sredini, podaci na sredini veći nego što su se podaci tražili, ili su podaci na sredini manji od podataka koji se traže.

Rekurzija se koristi u ovom algoritmu, jer sa svakim prolaskom kroz novi niz je stvorio sečenje starog na pola. Binarna pretraga postupka je zatim pozvana rekurzivno, ovaj put na novom (i manjem) nizu. Tipično veličina nizova se podešava manipulisanjem početnih i krajnjih indeksa. Algoritam pokazuje logaritamski redosled rasta, jer u suštini deli domen problema na pola sa svakom prolazu.

Primer implementacije binarne pretrage u C:

 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division

    //Stop condition.
    if (start > end)
       return -1;
    else if (data[mid] == toFind)        //Found?
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }

Rekurzija strukture podataka (strukturna rekurzija)

Važna primena rekurzije u kompjutersoj nauci je u definisanju dinamičke strukture podataka kao što su  liste i stabla. Rekurzivne strukture podataka mogu dinamički rasti do teoretski beskonačne veličine kao odgovor na početne zahteve; nasuprot tome, veličina statičkog niza mora biti postavljena na kompajliranje. Rekurzivni algoritmi su posebno odgovarajući kada se osnovni problem ili podatak koji se tretira,  definisani u rekurzivnim uslovima.

Primeri u ovom odeljku ilustruju ono što je poznato kao "strukturne rekurzije". Ovaj termin se odnosi na činjenicu da  rekurzivni postupci deluju na podatak koji je rekurzivno definisan.

Dokle god programer proizilazi obrazac iz definicije podataka, funkcija zapošljava strukturnu rekurziju. To jest rekurzija u funkcijskom telu troši neposredni deo date vrednosti.

Povezana lista

Ispod je C definicija povezane strukture liste čvorova. Obaveštenje posebno kako je čvor definisan u smislu sebi. "Sledeći" element strukturnog čvora je pokazivač na drugi strukturni čvor, efektivno stvarajući tip liste.

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Zato što je struct node struktura podataka  rekurzivno se definišu procedure koje posluju na njemu, mogu da se realizuju kao prirodno rekurzivne procedure. Postupak  list_print  definisan u daljem tekstu šetnja kroz listu dok je lista prazna (tj pokazivač liste  ima vrednost NULL)..

void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}

Binara stabla

Ispod je jednostavna definicija za binarno stablo čvora. Kao čvorište za povezane liste, što je definisano u smislu sebe, rekurzivno. Postoje dva samoreferencijalna pokazivača: levo (pokazujući na levo pod-stablo) i pravo (pokazujući nadesno pod-stablo).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

Operacije na stablu mogu da se implementiraju korišćenjem rekurzija. Imajte na umu da, jer postoje dve samoreferencijalna pokazivača (levo i desno), operacije stabla mogu zahtevati dva rekurzivna poziva:

// Test if tree_node contains i; return 1 if so, 0 if not.

int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}

Najviše dva rekurzivna poziva će biti napravljena za svaki dati poziv na tree_contains kako je gore definisano.

// Inorder traversal:
void tree_print(struct node *tree_node) {
        if (tree_node != NULL) {                  // base case
                tree_print(tree_node->left);      // go left
                printf("%d ", tree_node->data);   // print the integer followed by a space
                tree_print(tree_node->right);     // go right
        }
}

Gornji primer ilustruje obilazak stavla binarnog drveta. Binarno stablo pretrage je specijalni slučaj binarnog drveta gde su elementi podataka u svakom čvoru u redu.

Filesystem traversal

Od broja datoteka  fajlssistema može da varira, rekurzija je jedini praktičan način da prolaze i tako nabraja njegov sadržaj. . Prelaskom fajlsistem je veoma sličan onom iz obilaska stabla, pa su koncepti iza obilaska stabla važe za prelaženje fajlsistema. Preciznije, kod ispod će biti primer obilazak stabla na fajlsistemu..

import java.io.*;

public class FileSystem {

	public static void main (String [] args) {
		traverse ();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse () {
		File [] fs = File.listRoots ();
		for (int i = 0; i < fs.length; i++) {
			if (fs[i].isDirectory () && fs[i].canRead ()) {
				rtraverse (fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse (File fd) {
		File [] fss = fd.listFiles ();

		for (int i = 0; i < fss.length; i++) {
			System.out.println (fss[i]);
			if (fss[i].isDirectory () && fss[i].canRead ()) {
				rtraverse (fss[i]);
			}
		}
	}

}

Ovaj kod spaja linije, barem donekle, između rekurzije i ponavljanja. To je, u suštini, rekurzivna implementacija, što je najbolji način za prelazak  fajls istema. Takođe je primer direktne i indirektne rekurzije. Metod "rtraverse" je čisto direktan primer; metod  "traverse" je indirektan, kojom se poziva "rtraverse." Ovaj primer treba "osnovni slučaj" scenario s obzirom na činjenicu da će uvek biti neki fiksni broj datoteka ili direktorijuma u ​​datom fajl sistemu.

Pitanja implementacije

Zapravo implementacije, više nego čista rekurzivnoa funkcija (jedinstvena provera za osnovni slučaj, inače rekurzivni korak), veliki broj modifikacija može biti, u svrhu jasnoće i efikasnosti. Ovo uključuje:

• Omot funkcija (na vrhu)
• Kratkim spajanjem osnovnog slučaja, zvani "ruka- dužina rekurzije" (pri dnu) 
• Hibrid algoritma (na dnu) - prebacivanje na drugi algoritam dovoljno malih podataka

Na osnovu elegancijom, konfekcija funkcije se uglavnom odobravaju, dok je kratak spoj osnovnog slučaja nije poželjan, posebno u akademskim krugovima. Hibridni algoritmi se često koriste za efikasnost, smanjenje režijske troškove rekurzije u malim slučajevima ruka- dužine rekurzije je poseban slučaj za ovo.

Omot funkcija

Omot funkcija je funkcija koja se zove direktno, ali ne rekurzivno, poziva se posebna pomoćna funkcija koja zapravo radi o rekurziji.  

Omot funkcija može da se koriste za proveru parametra (tako rekurzivna funkcija preskače njih ), vrši inicijalizaciju (izdvojiti memoriju, pokrenite promenljive), osebno za pomoćne promenljive kao što su "nivo rekurzije" ili delimične proračune za memoizaciju, ručne izuzetake i grešake. U jezicima koji podržavaju umetnute funkcije, pomoćna funkcija može biti smeštena unutar omot funkcije i koriste zajednički obim. U odsustvu zainteresovane funkcije, pomoćne funkcije su unutar posebne funkcije, ako je moguće privatno (kao što se ne zove direktno), a informacije se dele sa omot funkcije pomoću prelazne reference.  

Kratko spajanje osnovnog slučaja

Kratko spajanje osnovnog slučaja, poznatije kao ruka- dužina rekurzije, sastoji se od provere osnovnog slučaja pre nego što rekurzivno pozove – odnosno provera da li sledeći poziv će biti osnova slučaja, umesto poziva, a zatim proverava za osnovni slučaj. Kratki spoj je posebno učinio za efikasnost razloga, da se izbegne iznad glave jednog poziva funkcije koja se odmah vraća.. Imajte na umu da, pošto osnovni slučaj već proverava (neposredno pre rekurzivnog koraka), ne treba da bude proveren odvojeno, ali ne treba da se koristi omot funkcija u slučaju kada je ukupna rekurzija počinje sa osnovnim slučajem. Na primer, u faktorijel funkciji, pravilni osnovni slučaj je  0! = 1, dok odmah vraća 1 za 1! za kratki spoj, i može propustiti 0; ovo se može ublažiti i u omot funkciji.

Kratki spoj je pre svega zabrinutost kada su naišli na veliki broj baza slučajeva, kao što su Null pokazivač na stablo, koje može biti linearno u broju poziva funkcija, pa značajne uštede za O(n) algoritma; ovo je prikazano ispod za dubinsko prvog pretresa. Kratkog spoja na drvetu odgovara razmatra list (ne prazna čvor bez dece) kao osnovnog slučaja, nego s obzirom prazan čvor kao osnovnog slučaja. Ako postoji samo jedan osnovni slučaj, kao što su u izračunavanju faktorijela, kratkog spoja obezbeđuje samo O (1) uštede.  

Konceptualno, kratak spoj može biti u slučaju da ima istu bazu, i rekruzivni korak samo proveru osnovnog slučaja pred rekurzije ili se može smatrati da imaju drugačiju bazu slučaja ( jedan korak se uklanja iz standardnog osnovnog slučaja ), i mnogo složeniji rekurzivni korak naime toga proverite vazi li onda rekurzija, kao i da s' obzirom na listanje čvorova umesto nultog čvora kao osnova predmeta u drvetu. Zbog kratkog spoja ima više komplikovanih tokova u poređenju sa jasnim razdvajanjem osnovnog slučaja i rekurzivnog koraka u standardima rekurzije i to se često smatra sporim stilom.naročito u akademskim krugovima.

Dubina prve pretrage

Osnovni primer kratkog spoja dat je u dubini prve pretrage (DFS) binarnog stabla; vidi binarni deo stabla za standardne rekurzivne diskusije.

Standardni rekurzivni algoritam  DFS je:

• osnovni slučaj: ako je trenutni čvor null vrati netačno
• rekurzivni korak: inače, proverite vrednost tekućeg čvora, vratite tačno ako je pogodak, u suprotnom rekurzija o deci.

U kratkom spoja, ovo je umesto toga:

• proveriti vrednost tekućeg čvora i vrati tačo ako je pogodak
• inače ako ne null onda rekurzija. 

Što se tiče standardnih koraka, ovo pokreće proveru baznog slučaja pred rekurzivnim korakom. Alternativno, oni se mogu smatrati drugačijim oblikom osnovnog slučaja i rekurzivnim korakom. Imajte na umu da ovo zahteva omot funkciju za rukovanje slučaj kada je samo stablo je prazno (koren čvora je null).

U slučaju savršenog binarog drveta visine h, gde je 2^h+1−1 čvor i 2^h+1 null pokazivači kao deca (2 za svaku od 2^h lišća), tako kratkog spoja smanjuje broj poziva funkcija na pola u najgorem slučaju.

U C, standardni rekurzivni algoritam može biti implementiran kao:

bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}

Algoritam kratkog spoja može biti implementiran kao:

// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}

Obratite pažnju na upotrebu kratkog spoja evaluacije boolean && (I) operatori, tako da rekurzivni poziv je napravljen samo ako je čvor važeći (ne null). Imajte na umu da dok je prvi termin  I predstavlja pokazivač na čvor, drugi termin je int, tako da je ukupan izraz procenjuje na bool. Ovo je uobičajena idiom u rekurzivnom kratkom spoju. Ovo je pored evaluacije kratkog spoja na Boolean || (ILI) operater, da samo proverite pravo dete ako je levo dete ne uspe. U stvari, cela kontrola toka od ovih funkcija može da se zameni sa jednim bulovom ekspresijom u saopštenju povratka, ali čitljivost pati bez korisne efikasnosti.

Hibridni algoritam

Rekurzivne algoritmi su često neefikasni za male podatke, zbog grafoskop ponovljenih poziva funkcija i povratak. Iz tog razloga efikasne implementacije algoritama rekurzivnih često počinju sa rekurzivnom algoritma, ali onda prebacite na drugi algoritam kada je ulaz postane mali.. Važan primer je spajanje vrsta, koja se često realizuje prelaskom na ne-rekurzivno ubacivanje vrsta  kada se podaci dovoljno mali, kao u popločanoj vrsti spajanja. Hibridna rekurzija algoritma često može biti dalje rafinirana, kao u Timsortu, izvedene iz hibridnog stapanja metodu / umetanja vrste

Rekurzija u odnosu iteracija

Rekurzija i iteracija su podjednako izražajna: rekurzija može biti zamenjena iteracijom sa eksplicitnim stekom, a iteracija može biti zamenjena rep rekurzijom. Koji pristup je poželjan zavisi od problema koji se razmatra i jezika koji se koristi. U imperativnom programiranju, iteracija je poželjna, posebno za jednostavne rekurzije, jer izbegava iznad funkcije poziva i upravljanje  stekom, ali rekurzije se uglavnom koriste za višestruke rekurzije. Nasuprot tome, u funkcionalnom jeziku rekurzija je poželjna, sa repa rekurzije optimizacija dovodi do malo iznad glave, a ponekad eksplicitna iteracija nije dostupna.

Uporedite šablone za izračunavanje x_n definisano sa x_n = f(n, x_n-1) od x_base:

function recursive(n) if n==base return xbase else return f(n, recursive(n-1))

function iterative(n) x = xbase for i = n downto base x = f(i, x) return x

Za imperativni jezik plafon je definisati funkciju, za funkcionalni jezik plafon je da se definiše akumulator promenljive x.

Na primer, faktorijalna funkcija može da se iterativno implementira u C dodelom na indeks petlje promenljive i akumulator promenljive, umesto da prolazi argumente i vraća vrednosti od rekurzije:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Izražajna moć

Većina programskih jezika u upotrebi danas omogućavaju direktnu specifikaciju rekurzivnih funkcija i procedura. Kada se zove takva funkcija, programi runtime environment prati raznih instanci funkcije (često koristeći poziv steka, iako mogu da se koriste druge metode). Svaka rekurzivna funkcija može da se transformiše u iterativnu funkciju zamenom rekurzivnog poziva sa iterativnim kontrolnim konstrukcijama  i simulira poziv steka sa steka eksplicitno upravlja programom.

S druge strane, sve iterativne funkcije i procedure koje mogu biti ocenjene od strane računara (pogledajte Tjuringova potpunost) mogu se izraziti u smislu rekurzivnih funkcija; iterativne kontrole konstrukcije, kao što su while petlja i do petlja su rutinski prepisani u rekurzivnom obliku funkcionalog jezika. Međutim, u praksi to prepisivanje zavisi od rep poziva eliminacija

, što nije karakteristika svih jezika. C, Java, i Pajton su značajni jezici na kojim svi pozivi funkcije, uključujući krajnje pozive, jer stek raspodela ne bi došla uz korišćenje petlje konstrukcija; na tim jezicima, radni ponavljački program prepisan u rekurzivnoj formi može premašiti pozivni stek.

Problemi sa performansama

U jezicima (kao što su C i Java) koji vole više iterativne petlje konstrukcije, obično postoji značajan prostor i vreme i troškovi povezani sa rekurzivnim programima, zbog dodatne potrebne za upravljanje bibliotekom i relativna sporost poziva funkcija; u funkcijalnim jezicima, funkcija poziva (naročito krajnji poziv) je obično veoma brz rad, a razlika je obično manje primetna.

Kao konkretan primer, razlika u performansama između rekurzivnih i učestali implementacija na "faktorijel" primeru iznad zavisi visoko na kompajler koristi. U jezicima gde su konstrukcije petlje omiljene, iterativnih verzija može biti onoliko koliko nekoliko redova veličine brže od rekurzivne. U funkcionalnim jezicima, ukupna vremenska razlika od dve implementacije može biti zanemarljiva; u stvari, troškovi umnožavanja veći broj prvo nego manji broj (koja iterativna verzija data ovde dešava da uradi) mogla da prevlada u bilo koje vreme sačuvane izborom iteracija.

Stek prostor

U nekim programskim jezicima, stek prostor dostupan na temi je mnogo manje od raspoloživog prostora u gomili, a rekurzivni algoritmi imaju tendenciju da zahtevaju više prostora nego stek iterativni algoritam. Shodno tome, ovi jezici ponekad stave limit na dubinu rekurzije da se izbegne stek prelivanja; Pajton je jedan takav jezik. Obratite pažnju na upozorenje ispod o posebnom slučaju rep rekurzije.

Višestruki rekurzivni problemi

Višestruki rekurzivni problemi su inherentno rekurzivni, zbog ranijeg stanja moraju da prate. Jedan primer je obilazak stabla kao u pretraga u dubinu; kontrast sa liste i linearne pretrage u listi, što je jednostruka rekurzija i tako prirodno iterativna.

Drugi primeri uključuju podeli pa vladaj algoritam kao što su Kviksort, i funkcije kao što su Akermanova funkcija. Sve ove algoritme možemo iterativno implementirati, uz pomoć eksplicitnog steka, ali programerski trud koji je uključen u upravljanju steka i složenosti dobijenog programa, će verovatno nadmašiti sve prednosti iterativnog rešenja.

Funkcije repne rekurzije

Funkcije repne rekurzije su funkcije u kojoj svi rekurzivni pozivi su rep pozivi i stoga ne nagomilavaju nikakve odložene operacije. Na primer, gcd funkcija (pokazano opet ispod ) je repno rekurzivna. Nasuprot tome, faktorijel funkcija (takođe ispod) nije rep-rekurzivna; jer je njegov rekurzivan poziv nije u poziciji repa, temelji se odložena množenja operacije koje se mora izvršiti nakon finalni rekurzivi poziv završi.  Sa kompajlerom ili tumačem koji tretira rep-rekurzivni poziv kao skokove, pre nego poziv funkcije, rep-rekurzivna funkcija kao što je gcd  će se izvršiti pomoću stalnog prostora. Tako se program suštinski ponavlja, jednako koristeći imperativne kontrolne strukture jezika kao što su "for" i "while" petlje.

Tail recursion:	Augmenting recursion:
//INPUT: Integers x, y such that x >= y and y > 0 int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); }	//INPUT: n is an Integer such that n >= 0 int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); }

Značaj rep rekurzija je da prilikom donošenja rep-recurzivnog poziva (ili bilo kog rep poziv), pozivalac vraća položaj ne mora da se čuva na pozivnom steku; kada rekurzivni poziv vrati, one će se granati direktno na prethodno sačuvanu poziciju povratka. Dakle, na jezicima koje priznaju ovu imovinu zadnjih poziva, rep rekurzije štedi prostor i vreme.  

Redosled izvršavanja

U jednostavnom slučaju funkcija koja je sebe pozivala samo jednom, instrukcije postavljaju pred rekurzivni poziv se izvršava jednom rekurzivnom pred bilo kojim od uputstava postavljenih posle rekurzivnog poziva. Ovi drugi su u više navrata izvršena nakon što je maksimalna rekurzija postignuta. Razmotrimo ovaj primer:

Funkcija 1

void recursiveFunction(int num) {
   printf("%d\n", num);
   if (num < 4)
      recursiveFunction(num + 1);
}

Funkcija 2 sa zamenjenim linijama

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   printf("%d\n", num);
}

Vremenska efikasnost rekurzivnog algoritma

Vremenska efikasnost rekurzivnog algoritma može se izraziti u odnosu na  vraćanje odnosa Veliko O. Oni mogu (obično) se pojednostaviti u jedan Big-Oh termin.

Pravilo prečice  (majstor teorema)

Ako je vreme-kompleksnost funkcije je u vidu

$T(n)=a\cdot T(n/b)+O(n^{k})$

Zatim Veliko-O vremenske kompleksnosti je ovako:

• If $a>b^{k}$, onda vremenska kompleksnost je

$O(n^{\log _{b}a})$

• If $a=b^{k}$, onda vremenska kompleksnost je $O(n^{k}\cdot \log n)$
• If $a<b^{k}$, onda vremenska kompleksnost je $O(n^{k})$

gde $a$ predstavlja broj rekurzivnih poziva na svakom nivou rekurzije, $b$ predstavlja po onome faktor manji ulaz za sledeći nivo rekurzije (tj broj komada podelimo problem u), i $n^{k}$ predstavlja rad funkcija ne nezavisna od bilo koje rekurzije (npr podela, kombinujući) na svakom nivou rekurzije.

Vidi još

• Funkcionalno programiranje
• Hijerarhijski i rekurzivni SQL upiti
• Kline-Rozer paradoks
• Otvorena rekurzija
• Rekurzija
• Kriva Sjerpinskog

Rekurzivne funkcije

• McCarthy 91 funkcija
• μ-rekurzivna funkcija
• Primitivna rekurzivna funkcija
• Tak (funkcija)

Knjige

• Structure and Interpretation of Computer Programs
• Walls and Mirrors

Literatura

• Felleisen, Matthias (2002). „Developing Interactive Web Programs”. Ur.: Jeuring, Johan. Advanced Functional Programming: 4th International School. Oxford, UK: Springer. str. 108. 
• Drozdek, Adam (2012). Data Structures and Algorithms in C++. Cengage Learning. str. 197. ISBN 978-1-285-41501-7. 
• Hetland, Magnus Lie (2010). Python Algorithms: Mastering Basic Algorithms in the Python Language. Apress. str. 79. ISBN 978-1-4302-3238-4. 

Članci

• Dijkstra, Edsger W. (1960). „Recursive Programming”. Numerische Mathematik 2 (1): 312—318. doi:10.1007/BF01386232. 

Spoljašnje veze

• Jonathan Bartlett: "Mastering Recursive Programming"
• David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"
• Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"
• Owen L. Astrachan: "Big-Oh for Recursive Functions: Recurrence Relations"