¿Cómo resolver recursividad

recursividad es un concepto poderoso en el campo de la informática, pero puede ser difícil para los principiantes a comprender . Recursión implica una función o método que invocar repetidamente en sí en un contexto diferente hasta que se alcanza y se devuelve un contexto " de base " . En otras palabras , para resolver un problema , el programa recontexualizes como un problema ligeramente diferente . Cuando se implementa un algoritmo recursivo , considerar siempre la forma más simple del problema y establecer este ejemplo simplificado, " caso base ", que todas las demás versiones del problema harán referencia . Instrucciones
1

Defina la cabecera de una función - el nombre de la función y sus insumos. Por ejemplo , una función que encuentra un número Fibonacci particular podría tener el siguiente aspecto :

fib ( int n ) { }

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

Anote cómo se llama a la función genérica . Por ejemplo , cuando se llama a fib ( ) , se utiliza 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 de base. Como la secuencia de Fibonacci requiere dos números , tendrá dos casos base para implementar su solución

if ( n == 0 ) return 0; . If ( n == 1 ) return 1 ;

4

Definir el paso recursivo de su problema de recursión como una versión más pequeña , más simple del mismo problema , haciendo referencia al ejemplo de invocación de la Etapa 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 los dos números anteriores en la secuencia . Por tanto, el algoritmo para encontrar un número Fibonacci particular debe invocarse a sí mismo dos veces, una para el número anterior y una vez para el número antes de que el número anterior :

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

regreso resultado1 + result2 ;
5

Poner la función en conjunto, por ejemplo :

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

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

regreso resultado1 + result2 ;} }

la estructura del " caso base " y " paso recursivo " será el mismo para todas las funciones recursivas , aunque puede haber varios casos base y los pasos recursivos largo.