Comprender la recursividad y la fórmula recursiva

Iteración

La iteración es la repetición de un proceso. Un estudiante que va a la escuela repite el proceso de ir a la escuela todos los días hasta la graduación. Vamos al supermercado al menos una o dos veces al mes para comprar productos. Repetimos este proceso todos los meses. En matemáticas, una secuencia de Fibonacci también sigue las propiedades de la repetición de tareas. Consideremos la secuencia de Fibonacci donde los dos primeros números son 0 y 1, todos los demás números son la suma de los dos números anteriores.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Pasos de iteración

La fórmula de Fibonacci se puede escribir como,

F (norte) = F (norte - 1) + F (norte - 2)
fibonacci (0) = 0
fibonacci (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8

El algoritmo que se muestra a continuación devuelve el número n de Fibonacci.

Recursividad

Cada vez que obtenemos un nuevo número de Fibonacci (n-ésimo número), ese n-ésimo número es en realidad (n - 1) el número cuando encontramos (n + 1) el Fibonacci como nuestro próximo n-ésimo Fibonacci. Como vemos los pasos de iteración mencionados anteriormente: si n = 2 entonces
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1

Ahora, queremos generar fibonacci (3), que es n = 3.

Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Eso significa que cada vez que n aumenta el valor de la corriente (n - 1) th y (n - 2) th fibonacci también aumenta. Pero es agotador hacer un seguimiento de (n - 1) ésimo y (n - 2) ésimo de fibonacci para cada n. ¿Qué tal escribir un método que se llame a sí mismo para repetir la tarea de iteración por sí mismo?

Un método que se llama a sí mismo se denomina método recursivo. Un método recursivo debe tener un caso base en el que el programa deje de llamarse a sí mismo. Nuestro caso base para la serie Fibonacci es fibonacci (0) = 0 y fibonacci (1) = 1. De lo contrario, el método Fibonacci se llama a sí mismo dos veces: fibonacci (n - 1) y fibonacci (n - 2). Luego los agrega para obtener fibonacci (n). Un método recursivo para encontrar n-ésimo Fibonacci se puede escribir como:

Si miramos con atención, la recursividad sigue la propiedad de la pila. Resuelve subproblemas más pequeños para obtener la solución de un problema. Para n> 1, ejecuta la última línea. Entonces, si n = 6, la función llama y agrega fibonacci (6 - 1) y fibonacci (6 - 2). fibonacci (6 - 1) o fibonacci (5) llama y agrega fibonacci (5 - 1) y fibonacci (5 - 2). Esta recursión continúa hasta que 6 llega a su valor de caso base, que es fibonacci (0) = 0 o fibonacci (1) = 1. Una vez que llega al caso base, agrega dos valores base y aumenta hasta obtener el valor de fibonacci ( 6). A continuación se muestra una representación en árbol de la recursividad.

árbol de recursividad

Como podemos ver, cuán poderosa puede ser una recursividad. Solo una línea de código forma el árbol de arriba (la última línea del código de arriba incluye los casos base). La recursividad mantiene una pila y se profundiza hasta llegar al caso base. Programación dinámica (DP): la recursividad es fácil de entender y codificar, pero puede ser costosa en términos de tiempo y memoria. Eche un vistazo al árbol de recursividad a continuación. El subárbol izquierdo que comienza con fib (4) y el subárbol derecho que comienza con fib (4) son exactamente iguales. Generan el mismo resultado que es 3 pero están haciendo la misma tarea dos veces. Si n es un número grande (ejemplo: 500000), la recursividad puede hacer que un programa sea muy lento, ya que llamaría a la misma subtarea varias veces.

recursividad en un círculo

Para evitar este problema, se puede utilizar la programación dinámica. En programación dinámica podemos usar subtareas previamente resueltas para resolver futuras tareas del mismo tipo. Esta es una forma de reducir la tarea para resolver el problema original. Tengamos una matriz fib [] donde almacenamos soluciones de subtareas previamente resueltas. Ya sabemos que fib [0] = 0 y fib [1] = 1. Guardemos estos dos valores. Ahora, ¿cuál es el valor de fib [2]? Como fib [0] = 0 y fib [1] = 1 ya se han almacenado, solo tenemos que decir fib [2] = fib [1] + fib [0] y eso es todo. Podemos generar fib [3], fib [4], fib [5], ……, fib [n] de la misma manera. Las subtareas previamente resueltas se llaman para obtener la siguiente subtarea hasta que la tarea original no se haya resuelto, por lo que se reduce el cálculo redundante.