1 Ing. Betty Suárez TorresRECURSIVIDAD Ing. Betty Suárez Torres

2 CONCEPTOS BÁSICOS La recursividad es la propiedad que poseen determinadas funciones por la cual pueden llamarse a sí mismas. Toda función/método recursivo debe tener dos partes: Una parte de terminación en la que se deja de hacer llamadas (caso base) y que constituye la condición de terminación de la función, permitiendo así que no se produzca una recursión infinita. Y una llamada recursiva con sus propios parámetros, en los que éstos sufrirán alguna variación. Cuando una función se llama así misma, se denomina función recursiva y a la llamada a sí misma es llamada recursiva. Puede ser utilizada como alternativa a la repetición o estructura repetitiva.

3 EJEMPLO FACTORIAL 5! 5! Devuelve 5! = 5 * 24 = 120 5*4! 5*4!El factorial de un número entero postiivo n (n!) es el producto: n * (n-1) * (n-1) * … * 1 Si el número es menor o igual a 1, la función factorial devuelve 1 EJEMPLO FACTORIAL 5! 5! Devuelve 5! = 5 * 24 = 120 5*4! 5*4! Devuelve 4! = 4 * 6 = 24 4*3! 4*3! Devuelve 3! = 3 * 2 = 6 3*2! 3*2! Devuelve 2! = 2 * 1 = 2 2*1! 2*1! Devuelve 1 1 1

4 FACTORIAL C++ Factorial long Factorial (int n) { if (n<=1)return 1; else return (n*Factorial(n-1)); }

5 EJEMPLO FIBONACCI Serie de Fibonacci: 0 1 1 2 3 5 8 13 21 34 55 89 ….Definida de manera recursiva: Fibonacci(0) = 0 Fibonacci(1) = 1 Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2) = 0

6 Fibonacci(3) return Fibonacci(2) + Fibonacci(1) return Fibonacci(1) Fibonacci(0) return 1 + return 1 return 0

7 Fib(6) = Fib(4) + Fib(5)= Fib(2) + Fib(3) + Fib(5)== 8

8 EJEMPLO RECURSIÓN MÚLTIPLE : SUCESIÓN DE FIBONACCILa ecuación que describe la sucesión de Fibonacci (fib) es: fib(0) = 0 fib(1) = 1 fib(n) = fib(n - 1) + fib(n - 2) long fib(long n) { if ((n==0) || (n==1)) return (n) ; else return(fib(n-1)+fib(n-2)); }

9 EJEMPLO: MULTIPLICACION DE NÚMEROS NATURALESEl producto de dos números es : A SI B=1 A * (B – 1) + A SI B>1 Ejemplo: Evaluar 6 * 3: 6 * 3 = 6 * = 6 * = = 18

10 MÁXIMO COMÚN DIVISOR int MCD(int M, int N); int MCD(int M, int N){int v; if(M%N==0) v=N; else v = MCD(N,M%N); return v; } void main(){ int M,N; cout<<"Ingresar primer número:"; cin>>M; cin>>N; cout<<"El máximo común divisor es: "< getch(); }

11 RECURSIVIDAD INDIRECTA#include int par(int n) ; int impar(int n); int main (void){ int n; do{ printf ("\nEntero > 0: " ) ;scanf ("%d", &n) ; } while (n<=0); if (par(n)) printf("El numero %d es par”,n); else return 0; printf("El numero %d es impar”,n) ; } int par(int n){ if (n == 0) return 1; else return impar(n-1); } int impar(int n){ return 0; return par(n-1); }

12 EJEMPLO: TORRES DE HANOISe tienen 3 palos de madera, que llamaremos palo izquierdo, central y derecho. El palo izquierdo tiene ensartados un montón de discos concéntricos de tamaño decreciente, de manera que el disco mayor está abajo y el menor arriba. • El problema consiste en mover los discos del palo izquierdo al derecho respetando las siguientes reglas: - Sólo se puede mover un disco cada vez. - No se puede poner un disco encima de otro más pequeño. - Después de un movimiento todos los discos han de estar en alguno de los tres palos. Leer por teclado un valor N, e imprimir la secuencia de pasos para resolver el problema.

13

14 SOLUCIÓN RECURSIVA • Solución recursiva a las Torres de HanoiSi n=1 mueva el disco de A a C y parar Mueva los n-1 discos superiores de A a B, con C auxiliar Mueva los discos restantes de A a C Mueva los n-1 discos de B a C, usando A como auxiliar

15 Planteamos un procedimiento recursivo con cuatro parámetros:- El número de discos a mover. - El palo origen desde donde moverlos. - El palo destino hacia el que moverlos. - El palo auxiliar. ALGORITMO Mueve(E N n; E Tpalos origen,auxiliar,destino) INICIO SI n == 1 ENTONCES Mueve un disco del palo origen al destino SINO Mueve(n-1,origen,destino,auxiliar) Mueve(n-1,auxiliar,origen,destino) FINSI FIN