Recursivitat

De Viquipèdia
Dreceres ràpides: navegació, cerca
Publicitat amb la utilització d'una imatge recursiva

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 | modifica el codi]

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 | modifica el codi]

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 3:

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 | modifica el codi]

La gramàtica sànscrita de Pānini ja usa la recursivitat en el segle V a.n.e. Alguns autors (per exemple, Noam Chomsky) 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, 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 | modifica el codi]

Referències[modifica | modifica el codi]

  1. Pinker, Steven. The Language Instinct. William Morrow, 1994. 
  2. 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.
  3. 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 | modifica el codi]