Recursivitat

De Viquipèdia

Recursió ó Recursivitat és la forma en la qual s'especifica un procès basat en la seva pròpia definició. Sent una mica més precisos, 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, estant les finals més simples, definides de forma explícita.

[edita] Els nombres naturals

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

0 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.

[edita] Funcions definides de manera recursiva

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

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

f(0) = 1

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

Amb aquesta definició, vegem com funciona aquesta funció per al valor del factorial de 3:

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

Alguns exemples de recursió:

• 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