¿Dijiste recursión?

Enviado por jmd el 12 de Diciembre de 2009 - 20:19.
Versión para impresiónEnviar a un amigo Share this

Introducción

La palabra recursión no la acepta la Real Academia española, a pesar de ser ampliamente usada en matemáticas y computación. Su palabra análoga más cercana es la de recurrencia que significa "que vuelve a ocurrir". En la recursión hay algo que se repite, es decir, que vuelve a ocurrir.

En matemáticas, el significado de "recursión" es más fácil de captar a través de ejemplos. El factorial de un número $ n $ se define como "$ n $ por el factorial de $ n-1 $". El problema es que entonces faltaría definir  el factorial de $ n-1 $. El problema se disuelve definiendo el caso base: el factorial de cero es 1.

Factorial de un número


El factorial de un número natural puede ser pensado como una función de los naturales en los naturales. Se denota con $ ()! $ y tiene la siguiente definición (no recursiva): $ n! = n(n - 1)(n -2) \cdots (3)(2)(1) $. El caso base es, por convención, $ 0! = 1 $.


Ejemplos:

$ 1! = 1 $,

$ 4! = (4)(3)(2)(1) = 24 $.


La forma recursiva de definir la función factorial es: Si $ n = 0 $ entonces $ n! = 0 $ (caso base), de otra manera (paso inductivo),  $ ( n + 1 )! = (n + 1)n! $ Ejemplo: $ 5!=5\times 4! $ .

Notemos en este ejemplo la principal utilidad de la recursión: el problema se reduce a otro de una dimensión menor.

$ 4! = (3 + 1)! =( 3 + 1 )( 3! ) = (4)(3!) $

$ 3! = 3( 2! ) $

$ 2! = (2)(1!) $

$ 1! = (1)(0!) $

Pero $ 0! $ sí está definido.

Entonces:

$ 1! = (1)(1) = 1 $

 $ 2! = (2)(1!) = (2)(1) = 2 $

$ 3! = (3)(2!) = (3)(2) = 6 $

 $ 4! = (4)(3!) = (4)(6) = 24 $

 $ 5! = (5)(4!) = 5(24) = 120 $

Recursividad


La definición misma de los números naturales es recursiva: 1 es un número natural (caso base), si n es un número natural entonces n+1 es un número natural.

 Sea $ f $ una función que transforma números naturales en elementos  de un conjunto $ A $ (esto lo abreviamos $ f: \mathbb{N} \rightarrow A $).  Se dice que la función $ f $ es recursiva si existe el caso base  $ a_{0} \in A $  tal que  $ f(0) = a_{0} $, y una operación $ T $ que transforma el número natural $ n $ y un elemento $ f(n) \in A $ en un elemento  $ T ( n, f(n) ) \in A $  tales que:


 $ f(0) = a_{0} $

 $ f(n + 1) = T(n, f(n) ) $

Dentro de esta definición (que no es la más general) está el factorial de un número natural: $ f(n+1)=(n+1)f(n) $, con $ f(0)=1. $

En general, se requiere el caso base y la transformación de $ n+1 $ en términos de $ n $ y $ f(n). $  Por ejemplo, si definimos $ f(n+1) $ como $ n+f(0) $ con $ f(0)=-3 $, se tiene $ f(0)=-3, f(1)=1-3=-2, $ etc.

Torres de Hanoi

La solución del acertijo denominado las Torres de Hanoi es también recursiva. En este acertijo hay tres postes donde se pueden colocar discos de diferentes diámetros. Inicialmente hay n discos en el poste 1 y el reto es pasarlos al poste 3  con la restricción de que nunca se ponga en un mismo poste un disco sobre uno de mayor diámetro y moviendo solamente un disco a la vez.

La solución para $ n=1 $ (caso base) es trivial, para $ n=2 $ se tiene que usar el poste 2 como de transición y "pasar el disco 1 al poste 2 y usar la solución para $ n=1 $ para el disco 2  y para el disco 1". De esta manera, si se sabe la solución para $ n $ discos entonces la solución para $ n+1 $ se obtiene "pasando los primeros $ n $ al poste 2, pasar el disco $ n+1 $ al poste 3 y finalmente pasar los $ n $ del poste 2 al poste 3." (Ver comentario más abajo sobre "pensar recursivamente".)

El lector podría verificar que para 3 discos se necesitan 7 movimientos. Para demostrar que para $ n $ discos se requieren $ 2^n-1 $ movidas, designemos con $ T(n) $ el número mínimo de movidas para pasar $ n $ discos del poste 1 al 3. Demostremos que $ T(n)=2^n-1 $.

El caso base es $ n = 1 $. Para este caso basta con hacer una movida, es decir, $ T(1) = 1 = 2^1-1 $. Así que la fórmula $ T(n)=2^n-1 $ se cumple para el caso base.

Ahora el paso inductivo. La hipótesis de inducción es que para n discos son necesarias $ T(n)=2^n – 1 $ movidas, y queremos probar que $ T(n+1)=2^{n+1}-1 $ (si la hipótesis de inducción es cierta). Es decir, queremos probar que si la fórmula se cumple para $ n $ entonces también se cumple para$ n+1 $.

(El siguiente razonamiento no es fácil de asimilar; para su comprensión cabal el lector debe razonarlo de manera recursiva. ¿Y cómo lo puede razonar recursivamente si todavía no sabe razonar recursivamente? Bueno, ésta es la paradoja del aprendizaje,  y lo único que yo podría decir es --aquí va una de mis frases favoritas-- el significado está en el uso.)

Puesto que para $ n+1 $ discos lo que tenemos que hacer es pasar los $ n $ discos superiores al poste 2 ($ T(n) $ movidas, por hipótesis de inducción), luego pasar el disco inferior al poste 3 (una movida) y, finalmente, pasar los $ n $ discos en el poste 2 al poste 3 ($ T(n) $ movidas), tenemos entonces que:

$ T(n+1)=2T(n)+1 $  (por lo recién dicho)

$ = 2 (2^n-1)+1 $  (por la hipótesis de inducción)

$ = 2 (2^n)-2+1 $ (expandiendo el producto)

$ = 2^{n+1}-1 $ (simplificando)

El teorema queda demostrado. (Este ejemplo ilustra el hecho de que el paso inductivo en general no es fácil. Es casi obligatorio "ver" la recursividad de la solución del acertijo.)

Factorización prima

Uno de los usos de más potencia de la recursividad es en el diseño de algoritmos. El siguiente ejemplo es el procedimiento equivalente a la prueba de la descomposición canónica de un número natural $ n $ --factorización prima:

Paso de inicialización: Dividir $ n $ entre $ 2,3,4,5,\ldots $ hasta encontrar un primer divisor $ p $ de  $ n $.

Si $ p=n $ entonces ya acabamos: n es primo (por favor, mediten sobre la veracidad de esta afirmación); de otra manera, si p es menor que n, entonces p es primo (porque si hubiese un divisor d de p tendría que ser menor que p y sería también divisor de n --y se logra una contradicción, pues entonces p no sería el primer divisor de n según el procedimiento.)

Paso recursivo: (Ya tenemos un primer factor primo de $ n=(n/p)p $) Repetir el proceso para $ n/p $.


Otra instancia de uso de la recursión como método de demostración

Con esta idea general de que si ya sabemos resolverlo para n entonces lo podemos resolver para $ n+1 $ veamos un pequeño teorema. Pero antes recordemos la notación sumatoria.

$ \sum_{m=2}^{4} a_{m} = a_{2} + a_{3} + a_{4} $.

$ \sum_{k= 2}^{5} k^{2} = 2^{2} + 3^{2} + 4^{2} + 5^{2} = 54 $


$ \sum_{n=1}^{7} {2n - 1} $ = $ \sum_{0 \leq j \leq 6} 2j + 1 $

 Ejercicio: Demostrar que  $ \sum_{i = 1}^{5} (i + 2) = \sum_{j =3}^{7} j $

Demostrar que para todo $ n \geq 3 $, $ n! \geq 0 + \cdots + n =\sum_{i = 0}^{n} i $

Solución
 Como tenemos que demostrar una propiedad para todos los números naturales a partir de $ 3 $,  el caso base es el $ 3 $, el cual tenemos que demostra directamente y después  en el paso inductivo supondremos que $ n \geq 3 $, y que la propiedad se cumple para n.

Caso base ($ n = 3 $):

$ 3! = 6 \geq 0 + 1 + 2 + 3 = \sum_{i = 0}^{3} i $

Supongamos que $ n \geq 3 $ es tal que $ n! \geq \sum_{i =0}^{n}i $.

Entonces, sumando $ n + 1 $ a ambos lados de $ n!\geq\sum_{i=0}^{n} i $ se obtiene  $ n! + (n + 1) \geq \sum_{i = 0}^{n} i + (n + 1) = 0 + 1 + \ldots + n + (n+1) $


Por otro lado,

$ (n + 1)! = (n + 1)n! $ (por recursividad)

$ = nn! + n! $ (por la propiedad distributiva de la multiplicación respecto a la suma)

$ \geq 2n + n! $ (porque $ n \geq 3 $)

$ \geq (n + 1) + n! $ (porque $ n \geq 3 $)

Pero antes demostramos que $ n! + (n + 1) \geq \sum_{i = 0}^{n+1}i $

De aquí que $ (n + 1)!\geq \sum_{i = 0}^{n+1} i $

 como se quería.

Los saluda

jmd

PD: Una definición recursiva "viola" una de las reglas del definir. No puede ser que el concepto definido entre a formar parte de su definición (no se puede definir algo en términos de sí mismo). Pero, se puede pensar a la definición recursiva como la excepción de la regla.

Ejemplo clásico: un ancestro de X es, ya sea uno de los padres de X o bien un ancestro de sus padres.
Otro ejemplo: un directorio (en el disco duro de mi PC) es una parte del disco que contiene archivos y directorios.

Su carácter de excepción es quizá lo que hace difícil comprender la recursión.

AdjuntoDescripciónTamaño
Torres de Hanoi.PNGTorres de Hanoi.PNG33.02 KB