Recursivitat

Un exemple de conjunt definit de manera recursiva és el dels nombres naturals:

1 pertany a N

si n pertany a N, llavors n+1 pertany a N

Els nombres naturals és el conjunt menor que compleix les dues propietats anteriors.

Aquelles funcions el domini de les quals pot ser recursivament definit, poden ser definides de manera recursiva.

L'exemple més conegut és la definició recursiva de la funció factorial f(n) = n! :

f(1) = 1

f(n) = n · f(n-1)  per a tot nombre natural n > 1

Amb aquesta definició, veiem com funciona aquesta funció per al valor del factorial de tres:

f(3) = 3 · f(2)
= 3 · 2 · f(1) 
= 3 · 2 · 1
= 6

Per tant, a partir del cas base i del cas global, podem definir la funció recursiva (en Java) de la manera següent:

public int Factorial(int n)
{
 if(n==0) return 1;
 else return n*Factorial(n-1);
}

La gramàtica sànscrita de Pānini ja usa la recursivitat en el segle V a.n.e. Noam Chomsky i altres autors consideren que la recursivitat és inherent als sistemes de comunicació humans i, en particular, al llenguatge humà.^[1][2] Avui dia, aquesta afirmació es veu qüestionada per treballs de cognició animal no humana, d'una banda i, de l'altra, per certes interpretacions de la gramàtica pirahã.^[3]

Un exemple de recursivitat en lingüística és la construcció dels grups nominals, com ara en: "la clau del pany de la porta d'entrada de la casa del carrer de l'eixida del poble". Les conjuncions, per exemple, són elements recursius.

• Factorial -- n! = n × (n-1)!
• Successió de Fibonacci -- f(n) = f(n-1) + f(n-2)
• Nombres de Catalan -- C(2n, n)/(n+1)
• Les Torres de Hanoi
• Funció d'Ackermann
• Rosa és una rosa és una rosa és una rosa

• Autoreferència.
• Efecte Droste.
• Regressió infinita.

Viccionari