Material de Apoyo para Programacin Estructurada

Universidad del Papaloapan

UNIDAD III. RECURSIVIDAD

3.1 DIRECTA E INDIRECTA Larecursividadesunatcnicadeprogramacinimportante.Seutilizapararealizarunallamadaauna funcindesdelamismafuncin.Porlotanto,podemosdecirqueunafuncinrecursivaesaquellaque formapartedesmisma.Estaideapuedeservirdeayudaparaladefinicindeconceptosmatemticos. Porejemplo,paraladefinicindelconjuntodelosnmerosnaturalespodemosdecirqueesaquel conjuntoenelquesecumplenlassiguientescaractersticas: 0 es un nmero natural. El siguiente nmero de un nmero natural es un nmero natural.

Mediante una definicin finita hemos representado un conjunto infinito. La recursividad es una de las formas de control ms importantes en la programacin debido a que los procedimientos recursivos son la forma ms natural de representar muchos algoritmos. Es importante tener en cuenta que un procedimiento o una funcin recursiva debe cumplir con dos propiedades generales para no dar lugar a un ciclo infinito con las sucesivas llamadas:

Material de Apoyo para Programacin Estructurada

Universidad del Papaloapan

Cumplir una cierta condicin o criterio base del que dependa la llamada recursiva. Cada vez que el procedimiento o funcin se llamen as mismos, directa o indirectamente debe estar ms cerca del incumplimiento de la condicin de que depende la llamada.

Tipo de recurrencias Directa. Este tipo de recursividad es la ms comn y se presenta cuando una funcin se llama as misma una o varias veces. Indirecta. Este tipo de recursividad se presenta cuando una funcin es llamada de manera indirecta, es decir, a travs de otra funcin, generando llamadas recursivas (El ejercicio 3.2 muestra un ejemplo de la recursividad indirecta). Existen otras clasificaciones de las funciones recursivas como son la recursividad lineal y mltiple. Recursin lineal. sta se presenta dentro de una funcin recursiva cuando cada llamada recursiva genera como mucho otra llamada recursiva. Final. Si la llamada recursiva es la ultima operacin que se efecta, devolvindose como resultado lo que haya obtenido de la llamada recursiva sin modificacin alguna. No Final. El resultado obtenido de la llamada recursiva se combina para dar lugar al resultado de la funcin que realiza la llamada.

Recursin mltiple. sta se presenta dentro de una funcin recursiva cuando una llamada recursiva puede generar ms de una llamada recursiva adicional. Ejemplo. Elaborar una funcin recursiva para calcula el factorial de un nmero. Matemticamente se define como factorial de un nmero n al producto de los enteros positivos desde 1 hasta n y se denota por n! n! = 1 * 2 * 3 * 4 * 5 . . . (n 2) * (n 1) * n

Material de Apoyo para Programacin Estructurada

Universidad del Papaloapan

Tambin se define 0! = 1, de forma que la funcin est definida para todos los enteros no negativos. As tenemos que: 0! = 1 1! = 1 2! = 1 * 2 = 2 3! = 1 * 2 * 3 = 6

4! = 1 * 2 * 3 * 4 = 24

5! = 1 * 2 * 4 * 5 = 120

y as sucesivamente. Por tanto, se cumple que para cualquier entero positivo n. n! = n (n 1)! De acuerdo con esto, la funcin factorial se puede definir tambin como: Si n < 2 entonces n! = 1 Si n >= 2 entonces n! = n(n - 1)! Esta definicin de n! es recursiva ya que se refiere as mismo cuando invocamos a n(n -1)!. El siguiente programa calcula el factorial de un nmero a travs del uso de funciones recursivas. #include<stdio.h> long factorial(int); int main() { int num; long result; printf("Introduce un nmero: "); scanf("%d",&num); result=factorial(num); printf("El factorial de %d es %ld\n",num,result); return 0; } long factorial(int x) { long fac; if(x==0 || x==1) fac = 1; else

Material de Apoyo para Programacin Estructurada fac = x * factorial(x-1); return fac; } El ejemplo anterior utiliza recursividad lineal.

Universidad del Papaloapan

Ejercicio 3.1 Realiza un programa que solicite al usuario un nmero y la potencia a la que desea elevarlo y muestra el resultado por pantalla. Para este ejercicio, crea una funcin recursiva que calcule el resultado. Ejercico 3.2 Realiza un programa que solicite al usuario un nmero y muestra en pantalla si el nmero es par o impar. Para este ejercicio debes crear una o varias funciones recursivas que determinen si el nmero es par o impar. int par(int n) { if (n == 0) return 1; return impar(n-1); } int impar(int n) { if (n == 0) return 0; return par(n-1); }

Ejercicio 3.3 Realiza un programa que solicite al usuario dos nmeros enteros positivos y crea una funcin recursiva denominada MCD que calcule el mximo comn divisor de dichos nmeros, por ltimo, muestra el resultado en pantalla. El programa terminar su ejecucin cuando el usuario introduzca 0 0. Ejemplo: Introduce dos nmero: 20 10 El mximo comn divisor es 10 Recordemos que 20 puede ser dividido por: 1, 2, 4, 5, 10 y 20, y que 10 puede ser dividido por: 1, 2, 5 y 10. Por lo tanto, el mximo comn divisor para ambos nmeros es 10.

Material de Apoyo para Programacin Estructurada

Universidad del Papaloapan

Ejercicio 3.4 Realiza un programa que solicite al usuario cuantos nmeros de la serie fibonacci desea ver y muestralos en pantalla. Para resolver este problema crea una funcin recursiva que calcule dicha serie. Ejemplo de la serie fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, . Ejercicio 3.5 Realiza un programa que solucione el problema de las torres de Hanoit para n discos, utilizando funciones recursivas para este ejercicio.

El objetivo del juego de las torres de hanoit, es mover todos los discos de la esta A a las esta C, utilizando a B como un apoyo. Las reglas de este juego es que slo se puede mover un disco a la vez, y que un disco chico no puede estar debajo de un disco ms grande que l.

3.2 COMPARACIN ENTRE FUNCIONES ITERATIVAS Y RECURSIVAS. La solucin recursiva de ciertos problemas simplifica mucho la estructura de los programas. Sin embrago, existe una desventaja, en la mayora de los lenguajes de programacin. Las llamadas recursivas a procedimientos o funciones tienen un costo de tiempo mucho mayor con respecto a las soluciones iterativas. Se puede, por tanto, afirmar que la ejecucin de un programa recursivo va a ser ms lenta y menos eficiente que el programa iterativo que soluciona el mismo problema, aunque, a veces, la sencillez de la estructura recursiva justifica el mayor tiempo de ejecucin. Las funciones recursivas se pueden convertir en no recursivas mediante la introduccin de un apila y as emular las llamadas recursivas. De esta forma se puede eliminar la recursin de aquellas partes de los programas que se ejecutan ms frecuentemente.

3.3 FUNCIONES RECURSIVAS CON ARREGLOS. Ejemplo: El siguiente programa realiza la suma de los nmeros de un arreglo usando una funcin

Material de Apoyo para Programacin Estructurada recursiva. #include<stdio.h> #define TM 10 int suma(int *,int); int main() { int arreglo[TM]={4,6,8,9,2,7,3,1,43,12}; int r; r = suma(arreglo,TM-1); printf("La suma de los elementos del arreglo es: %d\n",r); return 0; } int suma(int vector[],int posicion) { if(posicion==0) return vector[posicion]; return vector[posicion]+suma(vector,posicion-1); }

Universidad del Papaloapan

Ejercicio 3.6 Realizar un programa que solicite al usuario un conjunto de n nmeros enteros positivos (1< n <1000), los cuales sern colocados en un arreglo de tamao n, para que el usuario le indique a la computadora que ya no desea introducir ms nmeros deber colocar -1, ste indicar el fin de datos, posteriormente, el programa deber mostrar en pantalla la suma de los nmeros introducidos por el usuario (con excepcin del -1). Para este ejercicio crea una funcin recursiva que realice la suma. Ejercicio 3.7 Realiza un programa que solicite al usuario introducir n y m nmeros enteros (n m), los cuales debern ser colocados en el arreglo A y B de tamao n y m respectivamente. El programa deber determina si el arreglo B est contenido en el arreglo A. Ejemplo: A = {2,3,4,5,6,7,-3} B = {7,-3} El arreglo B esta contenido en A. A = {2,3,4,5,6,7,-3} B = {5,7} El arreglo B no esta contenido en A. A = {2,3,4,5,6,7,-3} B = {3,2}

Material de Apoyo para Programacin Estructurada El arreglo B no esta contenido en A.

Universidad del Papaloapan

Ejercicio 3.8 Realizar un programa que solicite al usuario un conjunto de n nmeros enteros (n 1) y crea una funcin recursiva que devuelva la suma de todos los elementos mayores que el ltimo elemento del arreglo. Parar este ejercicio basta con hacer un nico recorrido sobre el arreglo, no se debe utilizar ningn arreglo auxiliar, slo se podrn utilizar variables de tipo entero o booleano.

3.4 EJEMPLO DE TRANSFORMACIN DE UN ALGORITMO RECURSIVO A ITERATIVO. Para eliminar la recursividad se utiliza una pila. En la pila el primer elemento que entra es el ltimo en salir. Por consiguiente habr que recorrer la lista, nodo a nodo. Las direcciones de los nodos (punteros) son almacenados en una pila hasta alcanzar el ltimo nodo. Una vez alcanzado el ltimo nodo se escribe el campo de informacin y aqu es donde se simula la recursividad. La vuelta atrs conseguida con la recursividad se consigue sacando de la pila las direcciones de los nodos, escribiendo la informacin, as hasta que quede vaca la pila. Ejemplo: Realizar un programa que multiplique dos nmeros enteros por el mtodo de la montaa rusa. Descripcin: El mtodo consiste en formar dos columnas, una por cada operando. Las columnas se forman aplicando repetidamente los pasos siguientes: 1. Dividir por 2 el multiplicando. Anotar el cociente en la columna del multiplicando como nuevo multiplicando. 2. Duplicar el multiplicador y anotarlo en la columna del multiplicador. Una vez hecho esto, se suman los valores de la columna del multiplicador que se correspondan con valores impares de la columna de multiplicandos. La suma es el producto. Solucin del ejemplo de forma recursiva. #include <stdio.h> int multiplicacion(int,int); int main() { int a,b; printf("Introduce dos nmeros a multiplicar:"); scanf("%d %d",&a,&b); printf("%d * %d = %d\n",a,b,multiplicacion(a,b));

Material de Apoyo para Programacin Estructurada return 0; } int multiplicacion(int x, int y) { if(x==0) return 0; if(x%2==1) return y + multiplicacion(x/2,y*2); return multiplicacion(x/2,y*2); } Solucin de forma iterativa, implementado pilas. #include <stdio.h> #include <stdlib.h> struct num { int numero; struct num *sig; }; int multiplicacion(int,int); int push(struct num **,int); int pop(struct num **,int *); int pilavacia(struct num *); struct num * crearnodo(int); int main() { int a,b; printf("Introduce dos nmeros a multiplicar:"); scanf("%d %d",&a,&b); printf("%d * %d = %d\n",a,b,multiplicacion(a,b)); return 0; } int multiplicacion(int x,int y) { struct num *multiplicando,*multiplicador; int r = 0; multiplicando = NULL; multiplicador = NULL; if (!push(&multiplicando,x) || !push(&multiplicador,y)) {

Universidad del Papaloapan

Material de Apoyo para Programacin Estructurada printf("Error, se termin la memoria.\n"); exit(1); } while(1) { x /= 2; y *= 2; if (!push(&multiplicando,x) || !push(&multiplicador,y)) { printf("Error, se termin la memoria.\n"); exit(1); } if(x==0) break; } while(pop(&multiplicando,&x)) { pop(&multiplicador,&y); if(x%2==1) r += y; } return r; } int push(struct num **p,int z) { struct num *cima,*nuevo; cima = *p; nuevo = crearnodo(z); if(nuevo==NULL) return 0; nuevo->sig = cima; cima = nuevo; *p = cima; return 1; } int pop(struct num **p,int *z) { struct num *cima; cima = *p; if(pilavacia(cima)) return 0; *z = cima->numero; *p = cima->sig;

Universidad del Papaloapan

Material de Apoyo para Programacin Estructurada free(cima); return 1; } struct num * crearnodo(int z) { struct num *nodo; nodo = (struct num *)malloc(sizeof(struct num)); if(nodo!=NULL) { nodo->numero = z; nodo->sig=NULL; } return nodo; } int pilavacia(struct num *p) { if(p==NULL) return 1; return 0; }

Universidad del Papaloapan

Es importante aclarar que el uso de pilas no es la nica forma de eliminar la recursividad, existen diversas tcnicas que nos permiten convertir un algoritmo recursivo a iterativo, sin embargo, estos temas quedan fuera del alcance de esta asignatura. El siguiente cdigo da solucin al ejemplo de la multiplicacin por el mtodo de la montaa rusa, a travs de un algoritmo iterativo pero sin utilizar pilas. #include <stdio.h> int main() { int a,b,m,tmp1,tmp2; printf("Introduce dos nmeros a multiplicar:"); scanf("%d %d",&a,&b); tmp1 = a; tmp2 = b; m = 0; do{ if(a%2==1) m += b; a/=2;

Material de Apoyo para Programacin Estructurada b*=2; }while(a>0); printf("%d * %d = %d\n",tmp1,tmp2,m); return 0; }

Universidad del Papaloapan

3.5 EJEMPLO DE TRANSFORMACIN DE UN ALGORITMO ITERATIVO A RECURSIVO. Por lo general cuando se trata de optimizar los recursos de espacio en memoria que utiliza un programa para su ejecucin, lo ms comn es evitar el uso de funciones recursivas, para ellos una alternativa es convertir la funcin recursivo a iterativo como se mostr en el tema anterior, sin embargo, para propsitos didcticos en este tema veremos como pasar un algoritmo iterativo a recursivo. Ejemplo: Realizar una funcin que multiplique el contenido de dos matrices A y B de tamao 3x5 y 5x4 respectivamente, el resultado deber ser almacenado en una tercera matriz denominada C para posteriormente mostrarlo en pantalla. Solucin iterativa. #include <stdio.h> #define REN 3 #define COL1 5 #define COL2 4 void producto(int A[][COL1],int B[][COL2], int C[][COL2]); int main() { int A[REN][COL1],B[COL1][COL2],C[REN][COL2]; int x,y,z; printf("Introduce los datos de la primera matriz:\n"); for(x=0;x<REN;x++) for(y=0;y<COL1;y++) scanf("%d",&A[x][y]); printf("Introduce los datos de la segunda matriz:\n"); for(y=0;y<COL1;y++) for(z=0;z<COL2;z++) scanf("%d",&B[y][z]); producto(A,B,C); printf("El producto de las dos matrices es:\n"); for(x=0;x<REN;x++)

Material de Apoyo para Programacin Estructurada { for(z=0;z<COL2;z++) printf("%d\t\t",C[x][z]); printf("\n"); } return 0; } void producto(int A[][COL1],int B[][COL2], int C[][COL2]) { int x,y,z,aux; for(x=0;x<REN;x++) { for(z=0;z<COL2;z++) { aux = 0; for(y=0;y<COL1;y++) aux += (A[x][y] * B[y][z]); C[x][z] = aux; } } }

Universidad del Papaloapan

A continuacin mostraremos como convertir el programa del ejemplo anterior para que sea un programa recursivo. Esta tcnica nos servir para pasar funciones iterativas que usen bucles for (y otros) a forma recursiva. Primero tenemos el siguiente cdigo en C para multiplicar matrices de forma iterativa: void producto(int A[][COL1],int B[][COL2], int C[][COL2]) { int x,y,z,aux; for(x=0;x<REN;x++) for(z=0;z<COL2;z++) for(y=0;y<COL1;y++) C[x][z] += (A[x][y] * B[y][z]); } Vamos a llamar a los bucles primero segundo y tercero leyendo de arriba a abajo, y siendo A y B las matrices a multiplicar y C la matriz resultado. En las funciones, a y b son el tamao de la matriz. El primero for se traducira as:

Material de Apoyo para Programacin Estructurada

Universidad del Papaloapan

void primerFor(int A[][COL1],int B[][COL2], int C[][COL2], int a,int b,int i) {//El caso base es cuando i es igual a a. if(i!=a) { segundoFor(A, B, C, a, b, i, 0); primerFor(A, B, C, a, b, i++); } } Si miramos el primer for, la condicin para salirnos del bucle es que i sea igual (menor estricto) al tamao de la matriz, pues ese ser nuestro caso base, es decir, i==a. Al final del bucle incrementamos i, pues eso mismo hacemos en nuestra funcin con una llamada recursiva. Antes de eso, deberemos llamar a la segunda funcin recursiva, la cual sera creada del mismo modo. void segundoFor(int A[][COL1],int B[][COL2], int C[][COL2], int a,int b,int i,int j) { if(j!=COL2) { tercerFor(A,B,C, a, b, i, j, 0); segundoFor(matrices, a, b, i, j++); } } Como se puede ver, cada vez que llamamos a la siguiente funcin (en definitiva pasamos al siguiente for) pasamos el valor cero inicial de comienzo del bucle. La tercera y ltima funcin sigue el mismo patrn, pero en vez de llamar a una supuesta cuarta funcin (si hubiera 4 as sera), realizamos la operacin que vamos buscando. void tercerFor( int A[][COL1],int B[][COL2], int C[][COL2], int a,int b,int i,int j,int k) { if(k!=b) { C[i][j]+=A[i][k]*B[k][j]; tercerFor(A,B,C, a, b, i, j, k++); } } Este mtodo es slo una alternativa pasar convertir funciones iterativas a recursivas.