Recursivitat
La recursivitat és la forma en la qual s'especifica un procés basat en la seva pròpia definició. Més precisament, i per a evitar l'aparent cercle sense fi en aquesta definició, les instàncies complexes d'un procés es defineixen en termes d'instàncies més simples, i en són les finals més simples, definides de manera explícita.
Els nombres naturals[modifica]
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.
Funcions definides de manera recursiva[modifica]
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 recursivitat en lingüística[modifica]
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.
Alguns exemples de recursivitat[modifica]
- 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
Referències[modifica]
 |
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Recursivitat |
- ↑ Pinker, Steven. The Language Instinct. William Morrow, 1994.
- ↑ Pinker, Steven; Jackendoff, Ray «The faculty of language: What's so special about it?». Cognition, 95, 2, 2005, pàg. 201–236. DOI: 10.1016/j.cognition.2004.08.004. PMID: 15694646.
- ↑ Nevins, Andrew; Pesetsky, David; Rodrigues, Cilene «Evidence and argumentation: A reply to Everett (2009)» (PDF). Language, 85, 3, 2009, pàg. 671–681. DOI: 10.1353/lan.0.0140.
Vegeu també[modifica]