¿Cómo funciona esta función recursiva?

Creo que la mejor manera de entender esta función es visualizarla como un gráfico:


Esta es una función recursiva que genera todas las permutaciones de sumar +5 o multiplicar * 3 al número anterior. Se detiene cuando encontramos 24.

Comenzamos en 1. Luego hacemos un primer recorrido profundo prefiriendo +5 sobre * 3, hasta encontrar 24.

Para ver por qué esto es correcto, solo mira los casos en nuestra función recursiva:

  • si estamos en nuestro número objetivo, pare y regrese el historial
  • si estamos por encima de nuestro número objetivo, pare
  • Si estamos por debajo de nuestro número objetivo, primero baje por la ruta +5. Si esto devuelve nulo, vaya por la ruta * 3. Esto es básicamente la profundidad primero.

Puede ver el script de Python que utilicé para generar el gráfico aquí findsequence.py.

El objetivo es tratar de encontrar una manera de llegar de 1 a la meta solo sumando cinco o multiplicando por 3.
La función realmente intenta todas las rutas posibles hasta que una tiene éxito o todas fallan (porque todas conducen a números más grandes que el objetivo).

Cuando llamas a findSequence (24), este es el historial de llamadas.

  1 -> 6 (+5)
     -> 11 (+5)
       -> 16 (+5)
         -> 21 (+5)
           -> 26 // descartado
         -> 63 // descartados
       -> 48 (* 3) // descartado
     -> 33 // descartados
   -> 3 (* 3)
    -> 8
      -> 13
       -> 18
         -> 23
           -> 28 // descartado
         -> 69 // descartado
       -> 54 // descartado
      -> 24 // gol!  devolvemos el historial actual: ((1 * 3) +5) * 3

Primero intenta agregar 5 hasta que exceda 24. Cuando esto falla, reemplaza algunos +5 por * 3 y repite el proceso.

Intente poner en un papel la ejecución del programa (al menos para las primeras llamadas), ayuda a comprender la recursividad.

More Interesting

¿Cuáles son las cosas importantes que debe tener en cuenta al hacer un diseño web receptivo?

¿Es el desarrollo web front-end una carrera profesional lucrativa?

¿Cuáles son las mejores empresas de consultoría de negocios y desarrollo web en el área de Columbia, MD?

¿Debería centrarme en el desarrollo de stack completo ya que tengo 2 años de experiencia en frameworks Java y JS o elegir tecnologías avanzadas como IA, aprendizaje automático o big data?

Cómo ejecutar un script PHP a una hora específica del día

¿Debo usar PHP HHVM + Apache2 o PHP7 + Apache2 o HHVM + NginX o PHP7 + Nginx para obtener el mejor rendimiento?

¿Es imprudente guardar los componentes HTML / CSS / JavaScript que he usado en sitios que he creado para usarlos más tarde?

Cómo construir un sistema de rastreo de bus usando GPS (o geolocalización HTML5), PHP y MySQL

¿Aprender full stack y algoritmos es un boleto para las principales empresas de la India?

¿Qué es un marco de juego JS simple con sprite.js?

Si Facebook eligiera reconstruir su aplicación web en parte en ASP.NET, ¿cuáles serían los beneficios y las desventajas?

¿Qué información debo ingresar al hacer un sitio web y luego venderlo?

¿Hay futuro para los desarrolladores web front-end? Mi pregunta es específicamente sobre: ​​1) Aumento de salario basado en la experiencia y 2) Potencial de crecimiento dentro de una empresa.

¿Un sitio web diseñado con las versiones más recientes de html y CSS proporcionaría la mejor accesibilidad general para el mayor número de usuarios?

¿Cómo podemos usar el concepto de manejo de archivos de C ++ en HTML con PHP?