¿Cuál es la mejor manera de depurar un algoritmo recursivo?

No existe una diferencia real entre depurar un algoritmo recursivo y depurar cualquier otro algoritmo.

Por lo general, un algoritmo recursivo tiene tres partes:

1. La parte que convierte el problema en un problema menor.
2. La parte que trata con uno o más casos triviales del problema.
3. La parte que trata con el estado de error.

Entonces, comenzaría pasando la entrada que se ocupa del n. ° 1 y n. ° 2: entrada que es pequeña, pero no del todo trivialmente pequeña. Asegúrese de que trata de convertir el problema en un problema más pequeño correctamente. Asegúrese de que trata con un caso trivial correctamente. Luego mire la sección de error y asegúrese de que la entrada incorrecta se trate correctamente.

(Hay advertencias: es posible que esté recordando sus resultados, lo que sería otra cosa que debe verificar. Es posible que esté llegando a un límite en la profundidad de la pila, lo cual es una realidad desafortunada cuando usa la recursión en muchos idiomas. Puede estar haciendo algo que no No funciona si estaba usando recursividad o no, como tratar de calcular 100 factorial y devolverlo como un entero de 32 bits).

Una excelente manera de investigar los problemas en los algoritmos recursivos es reducir el orden de la entrada hasta que el problema desaparezca.
Un algoritmo recursivo funciona resolviendo el problema P (n) resolviendo un conjunto de subproblemas similares P (n-1) que se resuelven resolviendo más (conjuntos) P (n-2) y así sucesivamente. Si se da cuenta de que la salida de P (n) es incorrecta, simplemente verifique los resultados en el conjunto P (n-1). Si son correctos, entonces debe observar de cerca la lógica que los une para resolver P (n). De lo contrario, mire más allá de los que están mal. Al mirar hacia abajo el tramo de “error” de la recursión, eventualmente encontrará el problema.

Una excelente manera de probar un algoritmo recursivo (o cualquier algoritmo) es implementar otra forma (digamos iterativa) del mismo algoritmo y lanzar una batería de casos de prueba a ambos y verificar que los resultados sean iguales. A menudo es fácil realizar cientos de miles (incluso millones) de pruebas en una implementación de esa manera. Calcular a mano incluso unos pocos cientos de casos de prueba de cualquier complejidad normalmente está completamente fuera de discusión.
A menudo hay una implementación ‘simple’ que es mucho más fácil ‘probar’ que es correcta y luego puede usarse para validar una forma más rápida pero más compleja.

También busque invariantes que puedan verificarse. La mejor manera de probar cualquier algoritmo de clasificación serio es arrojar un montón de casos de prueba. Algunos deben formarse a mano para garantizar la cobertura del código, pero la mayoría podrían ser casos aleatorios generados por máquina. Su script de prueba puede verificarlos todos verificando que el resultado esté realmente ordenado. No necesita “saber” la respuesta a muchos casos en absoluto …

Por lo general, no desea depurar un algoritmo recursivo que es difícil de seguir después de cierto tiempo. Pero en caso de que aún tenga que hacer lo mismo, sugeriría escribir los parámetros en cuestión y el número de iteración como un registro en un archivo.

Puede escribir un conjunto de aserciones que se adjuntan en varios puntos del programa. Cada vez que el programa se ejecuta más allá del punto de prueba, se verifica la aserción. Adjunte aserciones en el punto de inicialización para asegurarse de que el algoritmo se inicie con el valor corregido y adjunte una aserción en el punto de avance cuando el siguiente valor se deriva del anterior.

Si hay algún error en el programa se detectará muy pronto.