Aquí hay un algoritmo recursivo simple en un pseudocódigo
vacío printTo (int current, int max) {
if (actual <max) {
printLine (actual)
corriente + = 1
printTo (actual, máx.)
}
regreso
}
Ahora digamos que lo llamamos así:
- ¿Alguien podrá escribir un algoritmo que pueda hacer dinero en el mercado durante un período de 20 años?
- ¿Cuál es la altura, el tamaño y la profundidad de un árbol binario?
- ¿Qué significa: = significa en algoritmos?
- ¿En cuánto tiempo puedo ser un profesional en la resolución de problemas en algoritmos y estructuras de datos si empiezo hoy sin ningún conocimiento previo?
- ¿Cuáles son los algoritmos más utilizados en los que puedo confiar para mejorar mis habilidades de resolución de problemas?
printTo (1, 10)
La primera vez que se llama a la función, los valores son
corriente = 1, max = 10
Como la corriente es menor que la condición máxima en la línea 2, continuamos en la línea 3 Imprimimos el valor de la corriente (que es uno), luego en la línea 4 incrementamos la corriente y en la línea 5 llamamos a la función printTo (en la que estamos actuales ) con los valores (2, 10).
Ahora ingresamos a la función printTo y volvemos a la línea 2. Como 2 es menor que 10, pasamos a la línea 3. Imprimimos el valor de current (que ahora es 2), luego incrementamos la corriente y llamamos a printTo nuevamente. Esto continuará hasta que la corriente sea igual a 10.
Cuando esto sucede, el condicional en la línea 2 devolverá falso (ya que 10 no es menor que 10) y omitiremos el bloque de código y terminaremos en la línea 7 donde volveremos de la llamada a la función actual.
Cuando volvemos, transferimos el control de la llamada con los argumentos (10, 10) a la que tiene los argumentos (9, 10) y luego (8, 10) … y así sucesivamente hasta que volvamos a nuestra llamada original (que llamó con (1,10)) y listo.
¿La salida?
1
2
3
4 4
5 5
6 6
7 7
8
9
Imprimimos los valores del 1 al 9 (no imprimimos 10 porque la condición para imprimir solo ocurre cuando tenemos menos de 10.
Pero ahora, ¿qué sucede si cambiamos ligeramente la función?
vacío printTo (int current, int max) {
if (actual <max) {
corriente + = 1
printTo (actual, máx.)
printLine (actual)
}
regreso
}
¿Qué pasa si no imprimimos hasta después de nuestra llamada recursiva?
Bueno, no hacemos estas llamadas (1,10), (2, 10), (3, 10) … (10, 10)
En (10,10) saltamos al retorno y volvemos a nuestra llamada al (9,10), y ENTONCES imprimimos el valor 9. Luego regresamos a (8,10) e imprimimos el valor 8. Luego a ( 7,10) e imprima el valor 7 … y así sucesivamente.
El resultado ahora es:
9
8
7 7
6 6
5 5
4 4
3
2
1
Ese es un comportamiento interesante!
Cambiar el orden del comportamiento de “hacer nuestra acción y luego recurrir” a “recurrir y luego hacer nuestra acción” invirtió el orden en el que realizamos la acción.
Esta táctica de cambiar el orden de cuándo repetimos frente a cuándo hacemos la acción es muy poderosa y hace que algunos cambios de comportamiento significativos sean muy fáciles de implementar. Un gran ejemplo de esto se puede ver en recorridos recursivos de árboles en los que el orden de las operaciones puede cambiar el comportamiento de preordenar, en orden y en orden posterior con solo un simple cambio.
