Instinto Lógico

Recuerda que nadie debe pensar por tí.

Introducción a la recursividad.

Triángulo-SierpinskiLa recursividad es una técnica muy utilizada en programación informática. Se suele utilizar  para resolver problemas cuya solución se puede hallar resolviendo el mismo problema, pero para un caso de tamaño menor.

Cuando en informática se escribe un programa con un algoritmo recursivo, en las propias sentencias del algoritmo hay una llamada a sí mismo, es decir una de las sentencias llama al algoritmo recursivo en el que está insertada, aunque para solucionar un caso más sencillo.

Los métodos recursivos se pueden usar en cualquier situación en la que la solución pueda ser expresada como una sucesión de pasos o transformaciones gobernadas por un conjunto de reglas claramente definidas.

En un algoritmo recursivo podemos distinguir dos partes:

Base o problema trivial que se puede resolver sin cálculo

Recursión: Fórmula da la solución del problema en función define de un problema del mismo tipo más sencillo

Escher-recursividadLa idea fundamental es que el algoritmo se hace una llamada así mismo.  Así se la imaginó poéticamente el pintor y grabador holandés M. C. Escher (1898-1972) en la litografía titulada Manos dibujando (1948), en la que la mano que dibuja y la mano dibujada juegan el mismo papel y producen un efecto en el que la causa y el efecto parecen intercambiar sus papeles.

EJEMPLOS BÁSICOS DE RECURSIVIDAD:

Ejemplo 1. Para definir recursivamente el algoritmo de calcular la potencia n-ésima de a,  al que designaremos.

potencia n-esima

procederemos de la siguiente forma:

problema potencia enésima

Ejemplo 2. Para definir recursivamente un algoritmo para calcular el factorial de un número natural.

factorial

Y que designaremos:

notación del factorial

Procederemos de la siguiente forma:

problema-fact

¿CÓMO FUNCIONA LA RECURSIVIDAD?

Para comprender cómo funciona la recursividad tomaremos como ejemplo el algoritmo del cálculo de Factorial (n) = n!  dado en el ejemplo anterior:

problema-fact

Al valor Factorial(n)= 1 si n =0 es lo que llamamos base, es un valor que se obtiene de forma sencilla.

A la expresión Factorial(n)=n·Factorial(n-1)  se le llama recursión. Es la fórmula que da la solución del problema en función de un problema del mismo tipo, aunque más sencillo. (En es te caso la fórmula de recursión permite calcular en función de otro factorial más sencillo (n-1)! )

Para comprender como funciona la recursividad tomemos el ejemplo la forma recursiva de n!  y supongamos que queremos calcular Factorial(3)=3! 

Primer paso: Llegar hasta el primer valor de conocido,  que, en este caso será la base, Factorial(0) =0!=1

 

 Factorial (0) 1
 Factorial (1) ¿?
Factorial (2) ¿?
 Factorial (3) ¿?

 

El segundo paso: Calcular  Factorial (1) con la fórmula de recursividad:

Factorial(n)=n·Factorial(n-1) si n>0,  que es aplicable porque n =1>0

 Factorial (0) 1
 Factorial (1) Factorial (0)=1·1=1

 

El tercer paso: Calcular  Factorial (2) con la fórmula de recursividad:

Factorial(n)=n·Factorial(n-1) si n>0,  que es aplicable porque n =2>0

Factorial (0) 1
Factorial (1) 1·Factorial(0)=1·1=1
Factorial(2) 2·Factorial(1)=2·1=2

 

El cuarto paso: Calcular  Factorial (3) con la fórmula de recursividad:

Factorial(n)=n·Factorial(n-1) si n>0,  que es aplicable porque n =3>0

 Factorial (0) 1
 Factorial (1)
Factorial (0)=1·1=1
 Factorial (2) Factorial (1)=2·1=2
 Factorial (3) Factorial (2)=3·2=6

 

 

 

Be Sociable, Share!

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Instinto Lógico © 2014 Frontier Theme