Funcion recursiva
una función recursiva, cuando hablamos de programación, es una función que dentro de ella, se llama a si misma, y para evitar que se ejecute de manera indefinida, se le agrega ademas, una condición para hacer que su ejecución se detenga en un momento.
esta función "recursiva" resuelve problemas de manera recursiva, osea, divide el problema en instancias cada vez mas pequeñas, mas fáciles de resolver, hasta que se llega a un momento donde la condición se cumple y su ejecución termina (ese caso se lo conoce como "caso base").
el ejemplo mas común es el de la factorizacion de números.
cuando factorizamos un numero, lo que estamos haciendo es obtener otro numero como resultado. Ese numero, representa la cantidad de combinaciones que podemos hacer con los números que hay detrás del numero a factorizar,
un ejemplo para que se aclare.
si queremos factorizar el 5, nosotros sabemos que...
5! = 5x4x3x2x1= 120
120 vendrian a ser la cantidad de combinaciones que podemos hacer con
este conjunto de numeros -----> (5, 4, 3, 2, 1)
una de esas combinaciones seria ----> (3, 4, 1, 5, 2)
entonces, eso es lo que se obtiene del factorial de un numero.
5! = 5x4x3x2x1 = 120
podemos notar que al calcular el factorial, como todos los numeros se multiplican, podemos agruparlos asi 5x(4x3x2x1) y el resultado sera el mismo
por lo tanto, se puede sacar el factorial de 4 y luego a ese numero multiplicarlo por 5, en este caso, hemos partido el problema en 2 partes mas simples.
de la misma manera podremos hacer 5x4x(3x2x1)
5x4 = 20 x 3! = 120 (multiplicamos 5 x 4 y al resultado lo multiplicamos por el factorial de 3, es mucho mas sencillo)
teniendo esto en cuenta, podemos definir el factorial de un numero de manera recursiva, asi:
𝑛 ∗ 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 (𝑛 − 1) solo mientras n sea mayor a 0.
(n es el numero al que le queremos calcular el factorial) si seguimos esa definicion tenemos que...
5 x (5 -1)! lo mismo que 5 x 4!
la función factorial recibe como parámetro el numero 3, es analizada la condición y como no se cumple, sigue.
luego la variable factorial es igualada al parámetro de la función por el factorial del parámetro de la función menos 1. a su vez, el parámetro (3-1) es pasado a la misma función y esta se vuelve a ejecutar pero con el parámetro 2, y así sucesivamente.
hasta que llega un momento en que el parámetro que se le pasa a la función sea 1, y se cumpla la condición (caso base), en ese momento la función resolvió el factorial de 1, que es igual a 1, retornara 1 a la instancia anterior y se comenzara a multiplicar por el numero que le sigue, y devolviendo los valores hacia atrás, hasta que la primera instancia sera la que finalmente devuelva el valor del factorial.
la función solo puede resolver el "caso base", osea el factorial de 1, que es cuando la condición se cumple, esa condición se la ponemos nosotros para evitar que se ejecute infinitamente.
si nosotros ingresáramos el 1 como parámetro a la función, la condición se cumpliría a la primera, y retornaría el valor 1, pero si ingresamos un 4, esto no sucede, la función no podría resolverlo y dividirá el problema en una instancia menor 4-1, 3-1. 2-1.
esta función "recursiva" resuelve problemas de manera recursiva, osea, divide el problema en instancias cada vez mas pequeñas, mas fáciles de resolver, hasta que se llega a un momento donde la condición se cumple y su ejecución termina (ese caso se lo conoce como "caso base").
el ejemplo mas común es el de la factorizacion de números.
cuando factorizamos un numero, lo que estamos haciendo es obtener otro numero como resultado. Ese numero, representa la cantidad de combinaciones que podemos hacer con los números que hay detrás del numero a factorizar,
un ejemplo para que se aclare.
si queremos factorizar el 5, nosotros sabemos que...
5! = 5x4x3x2x1= 120
120 vendrian a ser la cantidad de combinaciones que podemos hacer con
este conjunto de numeros -----> (5, 4, 3, 2, 1)
una de esas combinaciones seria ----> (3, 4, 1, 5, 2)
entonces, eso es lo que se obtiene del factorial de un numero.
5! = 5x4x3x2x1 = 120
podemos notar que al calcular el factorial, como todos los numeros se multiplican, podemos agruparlos asi 5x(4x3x2x1) y el resultado sera el mismo
por lo tanto, se puede sacar el factorial de 4 y luego a ese numero multiplicarlo por 5, en este caso, hemos partido el problema en 2 partes mas simples.
de la misma manera podremos hacer 5x4x(3x2x1)
5x4 = 20 x 3! = 120 (multiplicamos 5 x 4 y al resultado lo multiplicamos por el factorial de 3, es mucho mas sencillo)
teniendo esto en cuenta, podemos definir el factorial de un numero de manera recursiva, asi:
𝑛 ∗ 𝑓𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 (𝑛 − 1) solo mientras n sea mayor a 0.
(n es el numero al que le queremos calcular el factorial) si seguimos esa definicion tenemos que...
5 x (5 -1)! lo mismo que 5 x 4!
 |
| Ejemplo |
la función factorial recibe como parámetro el numero 3, es analizada la condición y como no se cumple, sigue.
luego la variable factorial es igualada al parámetro de la función por el factorial del parámetro de la función menos 1. a su vez, el parámetro (3-1) es pasado a la misma función y esta se vuelve a ejecutar pero con el parámetro 2, y así sucesivamente.
hasta que llega un momento en que el parámetro que se le pasa a la función sea 1, y se cumpla la condición (caso base), en ese momento la función resolvió el factorial de 1, que es igual a 1, retornara 1 a la instancia anterior y se comenzara a multiplicar por el numero que le sigue, y devolviendo los valores hacia atrás, hasta que la primera instancia sera la que finalmente devuelva el valor del factorial.
la función solo puede resolver el "caso base", osea el factorial de 1, que es cuando la condición se cumple, esa condición se la ponemos nosotros para evitar que se ejecute infinitamente.
si nosotros ingresáramos el 1 como parámetro a la función, la condición se cumpliría a la primera, y retornaría el valor 1, pero si ingresamos un 4, esto no sucede, la función no podría resolverlo y dividirá el problema en una instancia menor 4-1, 3-1. 2-1.
 |
| ejemplo en java |
Comentarios
Publicar un comentario