PDF de programación - Tema 7 - Recursividad

Tema 7:

Recursividad







Objetivos: en este tema estudiaremos funciones recursivas; esto es, funciones
que se invocan a sí mismas. Estas funciones son equivalentes a estructuras
tipo bucle pero permiten especificar muchos problemas de un modo más
simple y natural que éstos, de ahí su importancia en computación.

















Metodología y tecnología de la programación I



2/11



Índice

Índice ...........................................................................................................................................2

1

2

Introducción.........................................................................................................................3

Tipos de recursión ...............................................................................................................3

2.1

Recursión lineal ...........................................................................................................4

2.1.1

Recursión lineal no final......................................................................................4

2.1.2

Recursión lineal final...........................................................................................5

2.2

Recursión múltiple.......................................................................................................6

2.3

Recursión mutua..........................................................................................................7

3

Ejercicios .............................................................................................................................9

4 Apéndice: las torres de Hanoi............................................................................................10

4.1

Leyenda sobre las torres de Hanoi.............................................................................11





Metodología y tecnología de la programación I



3/11

1 Introducción

llevan consigo

Una función recursiva es una función que se llama a si misma. Esto es, dentro del cuerpo
de la función se incluyen llamadas a la
propia función. Esta estrategia es una
alternativa al uso de bucles. Una
solución
recursiva es, normalmente,
menos eficiente que una solución basada
en bucles. Esto se debe a las operaciones
auxiliares que
las
llamadas a las funciones. Cuando un
programa llama a una función que llama
a otra, la cual llama a otra y así
sucesivamente, las variables y valores de
los parámetros de cada llamada a cada
función se guardan en la pila o stack,
junto con la dirección de la siguiente
línea de código a ejecutar una vez finalizada la ejecución de la función invocada. Esta pila
va creciendo a medida que se llama a más funciones y decrece cuando cada función
termina. Si una función se llama a si misma recursivamente un número muy grande de
veces existe el riesgo de que se agote la memoria de la pila, causando la terminación
brusca del programa.

A pesar de todos estos inconvenientes, en muchas circunstancias el uso de la recursividad
permite a los programadores especificar soluciones naturales y sencillas que sin emplear
esta técnica serían mucho más complejas de resolver. Esto convierte a la recursión en una
potente herramienta de la programación. Sin embargo, por sus inconvenientes, debe
emplearse con cautela.

2 Tipos de recursión

Como regla básica, para que un problema pueda resolverse utilizando recursividad, el
problema debe poder definirse recursivamente y, segundo, el problema debe incluir una


Metodología y tecnología de la programación I



4/11

condición de terminación porque, en otro caso, la ejecución continuaría indefinidamente.
Cuando la condición de terminación es cierta la función no vuelve a llamarse a si misma.

Pueden distinguirse distintos tipos de llamada recursivas dependiendo del número de
funciones involucradas y de cómo se genera el valor final. A continuación veremos cuáles
son.

2.1 Recursión lineal

En la recursión lineal cada llamada recursiva genera, como mucho, otra llamada recursiva.
Se pueden distinguir dos tipos de recursión lineal atendiendo a cómo se genera resultado.

2.1.1 Recursión lineal no final

En la recursión lineal no final el resultado de la llamada recursiva se combina en una
expresión para dar lugar al resultado de la función que llama. El ejemplo típico de
recursión lineal no final es cálculo del factorial de un número (n! = n * (n-1) * ...* 2 * 1 ).
Dado que el factorial de un número n es igual al producto de n por el factorial de n-1, lo
más natural es efectuar una implementación recursiva de la función factorial. Veamos una
implementación de este cálculo:

/*
*ejemplo7_1.c
*/
#include <stdio.h>

int factorial(int numero){
if (numero > 1) return (numero*factorial(numero-1));
else return(1);
}

int main (){
int n;
printf("Introduce el número: ");
scanf("%d",&n);
printf("El factorial es %d", factorial(n));
}



para calcular el factorial de 4 esta sería la secuencia de llamadas:



Metodología y tecnología de la programación I



5/11



factorial(4) = 4 * factorial(3)





factorial(3) = 3 * factorial(2)











factorial(2) = 2 * factorial(1)









return(4*6)

return(3*2)

return (2*1)



factorial(1) = 1





return 1;

Cada fila del anterior gráfico supone una instancia distinta de ejecución de la función fact.
Cada instancia tiene un conjunto diferente de variables locales.

2.1.2 Recursión lineal final

En la recursión lineal final el resultado que es devuelto es el resultado de ejecución de la
última llamada recursiva. Un ejemplo de este cálculo es el máximo común divisor, que
puede hallarse a partir de la fórmula:



/*
*ejemplo7_2.c
*/
#include <stdio.h>

long mcd(long,long);

main(int argc, char *argv[]){
long a= 4454,b= 143052;
printf("El m.c.d. de %ld y %ld es %ld\n",a,b,mcd(a,b));
}



Metodología y tecnología de la programación I



6/11

long mcd(long a, long b){
if (a==b) return a;
else if (a<b) return mcd(a,b-a);
else return mcd(a-b,b);
}


2.2 Recursión múltiple

Alguna llamada recursiva puede generar más de una llamada a la función. Uno de los
centros más típicos son los números de Fibonacci, números que reciben el nombre del
matemático italiano que los descubrió. Estos números se calculan mediante la fórmula:



Estos números poseen múltiples propiedades, algunas de las cuales todavía siguen
descubriéndose hoy en día, entre las cuales están:

• La razón (el cociente) entre un término y el inmediatamente anterior varía
continuamente, pero se estabiliza en un número irracional conocido como razón
áurea o número áureo, que es la solución positiva de la ecuación x2-x-1=0, y se
puede aproximar por 1,618033989.

• Cualquier número natural se puede escribir mediante la suma de un número
limitado de términos de la sucesión de Fibonacci, cada uno de ellos distinto a los
demás. Por ejemplo, 17=13+3+1, 65=55+8+2.

• Tan sólo un término de cada tres es par, uno de cada cuatro es múltiplo de 3, uno
de cada cinco es múltiplo de 5, etc. Esto se puede generalizar, de forma que la
sucesión de Fibonacci es periódica en las congruencias módulo m, para cualquier
m.

• Si F(p) es un número primo, p también es primo, con una única excepción. F(4)=3;

3 es primo, pero 4 no lo es.

• La suma infinita de los términos de la sucesión F(n)/10n es exactamente 10/89.

Veamos un programa que nos permite calcular el número n de la serie de Fibonacci:




Metodología y tecnología de la programación I



7/11

/*
*ejemplo7_3.c
*/
#include <stdio.h>

long fibonacci (int);

int main()
{
int n= 30;

printf("El %dº número de Fibonacci es %ld\n", n,
fibonacci(n));
}

long fibonacci(int n)
{
if (1 == n || 2 == n) {
return 1;
} else {
return (fibonacci(n-1) + fibonacci(n-2));
}
}

2.3 Recursión mutua

Implica más de una función que se llaman mutuamente. Un ejemplo es el determinar si un
número es par o impar mediante dos funciones:

else

/*
*ejemplo7_4.c
*/
#include <stdio.h>

long fibonacci (int);

int main(){
int n= 30;
if (par(n))
printf("El número es par");
printf("El número es impar");
}

int par(int n){
if (n==0) return 1;
else return (impar(n-1));
}

int impar(int n){
if (n==0) return 0;


Metodología y tecnología de la programación I



8/11

else return(par(n-1));
}

Veamos un ejemplo de ejecución de este programa:

par(5) -> return(impar(4))
impar(4) -> return(par(3))
par(3) -> return(impar(2))
impar(2) -> return(par(1))
par(1) -> return(impar(0))

return(0) (no es par)
return(0)
return(0)
return(0)
return(0)

impar(0) -> return(0)



Metodología y tecnología de la programación I



9/11

3 Ejercicios

1. Construir una función recursiva que calcule la suma de los n primeros números

naturales.

2. Construir una función recursiva que imprima la lista de números naturales

comprendidos entre dos valores a y d dados por el usuario.

3. Escribir una función recursiva que devuelva la cantidad de dígitos de un número

entero.

4. Escribir una función recursiva que calcule x^y mediante multiplicaciones

sucesivas, siendo x e y dos números enteros.

5. Escribir una función recursiva