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 orecursivitate 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 apparentecirculo 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 applicarinduction 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 delinformatica, le termino correcte esrecurrentia. Nonobstante iste ultime termino es plus specific. Viderelation de recurrentia.
Un methodo usual de simplification de un problema complexe es de divider lo in subproblemas del mesme typo. Iste technica deprogrammation es cognoscite comodivide e vince e es le nucleo in le designo de numerosealgorithmos de grande importantia, assi como anque es un parte fundamental delprogrammation dynamic.
Le exemplo del calculo recursive del factorial de un numero portate al campo delprogrammation, in iste exemploC++:
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.
//Nos vole 3!, dunque X initial es 3 //Ora nos sta a sollicitar le factorial de 2 // Ora nos sta a sollicitar le factorial de 1 [In iste puncto nos ha le factorial de 1 per lo que nos volve marcha retro resolvente tote le resultatos] [in altere parolas: return 2*1 = return 2*factorial(1)] [in altere parolas: return 3*2 = return 3*factorial(2)*factorial(1)] // Le resultato devolvite es 6
Iste pagina contine material traducite abWikipedia in espaniol. Le articulo original se trova aes:Recursión, e es usate secundo le mandatos del licentia de Wikipedia.
