Recursion

De Wikipedia, le encyclopedia libere
Saltar a: navigation, cercar
Publicitate de cacao con un imagine recursive. La femina monstra un pacchetto identic a illa del proprie publicitate, continente assi altere femina que monstra altere pacchetto plus parve, de forma recursive.
Imagine recursive (triangulo de Sierpiński) formate per un triangulo. Cata triangulo se trova composite de alteres plus parve, composite a su torno del mesme structura recursive.

Recurrentia, recursion o recursivitate es le forma in le qual se specifica un processo basate super su proprie definition. Essente un poco plus precise, e a fin de evitar le apparente circulo sin fin in iste definition:

Un problema que pote esser definite in function de su mesura, sia iste N, pote esser dividite in instantias plus parve (< N) del mesme problema e on cognosce le solution explicite al instantias plus simple, los que on cognosce como casos base, on pote applicar induction super los appellate plus parve e supponer que iste deveni resolvite.

A fin que on comprende melior a continuation, se expone alcun exemplos:

  • Factorial(x: Integre): Sia N := x le mesura del problema, nos pote definir le problema de forma recurrente como x*Factorial(x - 1); como le mesura de Factorial(x - 1) es minor que N nos pote applicar induction per lo que nos dispone del resultato. Le caso base es le Factorial(0) que es 1.
  • Assortimento per fusion(v: vector): Sia N := mesura(v), nos pote separar le vector in duo medietates. Iste duo medietates habe mesura N/2 e per induction nos pote applicar le assortimento in iste duo subproblemas. Un vice que nos habe ambe medietates assortite simplemente nos debe fusionar los. Le caso base es assortir un vector de 0 elementos, que se trova trivialmente assortite e il debe facer nihil.

In iste exemplos nos pote observar como un problema se divide in varie (>= 1) instantias del mesme problema, ma de mesura minor gratias a lo qual se pote applicar induction, portante a un puncto ubi on cognosce le resultato (le caso base)..

Nota: benque le terminos "recursion" e "recursivitate" son amplemente usate in le campo del informatica, le termino correcte es recurrentia. Nonobstante iste ultime termino es plus specific. Vide relation de recurrentia.

Le numeros natural[modificar | modificar fonte]

Un exemplo de ensemble definite de forma recurrente es le ensemble del numeros natural:

a) 0 pertine a N
b) Si n pertine a N, alora n+1 pertine a N
c) Si X verifica a) e b) , alora N se trova includite in X

Le numeros natural es le ensemble de numeros integre non negative.

Functiones definite de forma recurrente[modificar | modificar fonte]

Aquelle functiones cuje dominio pote esser recursivemente definite pote esser definite de forma recurrente.

Le exemplo plus cognoscite es le definition recurrente del function factorial n!:


n!=
\begin{cases} 
\mbox{si }n=0 & \Rightarrow 1  \\ 
\mbox{si }n\geq1 & \Rightarrow n \;(n-1)!
\end{cases}


Con iste definition nos vide como functiona iste function pro le valor del factorial de 3:

3! = 3 · (3-1)!
   = 3 · 2!
   = 3 · 2 · (2-1)!
   = 3 · 2 · 1!
   = 3 · 2 · 1 · (1-1)!
   = 3 · 2 · 1 · 0!
   = 3 · 2 · 1 · 1
   = 6

Algorithmo recursive[modificar | modificar fonte]

Un methodo usual de simplification de un problema complexe es divider lo in subproblemas del mesme typo. Iste technica de programmation es cognoscite como divide e vince e es le nucleo in le designo de numerose algorithmos de grande importantia, assi como anque es un parte fundamental del programmation dynamic.

Le exemplo del calculo recursive del factorial de un numero portate al campo del programmation, in iste exemplo C++:

int factorial(int x)
{
   if (x > -1 && x < 2) return 1;  // Quando -1 < x < 2 nos restitue 1 puesto que 0! = 1 e 1! = 1
   else if (x < 0) return 0;       // Error: il non existe factorial de numeros negative
   return x * factorial(x - 1);    // Si x >= 2 nos restitue le producto de x per le factorial de x - 1
}

Le curso del recursivitate programmate es quasi exactemente equal al exemplo antea date, a fin de intentar adjutar pro comprender melior se ha accompaniate con multe explicationes e con colores que differentia le distincte sub-processos del recursivitate.

X = 3 //Nos vole 3!, dunque X initial es 3
X >= 2 -> return 3*factorial(2);
    X = 2 //Ora nos sta a sollicitar le factorial de 2
    X >= 2 -> return 2*factorial(1);
        X = 1 // Ora nos sta a sollicitar le factorial de 1
        X < 2 -> return 1;
        [In iste puncto nos habe le factorial de 1 per lo que nos volve marcha retro resolvente tote le resultatos]
    return 2 [in altere parolas: return 2*1 = return 2*factorial(1)]
return 6 [in altere parolas: return 3*2 = return 3*factorial(2)*factorial(1)] // Le resultato devolvite es 6

Exemplos de recurrentias[modificar | modificar fonte]

Resolution de equationes homogene de prime grado, secundo ordine:

a) On passa al prime membro le terminos a_n, a_{n-1}, a_{n-2}, le quales anque poterea figurar como a_{n+2}, a_{n+1}, a_n

b) On reimplacia a_n per r^2, a_{n-1} per r e a_{n-2} per 1, obtenente un equation de secunde grado con radices real e distincte r_1 e r_2.

c) On presenta  a = u\; r_1 n + v\; r_2 n

d) Nos debe haber como dato le valores del duo prime terminos del succession: A_0 = k\, e A_1 = k^\prime. Utilisante iste datos nos ordina le systema de 2x2:

\begin{cases}
u + v = k \\
u \; r_1 + u \; r_2 = k^\prime
\end{cases}

Le resolution de iste systema nos da como resultato le valores u_0 e v_0, que son numeros real cognoscite.

e) Le solution general es:

a_n = u_0 \; r_1 n + v_0 \; r_2 n



Alcun exemplos de recurrentia:

Ligamines externe[modificar | modificar fonte]

Logo

Iste pagina usa contento del Wikipedia in espaniol. Le articulo original se trova a es:Recursión, e es usate secundo le mandatos del licentia de Wikipedia.