Recursión

Anunci de cacao en una image recursiva. La dòna mostra un paquet idèntic al del propi anunci, contenint aixina a una atra dòna que mostra un atre paquet més menut, de forma recursiva.

Image recursiva formada per un triàngul de Sierpinski. Cada triàngul està compost d'uns atres, composts a la seua volta de la mateixa estructura recursiva.

La recursión o recursividad és la possibilitat que té un cert tipo d'unitat o procés de contindre's o aplicar-se a sí mateixa indefinidament. La recursión té esta característica discernible en térmens d'autorreferencialidad, autopoiesis, fractalidad o, en atres paraules, construcció a partir d'un mateix tipo. En ànim d'una major precisió, i per a evitar l'aparent circularidad en esta definició, es formula el concepte de recursión de la següent manera:

Un problema que puga definir-se en funció del seu tamany, siga este N, pot dividir-se en instàncies més chicotetes (< N) del mateix problema i es coneixerà la solució explícita a les instàncies més simples, lo que es coneix com a casos base, i es pot aplicar inducció sobre les cridades més chicotetes i supondre que estes queden resoltes.^{cita requerida}

A continuació s'exponen alguns eixemples:

• Factorial: Es desija calcular $n!$ (el factorial de $n$, que es definix com el producte de tots els sancers positius de $1$ a $n$). Es pot definir el problema de forma recurrent com $n(n-1)!$; com $(n-1)!$ és menor que $n!$ podem aplicar inducció per lo que disponem del resultat. El cas base és $0!$ que és $1$.
• Algoritme d'ordenació per fusió: Siga v un vector de n elements, podem separar el vector en dos mitats. Estes dos mitats tenen tamany n/2 per lo que, per inducció, podem aplicar l'ordenació en estos dos subproblemas. Una volta tenim abdós mitats ordenades, simplement devem fusionar-les. El cas base és ordenar un vector de zero o un element, que està trivialmente ordenat i no cal fer res.

En estos eixemples pot observar-se cóm un problema es dividix en vàries (una o més) instàncies del mateix problema, pero de tamany menor, gràcies a la qual cosa es pot aplicar inducció, aplegant a un punt a on es coneix el resultat (el cas base).^{cita requerida}

Recursión en matemàtiques

Conjunts definits de forma recurrent

Un eixemple de conjunt definit de forma recurrent és el dels número natural, és dir, el conjunt dels número entero no negatius:

1. $0$ pertany a ℕ.
2. Si $n$ pertany a ℕ, llavors $n+1$ pertany a ℕ.
3. Si $x$ verifica les anteriors condicions, llavors $x$ està inclós en ℕ ^{cita requerida}.

Funcions definides de forma recurrent

Aquelles funcions que el seu domini és un conjunt a lo més enumerable poden ser definides de forma recurrent.

Un eixemple conegut és la definició recurrent de la funció factorial n!:

$n!=\{\begin{array}{cc}\text{si }n=0& \Rightarrow 1\\ \text{si }n\ge 1& \Rightarrow n(n-1)!\end{array}$

Vejam cóm s'usa esta definició per a trobar el valor del factorial de 3:

$\begin{array}{cc}3!& =3\cdot (3-1)!\\ & =3\cdot 2!\\ & =3\cdot 2\cdot (2-1)!\\ & =3\cdot 2\cdot 1!\\ & =3\cdot 2\cdot 1\cdot (1-1)!\\ & =3\cdot 2\cdot 1\cdot 0!\\ & =3\cdot 2\cdot 1\cdot 1\\ & =6\\ \end{array}$

Atres eixemples de funcions i successions matemàtiques definides de forma recursiva són:

• Successió de Fibonacci — f(0)= 1, f(1) = 1; f(n) = f(n-1) + f(n-2) para $n\ge 2$.
• Números de Catalan — C(2n, n)/(n+1)
• Funció de Ackermann

Constants

La raó áurea es pot definir de forma recursiva, com una fracció contínua en que tots els números són uns:

$\varphi =1+\frac{1}{\varphi }=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\mathrm{...}}}}$.

De forma similar, l'identitat $\sqrt{x}=1+\frac{x-1}{1+\sqrt{x}}$ dona lloc a una definició com a fracció contínua de qualsevol raïl quadrada:

$\sqrt{x}=1+\frac{x-1}{2+\frac{x-1}{2+\frac{x-1}{2+\ddots }}}$

Resolució de problemes

Resolució d'equacions homogénees de primer grau, segon orde:

a) Es passen al primer membre els térmens $a_n$, $a_{n-1}$, $a_{n-2}$, els quals també podrien figurar com $a_{n+2}$, $a_{n+1}$, $a_n$

b) Es reemplaça $a_n$ per $r^2$, $a_{n-1}$ per $r$ i $a_{n-2}$ per $1$, quedant una equació de segon grau en raïls reals i distintes $r_1$ i $r_2$.

c) Es planteja $a=u{r}_{1}n+v{r}_{2}n$

d) Devem tindre com a senya els valors dels dos primers térmens de la successió: $A_0=k$ i $A_1=k^{\prime }$. Utilisant estes senyes ordenem el sistema de 2x2:

$\{\begin{array}{c}u+v=k\\ u{r}_1+u{r}_2=k^{\prime }\end{array}$

La resolució d'este sistema nos dona com resultat els valors $u_0$ i $v_0$, que són número real coneguts.

i) La solució general és:

$a_n=u_0{r}_{1}n+v_0{r}_{2}n$

Recursión en informàtica

Artícul principal → Recursión (ciències de computació).

En programació, un método usual de simplificació d'un problema complex és la divisió d'est en subproblemas del mateix tipo. Esta tècnica de programació es coneix com dividix i venceràs i és el núcleu en el disseny de numerosos algoritmes de gran importància, aixina com també és part fonamental de la programació dinàmica.

Implementació en C:

int factorial (int n)
{
    if (n > 1)
    {
        return n * factorial(n-1);
    }else
    {
        return 1;
    }
}
int main()
{
    printf("Recusividad
");

    int result = factorial(5);
    printf("El resultat és: %i", result);
    return 0;
}

Implementació en C++:

 int factorial(int x)
 {
    if (x > -1 && x < 2) return 1;  // Quan -1 < x < 2 tornem 1 lloc que 0! = 1 i 1! = 1
    else if (x < 0) return 0;       // Error no existix factorial de números negatius
    return x * factorial(x - 1);    // Si x >= 2 tornem el producte de x pel factorial de x - 1
 }

Implementació en Pascal:

  FUNCTION Factorial (CONST N: INTEGER): INTEGER;
  BEGIN
    IF N > 1 THEN
      Factorial := N * (Factorial (N - 1));
    ELSE
      BEGIN
         IF ((N=0) OR (N=1))
           Factorial := 1;
         ELSE
           Factorial := 0;
      END;
    END;
  END;

Implementació en Python:

def factorial(n):
    if n == 1 or n == 0:
        return 1
    else:
        return n * factorial(n-1)

El seguiment de la recursividad programada és casi exactament igual als eixemples abans donats, per a intentar ajudar a que s'entenga millor s'ha acompanyat en moltes explicacions i en colors que diferencia els distints sub-processos de la recursividad.

X = 3 //Volem 3!, per lo tant X inicial és 3
X >= 2 -> return 3factorial(2);
    X = 2 //Ara estem solicitant el factorial de
    2 X >= 2 -> return 2factorial(1);
        X = 1 // Ara estem solicitant el factorial d'1
        X < 2 -> return 1;

[En este punt tenim el factorial d'1 per lo que tornem marcha arrere resolent tots els resultats]

    return 2 [és dir: return 2*1 = return 2factorial(1)]
return 6 [és dir: return 3*2 = return 3factorial(2)factorial(1)] // El resultat tornat és 6

Vore també

• Recursión (ciències de computació)
• Algoritme recursivo
• Fractal
• Sistema-L
• Torres de Hanói
• Relació de recurrencia
• Iteración
• Metaficción