Recursion

**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 (= 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\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
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 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*(2*n*, *n*)/(*n*+1)
* Le Turres de Hanoi
* Function de Ackermann

## Ligamines externe
*  Exemplo de curvas recursive fractal