Exportar (0) Imprimir
Expandir todo

Recursividad

La recursividad es una técnica importante de programación que permite que una función se llame a sí misma. Como ejemplo útil se puede presentar el cálculo de números factoriales. El factorial de 0 está definido específicamente como 1. El factorial de n, un entero mayor que 0, es el producto de todos los enteros del intervalo comprendido entre 1 y n.

Utilizar recursividad

El siguiente párrafo muestra una función, expresada con palabras, que calcula un factorial.

"Si el número es menor que cero, se rechaza. Si no es un entero, se rechaza. Si el número es cero, su factorial es uno. Si el número es mayor que cero, se multiplica por el factorial del número menor inmediato".

Para calcular el factorial de cualquier número mayor que cero debe calcular como mínimo el factorial de otro número. La función debe llamarse a sí misma para el siguiente número menor antes de que se pueda ejecutar en el número actual, lo cual constituye un ejemplo de recursividad.

La recursividad y la iteración (recorrido en bucles) están íntimamente relacionadas: una función puede devolver los mismos resultados con recursividad o con iteración. Normalmente, un cálculo determinado se prestará a una técnica u otra; sólo deberá elegir el enfoque más natural o el que más le guste.

A pesar de la utilidad de la recursividad, es fácil crear una función recursiva que no devuelva nunca un resultado y no llegue a un extremo. Este tipo de recursividad hace que el sistema ejecute un bucle infinito. Por ejemplo, omita la primera regla (la de los números negativos) de la descripción verbal del cálculo de un factorial e intente calcular el factorial de un número negativo. Se produce un error, ya que para calcular el factorial de -24, por ejemplo, hay que calcular el factorial de -25. Para calcular el factorial de -25, hay que calcular primero el factorial de -26, y así sucesivamente. Obviamente, el bucle nunca se detendrá.

Otro problema que puede surgir con la recursividad es que la función recursiva utilice todos los recursos disponibles (como la memoria del sistema y el espacio de la pila). Cada vez que una función recursiva se llama a sí misma (o llama a otra función que llama a la función original), utiliza algunos recursos. Estos recursos se liberan cuando la función recursiva termina, pero una función que tenga demasiados niveles de recursividad podría utilizar todos los recursos disponibles. Cuando esto sucede, se produce una excepción.

Por tanto, es importante cuidar el diseño de las funciones recursivas. Si sospecha que existe la posibilidad de una recursividad excesiva o infinita, diseñe la función de forma que cuente el número de veces que se llama a sí misma y establezca un límite en el número de llamadas. Si la función se llama a sí misma más veces que el umbral definido, puede hacer que la función termine automáticamente. El número máximo óptimo de iteraciones depende de la función recursiva.

Aquí está de nuevo la función del factorial, pero esta vez escrita en JScript. Se utiliza la anotación de tipo para que la función sólo acepte enteros. Si se pasa un número no válido (es decir, un número menor que cero), la instrucción throw genera un error. En caso contrario, se utiliza una función recursiva para calcular el factorial. La función recursiva utiliza dos argumentos, uno para el argumento factorial y otro para el contador que realiza un seguimiento del nivel de recursividad actual. Si el contador no alcanza el nivel máximo de recursividad, se devuelve el factorial del número original.

function factorialWork(aNumber : int, recursNumber : int ) : double {
   // recursNumber keeps track of the number of iterations so far.
   if (aNumber == 0) {  // If the number is 0, its factorial is 1.
      return 1.;
   } else {
      if(recursNumber > 100) {
         throw("Too many levels of recursion.");
      } else {  // Otherwise, recurse again.
         return (aNumber * factorialWork(aNumber - 1, recursNumber + 1));
      }
   }
}

function factorial(aNumber : int) : double {
   // Use type annotation to only accept numbers coercible to integers.
   // double is used for the return type to allow very large numbers to be returned.
   if(aNumber < 0) {
      throw("Cannot take the factorial of a negative number.");
   } else {  // Call the recursive function.
      return  factorialWork(aNumber, 0);
   }
}

// Call the factorial function for two values.
print(factorial(5));
print(factorial(80));

El resultado de este programa es:

120
7.156945704626378e+118

Vea también

Adiciones de comunidad

AGREGAR
Mostrar:
© 2014 Microsoft