Recursión (ciències de computació)

Per a un tractament més general dels fenomens recursivos, vore l'artícul de Recursión.

Recursión és, en ciències de la computació, una forma d'atallar i solucionar problemes. De fet, recursión és una de les idees centrals de ciència de computació. Resoldre un problema per mig de recursión significa que la solució depén de les solucions de chicotetes instàncies del mateix problema.

La majoria dels llenguages de programació donen soport a la recursión permetent a una funció cridar-se a sí mateixa des del text del programa. Els llenguages imperatius definixen les estructures de loops com while i for que són usades per a realisar tasques repetitives. Alguns llenguages de programació funcionals no definixen estructures de loops sino que possibiliten la recursión cridant còdic de forma repetitiva. La teoria de la computabilidad ha demostrat que estos dos tipos de llenguages són matemàticament equivalents, és dir que poden resoldre els mateixos tipos de problemes, encara que els llenguages funcionals carixquen de les típiques estructures while i for.

Archiu:RecursiveTree. caps block 0

Arbre basat en la recursión creat usant el llenguage de programació Logo.

Algoritmes recursivos

Generalment, si la primera cridada al subprograma es planteja sobre un problema de tamany o orde N, cada nova eixecució recurrent del mateix es plantejarà sobre problemes, d'igual naturalea que l'original, pero d'un tamany menor que N. D'esta forma, en anar reduint progressivament la complexitat del problema que resoldre, aplegarà un moment en que la seua resolució siga més o menys trivial (o, a lo manco, suficientment manejable com per a resoldre-ho de forma no recursiva). En eixa situació direm que estem davant un cas base de la recursividad.

Les claus per a construir un subprograma recurrent són:

• Cada cridada recurrent es deuria definir sobre un problema de menor complexitat (alguna cosa més fàcil de resoldre).
• Ha d'existir a lo manco un cas base per a evitar que la recurrencia siga infinita.

És freqüent que els algoritmes recurrents siguen més ineficientes en temps que els iterativos encara que solen ser molt més breus en espai.

Un método freqüent per a simplificar és dividir un problema en problemes derivats de menor tamany del mateix tipo. Açò es coneix com dialecting. Com a tècnica de programació es denomina dividix i venceràs i és peça fonamental per al disseny de molts algoritmes d'importància, aixina com part essencial de la programació dinàmica.

Virtualment tots els llenguages de programació moderns permeten l'especificació directa de funcions i subrutinas recursivas. Quan es diu una funció d'este tipo, l'ordenador, per a la majoria dels llenguages en casi totes les arquitectura basades en una pila (stack) o en l'implementació del llenguage, du el conte de les distintes instàncies de la funció, en numeroses arquitectura per mig de l'us d'un call stack, encara que no de forma exclusiva. A l'inversa, tota funció recursiva pot transformar-se en una funció iterativa usant un stack.

La majoria (encara que no totes) de les funcions i subrutina que poden ser evaluades per un ordenador, poden expressar-se en térmens d'una funció recursiva (sense tindre que utilisar una iteración pura); a l'inversa, qualsevol funció recursiva pot expressar-se en térmens d'una iteración pura, ya que la recursión és, de per sí, també iterativa. Per a evaluar una funció per mig de la recursión, té que definir-se com una funció de sí mateixa (ej. el factor n! = n * (n - 1)! , a on 0! es definix com 1). Resulta evident que no totes les evaluacions de funcions es presten a un acostament recursivo. Per lo general, totes les funcions finitas poden descriure's directament de forma recursiva; les funcions infinites (ej. les séries d'i = 1/1! + 2/2! + 3/3!...) necessiten un criteri extra per a detindre's, ej. el número de iteraciones, o el número de dígits significatius, en cas contrari una iteración recursiva resultaria en un bucle infinit.

A modo d'ilustració: Si es troba una paraula desconeguda en un llibre, el llector pot anotar la pàgina actual en un paper i posar-ho en una pila (fins a llavors buida). El llector consulta la paraula en un atre artícul i, de nou, descobrix una atra paraula desconeguda, l'anota i la posa en la pila, i aixina successivament. Aplega un moment que el llector llig un artícul que a on totes les paraules són conegudes. El llector retorna llavors a l'última pàgina i contínua la llectura des d'ahí, i aixina fins que es retira l'última nota de la pila retornant llavors al llibre original. Este modus operandi és recursivo.

Alguns llenguages dissenyats para programació llògica i programació funcional oferixen la recursión com l'únic mig de repetició directa disponible per al programador. Estos llenguages solen conseguir que la recursión de coa siga tan eficient com la iteración, permetent als programadors expressar atres estructures repetitives (tals com map i for de scheme) en térmens de recursión.

La recursión està profundament ancorada en la teoria de computació, en l'equivalència teòrica de funció microrecursiva i màquines de Turing en la fonamentació d'idees sobre l'universalitat de l'ordenador modern.

Programació recursiva

Crear una subrutina recursiva requerix principalment la definició d'un "case base", i llavors definir regles per a subdividir casos més complexos en el cas base. Per a una subrutina recursiva és essencial que en cada cridada recursiva, el problema es reduïxca de manera que al final aplegue al case base.

Alguns experts classifiquen la recursión com "generativa" o be "estructural". La distinció es fa segons d'a on provinguen les senyes en els que treballa la subrutina. Si les senyes procedixen d'una estructura de senyes similar a una llista, llavors la subrutina és "estructuralment recursiva"; en cas contrari, és "generativamente recursiva".

Eixemples de subrutina definides recursivamente (recursión generativa)

Factorial

Un eixemple clàssic d'una subrutina recursiva és la funció usada per a calcular el factorial d'un sancer.

Definició de la funció:

$\mathrm{fact}(n)=\{\begin{array}{cccc}si& n=0& ⟶& 1\\ si& n>0& ⟶& n\cdot \mathrm{fact}(n-1)\end{array}$

Pseudocódigo (recursivo):
funció factorial: input: entere n de manera que n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n és 0, return 1 2. else, return [ n × factorial(n-1) ] end factorial

Una relació recurrent és una equació que relaciona térmens posteriors en la seqüència en térmens previs.

Relació recurrent d'un factorial:

$b_n=n{b}_{n-1}$

$b_0=1$

Computant la relació recurrent per a 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

Esta funció factorial també pot descriure's sense usar recursión fent us de típiques estructures de bucle que es troben en llenguages de programació imperatius:

Pseudocódigo (iterativo):
funció factorial és: input: entere n de manera que n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. crear una variable nova cridada running_total en un valor = 1 2. begin loop 1. si n és = 0, eixir del loop 2. canviar running_total a (running_total × n) 3. decrementar n 4. repetir el loop 3. return running_total end factorial

El llenguage de programació scheme és, no obstant, un llenguage de programació funcional i no definix estructures de loops de qualsevol tipo. Es basa únicament en la recursión per a eixecutar tot tipo de loops. Ya que scheme és recursivo de coa, es pot definir una subrutina recursiva que implementa la subrutina factorial com un procés iterativo, és dir, usa espai constant pero temps llineal.

Fibonacci

Una atra popular seqüència recursiva és el Número de Fibonacci. Els primers elements de la seqüència són: 0, 1, 1, 2, 3, 5, 8, 13, 21...

Definició de la funció:

$\mathrm{fib}(n)=\{\begin{array}{cccc}si& n=0& ⟶& 0\\ si& n=1& ⟶& 1\\ si& n>2& ⟶& \mathrm{fib}(n-2)+\mathrm{fib}(n-1)\end{array}$

Pseudocódigo
function fib is: input: entere n de manera que n >= 0 1. si n és = 0, return 0 2. si n és = 1, return 1 3. else, return [ fib(n-1) + fib(n-2) ] end fib

Relació recurrent per a Fibonacci:
b_n = b_n-1 + b_n-2
b₁ = 1, b₀ = 0

Computant la relació recurrent per a n = 4:
b4 = b3 + b2 = b2 + b1 + b1 + b0 = b1 + b0 + 1 + 1 + 0 = 1 + 0 + 1 + 1 + 0 = 3

Este algoritme de Fibonacci és especialment mal puix cada volta que s'eixecuta la funció, realisarà dos cridades a la funció a sí mateixa, cada una de les quals farà al mateix temps dos cridades més i aixina successivament fins que terminen en 0 o en 1. L'eixemple es denomina "recursión d'arbre", i els seus requisits de temps creixen de forma exponencial i els de espai de forma llineal.

Màxim comú divisor

Un atre famosa funció recursiva és l'algoritme de Euclides, usat per a computar el màxim comú divisor de dos sancers.

Definició de la funció:

$\mathrm{mcd}(x,y)=\{\begin{array}{cccc}si& y=0& ⟶& x\\ si& y>0\wedge x\ge y& ⟶& \mathrm{mcd}(y,mod(x,y))\end{array}$

Pseudocódigo (recursivo):
function gcd is: input: entere x, sancer i de manera que x >= i i i > 0 1. if i is 0, return x 2. else, return [ gcd( i, (remainder of x/i) ) ] end gcd

Relació recursiva del màxim comú denominador, a on $x\mathrm{\%}y$ expressa el restant de la divisió sancera $x/y$:

$\gcd (x,y)=\gcd (y,x\mathrm{\%}y)$

$\gcd (x,0)=x$

Computant la relació recurrent per a x = 27 i i = 9:
gcd(27, 9) = gcd(9, 27 % 9) = gcd(9, 0) = 9
Computant la relació recurrent per a x = 259 i i = 111:
gcd(259, 111) = gcd(111, 259 % 111) = gcd(111, 37) = gcd(37, 0) = 37

Note's que l'algoritme "recursivo" mostrat dalt és, de fet, únicament de coa recursiva, lo que significa que és equivalent a un algoritme iterativo. En l'eixemple següent es mostra el mateix algoritme usant explícitament iteración. No acumula una cadena d'operacions deferred, sino que el seu estat és, més be, mantingut completament en les variables x i i. El seu "number of steps grows the as the logarithm of the numbers involved. ", a l'espanyol "número de passos creix a mida que ho fa el logaritmo dels números involucrats."

Pseudocódigo:
funció gcd és: input: entere x, sancer i de manera que x >= i i i > 0 1. crear una nova variable anomenada remainder 2. begin loop 1. if i is zero, exit loop 2. set remainder to the remainder of x/i 3. set x to i 4. set i to remainder 5. repeat loop 3. return x end gcd

L'algoritme iterativo requerix una variable temporal, i inclús supost el coneiximent del Algoritme de Euclides és més difícil d'entendre el procés a simple vista, encara que els dos algoritmes són molt similars en els seus passos.

Torres de Hanói

Artícul principal → Torres de Hanói.

Per a una detallada discussió de la descripció d'este problema, de la seua història i de la seua solució, consulte's l'artícul principal. El problema, posat de forma simple, és el següent: Donades 3 piles, una en un conjunt de N discs de tamany creixent, determina el mínim (òptim) número de passos que du moure tots els discs des de la seua posició inicial a una atra pila sense colocar un disc de major tamany sobre un de menor tamany.

Definició de la funció:

$\mathrm{hanoi}(n)=\{\begin{array}{cccc}si& n=1& ⟶& 1\\ si& n>1& ⟶& 2\cdot \mathrm{hanoi}(n-1)+1\end{array}$

Relació de recurrencia per a hanoi:

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

$h_1=1$

Computació de la relació de recurrencia per a 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

Eixemples d'implementació:

Pseudocódigo (recursivo):
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

Encara que no totes les funcions recursivas tenen una solució explícita, la seqüència de la Torre de Hanói pot reduir-se a una fòrmula explícita.

Una fòrmula explícita de les Torres de Hanói:
h1 = 1 = 21 - 1 h2 = 3 = 22 - 1 h3 = 7 = 23 - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1 Per lo general: hn = 2n - 1, for all n >= 1

Busca binaria

l'algoritme de busca binaria és un método de busca d'una senya en un vector de senyes ordenat dividint el vector en dos despuix de cada passada. El truc és triar un punt prop del centre del vector, comparar en eixe punt la senya en la senya buscada per a respondre llavors a una de les següents 3 condicions: es troba la senya buscada, la senya en el punt mig és major que el valor buscat o la senya en el punt mig és menor que el valor buscat.

S'usa recursión en este algoritme perque despuix de cada passada es crea un nou vector dividint en original en dos. La subrutina de busca binaria es diu llavors de forma recursiva, cada volta en un vector de menor tamany. El tamany del vector s'ajusta normalment canviant l'índex inicial i final. L'algoritme mostra un orde logaritmo de creiximent perque dividix essencialment el domini del problema en dos despuix de cada passada.

Eixemple d'implementació de la busca binaria:

 /*
  Call binary_search with proper initial conditions.
  
  Entrada: 
    Les senyes es presenten en forma de vector de [[número entero|número entero]] ordenat de forma ascendent,
    ''toFind'' és l'número entero a buscar,
    ''count'' és el número total d'elements del vector
           
  Eixida:
    resultat de la busca binaria
   
 */
 int search(int data, int toFind, int count)
 {
    //  Start = 0 (índex inicial)
    //  End = count - 1 (índex superior)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Algoritme de la busca binaria.
   
   Entrada: 
        Les senyes es presenten en forma de vector de [[número entero|número entero]] ordenat de forma ascendent,
        ''toFind'' és l'número entero a buscar,
        ''start'' és l'índex mínim del vector,
        ''end'' és l'índex màxim del vector
   Eixida: 
        posició de l'número entero ''toFind'' dins del vector de senyes, 
        -1 en cas de busca fallanca
 */
 int binary_search(int data, int toFind, int start, int end)
 {
    //Averigua el punt mig.
    int mid = start + (end - start)/2;   //Divisió de sancers
    
    //Condició per a detindre's.
    if (start > end)
       return -1;
    else if (data[mid] == toFind)        //Trobat?
       return mid;
    else if (data[mid] > toFind)         //La senya és major que ''toFind'', es busca en la mitat inferior
       return binary_search(data, toFind, start, mid-1);
    else                                 //La senya és menor que ''toFind'', es busca en la mitat superior
       return binary_search(data, toFind, mid+1, end);
 }

Estructures de senyes recursivo (recursión estructural)

Una aplicació d'importància de la recursión en ciències de la computació és la definició d'estructures de senyes dinàmiques tals com a llestes i arbres. Les estructures de senyes recursivos poden créixer de forma dinàmica fins a un tamany teòric infinit en resposta a requisits del temps d'eixecució; per la seua banda, els requisits del tamany d'un vector estàtic deuen declarar-se en el temps de complicació.

"Els algoritmes recursivos són especialment apropiats quan el problema que resoldre o les senyes que manejar són definits en térmens recursivos."

Els eixemples en esta secció ilustren lo que es coneix com "recursión estructural". Este terme es referix al fet de que les subrutina recursivas s'apliquen a senyes que es definixen de forma recursiva.

En la mida en que un programador deriva una plantilla d'una definició de senyes, les funcions ampren recursión estructural. És dir, les recursiones en el cos d'una funció consumixen una determinada cantitat d'un compost donat de forma immediata.

Llistes enllaçades

A continuació es descriu una definició simple del nodo d'una llista enllaçada. Note's com es definix el nodo per sí solament. El següent element del nodo del struct és un punter a un nodo de struct.

struct node
{
  int n;              // algun tipo de senyes
  struct node *next;  // busca a un atre nodo de ''struct''
};

// LIST no és una atra cosa que un nodo de ''struct'' *.
typedef struct node *LIST;

Les subrutina que operen en l'estructura de senyes de LIST poden implementar-se de forma natural com una subrutina recursiva perque l'estructura de senyes sobre la que opera (LIST) és definida de forma recursiva. La subrutina printList definida a continuació recorre la llista cap a avall fins que esta es buida (NULL), per a cada nodo imprimix la senya (un número entero). En l'implementació en C, la llista permaneix inalterada per la subrutina printList.

void printList(LIST lst)
{
    if (!isEmpty(lst))         // cas bàsic
    {
       printf("%d ", lst->n);  // imprimix el sancer seguit per un espai
       printList(lst->next);   // cridada recursiva
    }
}

Arbres binarios

Més avall es mostra una definició simple d'un nodo d'arbre binario. De la mateixa manera que el nodo de llistes enllaçades, es definix a sí mateixa (de forma recursiva). Hi ha dos busques que es referixen a sí mateixos – left (apuntant a l a banda esquerra del subárbol) i right (a la part dreta del subárbol).

struct node
{
  int n;               // algun tipo de senyes
  struct node *left;   // busca al subárbol esquerre
  struct node *right;  // busca al subárbol dret
};

// TREE no és una atra cosa que un nodo '' struct ''
typedef struct node *TREE;

Les operacions en l'arbre poden implementar-se usant recursión. Note's que, pel fet de que hi ha dos busques que es referencian a sí mateixos (esquerra i dreta), eixes operacions de l'arbre van a necessitar dos cridades recursivas. Per a un eixemple similar, vore la funció de Fibonacci i l'explicació següent.

void printTree(TREE t) {
        if (!isEmpty(t)) {            // cas bàsic                          
                printTree(t->left);   // anar a l'esquerra
                printf("%d ", t->n);  // imprimir el sancer seguit d'un espai
                printTree(t->right);  // anar a la dreta
        }
}

L'eixemple descrit ilustra un arbre binario d'orde transversal. Un arbre de busca binaria és un cas especial d'arbre binario en el qual les senyes de cada arbre estan en orde.

Recursión front a iteración

En l'eixemple "factorial" l'implementació iterativa és provablement més ràpida en la pràctica que la recursiva. Açò és casi definit per l'implementació de l'algoritme euclidiano. Este resultat és llògic, puix les funcions iterativas no tenen que pagar l'excés de cridades de funcions com en el cas de les funcions recursivas, i eixe excés és relativament alt en molts llenguages de programació (note's que per mig de l'us d'una lookup table és una implementació encara més ràpida de la funció factorial).

Hi ha atres tipos de problemes les solucions dels quals són inherentemente recursivas, perque estar al tant de l'estat anterior. Un eixemple és l'arbre travesser; uns atres inclouen la funció de Ackermann i l'algoritme dividix i venceràs tals com Quicksort. Tots estos algoritmes poden implementar-se iterativamente en l'ajuda d'una pila, pero la necessitat del mateix, pot ser que anule les ventages de la solució iterativa.

Una atra possible raó per a l'utilisació d'un algoritme iterativo en lloc d'un recursivo és el fet de que en els llenguages de programació moderns, l'espai de stack disponible per a un fil és, a sovint, molt manco que l'espai disponible en el montícul, i els algoritmes recursivos solen requerir més espai de stack que els algoritmes iterativos. Vore, per un atre costat, la secció següent que tracta el cas especial de la recursión de coa.

Vore també

• Recursión primitiva
• Programació funcional
• Funció de Ackermann