1 Recursividad

2 2 Son funciones que se llaman a sí mismas. Requisitos: – Deben retornar un valor. – Deben tener expresiones en las que se llaman a sí mismas: “ciclo activo”. – Deben incluir, en una sentencia de selección, una opción en la cual terminen la ejecución y no se llamen a sí mismas: “caso base”. – Si no poseen un opción que les permita terminar su ejecución, se producirán llamadas hasta agotar los recursos de memoria del sistema. – Si se alcanza el “caso base” en una llamada del “ciclo activo”, entonces se inicia el “ciclo pasivo” o de retorno.

3 3 Recursividad código C tipo_de_retorno nombre_funcion(tipo argumentos){ if ( caso_base ) return valor_base; else {................ return nombre_funcion(argumentos'); }

4 4 Recursividad (ejemplo) Obtener el factorial de un número Casos base: - el factorial de cero es uno - factorial de uno es uno - factorial de un número negativo lo hacemos cero. Ciclo activo: - llamar a partir del número en forma descendente hasta llegar al caso base.

5 5 Recursividad (Ejemplo cont.) #include int factorial(int n){ if (n

6 main(){ int x = 3; fac = factorial(x); 6 Simulación: ciclo activo

7 main(){ int x = 3; fac = factorial(x); 7 Simulación: ciclo activo factorial(3);

8 main(){ int x = 3; fac = factorial(x); 8 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1);

9 main(){ int x = 3; fac = factorial(x); 9 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2);

10 main(){ int x = 3; fac = factorial(x); 10 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1);

11 main(){ int x = 3; fac = factorial(x); 11 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1); 2*factorial(1);

12 main(){ int x = 3; fac = factorial(x); 12 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1); 2*factorial(1); factorial(1){ if (1==0) return 1; else if (1==1) return 1;

13 main(){ int x = 3; fac = factorial(x); 13 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1); 2*factorial(1); factorial(1){ if (1==0) return 1; else if (1==1) return 1; return 1

14 main(){ int x = 3; fac = factorial(x); 14 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1); 2*factorial(1); factorial(1){ if (1==0) return 1; else if (1==1) return 1; return 1 Caso Base alcanzado!!

15 main(){ int x = 3; fac = factorial(x); 15 Simulación: ciclo activo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1); 2*factorial(1); factorial(1){ if (1==0) return 1; else if (1==1) return 1; return 1

16 main(){ int x = 3; fac = factorial(x); 16 Simulación: ciclo pasivo factoria l(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2 ); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2*factorial(2-1); 2*1

17 main(){ int x = 3; fac = factorial(x); 17 Simulación: ciclo pasivo factoria l(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*factorial(2); factorial(2){ if (2==0) return 1; else if (2==1) return 1; else return 2;

18 main(){ int x = 3; fac = factorial(x); 18 Simulación: ciclo pasivo factoria l(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 3*factorial(3-1); 3*2

19 main(){ int x = 3; fac = factorial(x); 19 Simulación: ciclo pasivo factorial(3); factorial(3){ if (3==0) return 1; else if (3==1) return 1; else return 6;

20 main(){ int x = 3; fac = factorial(x); 20 Simulación: ciclo pasivo 6;