Cómo resolver recursividad

La recursividad es un concepto de gran alcance en el campo de la informática, pero puede ser difícil para los novatos de entender. La recursividad implica una función o método que invoca en repetidas ocasiones en un contexto diferente hasta un contexto "base" se alcanza y se devuelve. En otras palabras, para resolver un problema, el programa recontexualizes como un problema ligeramente diferente. Cuando se implementa un algoritmo recursivo, siempre tenga en cuenta la forma más sencilla del problema y establecer este ejemplo simplificado, "caso base", que harán referencia a todas las demás versiones del problema.

Instrucciones

1 Defina la cabecera de una función - El nombre de la función y de sus entradas. Por ejemplo, una función que encuentra un determinado número de Fibonacci puede tener un aspecto como sigue:

fib (int n) {}

Aquí, la función calcula el número "n-ésimo" Fibonacci en la secuencia.

2 Escribe cómo la función se denomina genéricamente. Por ejemplo, cuando se llama a fib (), que va a utilizar un entero como argumento y registrar el número entero que se calcula:

int resultado = fib (x);

3 Definir el "caso base" de su problema de recursividad. Puede haber múltiples casos base. Como la secuencia de Fibonacci requiere dos números, necesitará dos casos base para implementar su solución.

si (n == 0) return 0;
si (n == 1) return 1;

4 Definir la etapa recursiva de su problema de la recursividad como una versión más pequeña y más simple del mismo problema, haciendo referencia al ejemplo de invocación desde el Paso 2. En nuestro ejemplo, la secuencia de Fibonacci es una secuencia matemática, donde cada número en la línea es la suma de las anteriores dos números en la secuencia. El algoritmo para encontrar, por tanto, un número de Fibonacci particular debe invocarse a sí mismo dos veces, una para el número anterior y una vez para el número antes del número anterior:

int resultado1 = fib (n-1);
int result2 = fib (n-2);

resultado1 + result2 regresar;

5 Poner la función en conjunto, por ejemplo:

fib (int n) {
si (n == 0) return 0; // Caso base 1
else if (n == 1) return 1; // Caso base 2

else {// etapa recursiva
int resultado1 = fib (n-1);
int result2 = fib (n-2);

resultado1 + result2 regresar;
}

}

La estructura del "caso base" y "paso recursivo" será el mismo para todas las funciones recursivas, aunque puede haber múltiples casos base y pasos largos recursivas.

Consejos y advertencias

• Para ayudarle a visualizar una solución recursiva, caminar a través de entradas y retornos con un problema de muestra del programa.
• No importa cómo se implementa su función, siempre debe devolver la cubierta base en algún momento durante la ejecución de su programa. De lo contrario, la función nunca dejará de llamar sí mismo!