El ejemplo clásico de recursividad implica factoriales computación. Un factorial es el producto de cualquier número entero positivo dado multiplicado por todos los números enteros menores. El factorial de 5 es 5 * 4 * 3 * 2 * 1 , el factorial de 4 es 4 * 3 * 2 * 1 y así sucesivamente . El factorial de cualquier número es igual al número multiplicado por el factorial del número inmediatamente debajo de él . En otras palabras , factorial ( 5 ) es lo mismo que 5 * factorial ( 4 ) , factorial ( 4 ) es el mismo que 4 * factorial ( 3 ) y así sucesivamente , por lo que una función factorial simple podría ser escrito como :
int factorial ( int n) {return n * factorial ( n - 1 ) ;}
Base Case
El problema con esta función simple, sin embargo, es que no tiene ningún caso base, o condiciones de decir que cuando parar. En la actualidad, la función seguirá llamándose cuando n llegó a cero y más allá de los números negativos , volviendo factoriales sin sentido . En realidad, una función factorial tiene que parar cuando n = 1 , por lo que una función factorial real podría ser escrito como :
int factorial ( int n) {if (n == 1 ) {return 1 ; } else { regreso n * factorial ( n - 1 ) ; } }
En Inglés , la función examina el número se le ha pasado como un parámetro y , si el número es 1 , devuelve 1 . De lo contrario la función devuelve el número multiplicado por el factorial del número menos uno.
Programa Pila
Todos los programas recursivos deben tener un punto inferior , o base caso, en que la operación es tan trivial que una respuesta puede ser devuelto directamente . La recursividad funciona mediante la adición de , o empujar , y la eliminación de , o hacer estallar, fotogramas individuales hacia y desde una estructura de datos conocida como una pila del programa . Sólo hay una cantidad limitada de espacio en la pila del programa , por lo que , sin un caso base, un programa recursivo simplemente sigue corriendo hasta que la pila se desbordó .
Pros y Contras
recursividad es difícil de entender , ya que no es intuitivo y puede parecer , a primera vista, para involucrar a la lógica circular o falsa . Según IBM , la recursividad es raramente utilizado por los programadores de lenguajes de programación imperativos - que no especifican una secuencia explícita de pasos para realizar - porque creen que es lento y desperdicia espacio . Sin embargo , si se aplica correctamente , la recursividad es una técnica de programación potente que puede simplificar algunas tareas de programación .