Recursion
From Wikipedia, the free encyclopedia
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.