Recursion

Recursion
subclasse de: self-similarity[*]
Commons: Recursion

Publicitate de cacao con un imagine recursive. Le femina monstra un pacchetto identic a illo del publicitate mesme, continente assi un altere femina qui monstra un 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 lor 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, illos que on cognosce como casos base, on pote applicar induction super illos appellate plus parve e supponer que isto deveni resolvite.

A fin que on comprende melior le 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 le 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 ha mesura N/2 e per induction nos pote applicar le assortimento in iste duo subproblemas. Quando nos ha ambe medietates assortite, simplemente nos debe fusionar los. Le caso de base es assortir un vector de 0 elementos, que se trova trivialmente assortite, e illo debe facer nihil.

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

Nota: Ben que le terminos "recursion" e "recursivitate" es 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

Un exemplo de insimul definite de forma recurrente es le insimul 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 insimul de numeros integre non negative.

Functiones definite de forma recurrente

Iste functiones cuje dominio pote esser recursivemente 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\geq 1&\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

Un methodo usual de simplification de un problema complexe es de 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 donate, a fin de intentar de adjutar pro comprender melio accompaniate con multe explicationes e con colores que differentia le subprocessos distincte 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 ha 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

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}$, qui es numeros real cognoscite.

e) Le solution general es:

$a_{n}=u_{0}\;r_{1}n+v_{0}\;r_{2}n$

Alcun exemplos de recurrentia:

• Factorial -- n! = n × (n-1)!
• Succession de Fibonacci -- f(n) = f(n-1) + f(n-2)
• Numeros de Catalan -- C(2n, n)/(n+1)
• Le Turres de Hanoi
• Function de Ackermann

Ligamines externe

• (espaniol) Exemplo de curvas recursive fractal

Nota

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