Recursión lo básico 1


Recursión lo básico

 

COMPUT:  una técnica de programación en que una rutina realiza su tarea delegando parte de ella a otra instancia de sí misma.

Introducción

Para los nuevos estudiantes de informática, el concepto de la programación recursiva es a menudo difícil. El pensamiento recursivo es difícil porque casi parece un razonamiento circular. Tampoco es un proceso intuitivo, cuando damos instrucciones a otras personas, rara vez lo hacemos de forma recursiva.

Para aquellos ustedes que son nuevos en la programación de ordenadores, resumimos una definición simple de recursividad: recursividad se produce cuando una función se llama a sí misma, directa o indirectamente.

Un ejemplo clásico de la recursividad

El ejemplo clásico de la programación recursiva implica factoriales de computación. En matemáticas, el factorial de un entero no negativo,  n  (denotado  n !) es el producto de todos los enteros positivos menores o iguales a  n . Por ejemplo,  5!  es lo mismo que 5 * 4 * 3 * 2 * 1, y  3!  es 3 * 2 * 1.

Una propiedad interesante de un factorial es que el factorial de un número es igual al número inicial multiplicado por el factorial del número inmediatamente debajo de él. Por ejemplo, 5! es lo mismo que 5 * 4! Casi se podría escribir la función factorial como:

int factorial(int n)
{
   return n * factorial(n - 1);
}

Listing 1. First cut factorial function

Sin embargo, hay un pequeño problema con esto, se ejecuta siempre, porque no hay ningún lugar donde se detenga el llamado a sí misma. Por lo tanto, se necesita una condición para decirle que se detenga. Un factorial para los números positivos sólo tiene sentido detener la recursión cuando la entrada es 1, y devuelve 1 como resultado. El código modificado se verá así:

int factorial(int n)
{
   if(n == 1)
   {
      return 1;
   }
   else
   {
      return n * factorial(n - 1);
   }
}

Listing 2. better factorial function

Como puede verse, cuando se llegue al valor 1 esta función terminará.

El punto en el que se detiene  la recursión se llama -caso base-. En el caso de un factorial cuando 1! = 1. Todos los programas recursivos deben tener por lo menos un caso base y deben garantizar que van a llegar a uno en algún momento, de lo contrario el programa se ejecutaría para siempre o hasta que el programa se quede sin memoria o espacio en el stack.

recursion

Basic steps of recursive programs
All recursive programs follows the same basic sequence of steps:
1: Initialize the algorithm. Recursive programs often need a seed value to start with.
2: Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3: Redefine the answer in terms of a smaller or simpler sub-problem or sub-problems.
4: Run the algorithm on the sub-problem.
5: Combine the results in the formulation of the answer.
6: Return the results.

 

Advantages and drawbacks of recursion

Main advantage of recursion is programming simplicity. When using recursion, programmer can forget for a while of the whole problem and concentrate on the solution of a current case. Then, returning back to the whole problem, base cases (it’s possible to have more than one base case) and entry point for recursion are developed.

On the other hand, recursion has a serious disadvantage of using large amount of memory. Moreover, for most programming languages, recursion use stack to store states of all currently active recursive calls. The size of a stack may be quite large, but limited. Therefore too deep recursion can result in Stack Overflow. To resolve this problem recursion can be simulated, using loop and stack data structure.


Dejar un Comentario

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

Un comentario en “Recursión lo básico