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
modificaUn 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
modificaAquelles 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
modificaLa 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
- ↑ 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