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, essent les finals més simples, definides de forma 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ó, vegem 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 següent manera:

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, Chomsky) consideren que la recursivitat és inherent als sistemes de comunicació humans i, en particular, al llenguatge humà. 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ã.

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]

Vegeu també[modifica | modifica el codi]