tp 1 recursividad

1 Tecnología de la Programación

Tema 1. Recursividad

Temario


1.1 Definición de recursividad

1.2 Ejemplos de recursividad en C

1.3 Tipos de recursividad

1.4 La pila de recursión

1.5 El árbol de recursión

1.6 Tiempo de ejecución de los algoritmos recursivos

1.7 Recursión vs iteración




Se dice que un objeto es recursivo si forma parte de sí mismo o se

define en función de sí mismo.

Técnica particularmente potente en las definiciones matemáticas.

La potencia de la recursión reside en la posibilidad de definir un número

infinito de objetos mediante un enunciado finito.

De igual forma, un número infinito de operaciones de cálculo puede

describirse mediante un programa recursivo finito.

En general, un algoritmo recursivo P puede expresarse como una

composición de instrucciones básicas Si (que no contienen a P) y el

propio P.

P[Si,P]




Ejemplos:

Números naturales:

1 es un número natural

El siguiente de un número natural es un número natural

Función factorial, n! (para números enteros no negativos): 0! = 1

Si n>0 entonces n! = n · (n–1)!

3! = 3 · (3-1)!

= 3 · 2!

= 3 · 2 · (2-1)!

= 3 · 2 · 1!

= 3 · 2 · 1 · (1-1)!

= 3 · 2 · 1 · 0!

= 3 · 2 · 1 · 1

= 6

4

En general, los programas se estructuran de la siguiente manera:

Para implementar algoritmos

recursivos en C, se utilizan

funciones recursivas, que se

invocan a sí mismas al menos una

vez, con la siguiente estructura:

Tecnología de la Programación



instruccion1

…

funcionC

…

instruccionM

retorna

instruccion1

…

instruccionI

…

instruccionJ

retorna

funcionA funcionB funcionC

instruccion1

…

funcionB

…

instruccionN

retorna

funcionR

instruccion1

…

funcionR

…

instruccionM

retorna




Una función recursiva está bien construida si:

1. Contiene, al menos, un caso base, que no contiene

ninguna llamada recursiva.

2. Los valores de los parámetros de la función en las

sucesivas llamadas recursivas, están más cerca del caso

base que el valor con el que se llamó inicialmente la

función, garantizando que el caso base se alcanza. Al

caso que contiene la llamada recursiva se le llama caso

general o de recursión (pueden ser varios).



1.2 Ejemplos de Recursividad en C

Multiplicación n · m ( m ≥ 0 )

Caso Base: ( m==0 ) n · m = 0 Caso General: ( m > 0 ) n · m = n + n · ( m – 1 )

// m>=0

int multiplica(int n, int m){ int salida;

if (m==0) salida = 0;

else salida=n+multiplica(n,m-1);

return salida; }

Un esquema más compacto y propio de C es el siguiente:

// m>=0

int multiplica(int n, int m) { if (m==0) return 0;

return n+multiplica(n,m-1); }




División entera n / m ( n 0 y m > 0 )

Caso Base: ( n < m ) n / m = 0 Caso General: ( n m ) n / m = 1 + ( n – m ) / m

// n>=0 && m>0

int divide(int n, int m)

{

if (n<m) return 0;

return 1 + divide(n-m,m);

}




Módulo n % m ( n 0 y m > 0 )

Caso Base: ( n < m ) n % m = n Caso General: ( n m ) n % m = ( n – m ) % m

// n>=0 && m>0

int modulo(int n, int m)

{

if (n<m) return n;

return modulo(n-m,m);

}




Potencia nm ( ( m > 0 ) o ( ( m = 0 ) y ( n != 0 ) ) )

Caso Base: ( m = 0 ) n 0 = 1 Caso General: ( m > 0 ) n m = n · n m - 1

// (m>0) || ((m==0)&&(n!=0))

int potencia(int n, int m)

{

if (m==0) return 1;

return n * potencia(n,m-1);

}




Factorial n ! ( n 0 )

Caso Base: ( n = 0 ) 0 ! = 1 Caso General: ( n > 0 ) n ! = n · ( n – 1 ) !

// n>=0

int factorial(int n)

{

if (n==0) return 1;

return n * factorial(n-1);

}




Fibonacci fibonacci(n) ( n 0 )

Caso Base: ( n 1 ) fib(n) = n Caso General: ( n > 1 ) fib(n) = fib(n-2) + fib(n-1)

// n>=0

int fibonacci(int n)

{

if (n<=1) return n;

return fibonacci(n-2) + fibonacci(n-1);

}



1.3 Tipos de Recursividad

Existen varios tipos de recursividad dependiendo de cómo se

realice la llamada recursiva:

•Recursividad directa o simple: La función contiene una llamada

explícita a sí misma, es decir, A invoca a A.

•Recursividad múltiple: existe más de una llamada recursiva en el

cuerpo de la función.

•Recursividad indirecta o cruzada: La función se invoca a sí

misma de forma indirecta, es decir, A invoca a B y B invoca a A.

•Recursividad de cola o de extremo final: La llamada recursiva

es la última instrucción que ejecuta la función.

•Recursividad anidada: En alguno de los argumentos de la llamada

recursiva hay una nueva llamada recursiva

13


La función modulo es un ejemplo de recursividad directa y de extremo final.

La función fibonacci es un ejemplo de recursividad múltiple.

Ejemplo de recursividad indirecta o cruzada:

Par par(n) ( n 0 )

Caso Base: ( n = 0 ) par(n) = cierto

Caso General: ( n > 0 ) par(n) = impar(n-1)

Impar impar(n) ( n 0 )

Caso Base: ( n = 0 ) impar(n) = falso

Caso General: ( n > 0 ) impar(n) = par(n-1)

// n>=0

int par(int n)

{ if (n==0) return 1;

return impar(n-1);

}

// n>=0

int impar(int n)

{ if (n==0) return 0;

return par(n-1);

}

14


// n>=0 && m>=0

int ackermann(int m, int n)

{

if (m==0) return n+1;

if (n==0) return ackermann(m-1,1);

return ackermann(m-1,ackermann(m,n-1));

}

Ejemplo de recursividad anidada:

Ackermann ack(m,n) ( n 0 y m 0 )

Caso Base: ( m = 0 ) ack(m,n) = n+1

Caso General: ( m > 0 y n = 0 ) ack(m,n) = ack(m-1,1)

( m > 0 y n > 0 ) ack(m,n) = ack(m-1, ack(m,n-1) )

15


Las llamadas a funciones se manejan a través de la pila que gestiona el compilador.

Cada llamada produce un registro de activación en la pila que guarda:

• Los parámetros de llamada.

• Las variables locales.

• La dirección de retorno.

• El resultado devuelto por la función.

Las llamadas recursivas se gestionan exactamente igual que el resto de llamadas, formando la pila de recursión.

A continuación mostramos, para el ejemplo de la función factorial, la evolución de la pila de llamadas del sistema.

16


Ejemplo: pila de recursión de la función factorial

int factorial(int n)

{

if (n==0) return 1;

return n*factorial(n-1);

// Despues de la llamada recursiva se ejecuta el operador de

// multiplicación (direccion $B en el segmento de código)

}

int main()

{

int x=3;

int f = factorial(x);

// Despues de la llamada a factorial se ejecuta la sentencia

// de asignación (direccion $A en el segmento de código)

printf("%d",f);

return 0;

}

17


Ejemplo: pila de recursión de la función factorial

int factorial(int n) {

if (n==0) return 1;

return n*factorial(n-1); // $B

}

int main() {

int x=3;

int f = factorial(x); // $A

printf("%d",f);

return 0;

}

Leyenda:

VR(Vi,VF) = Valor de Retorno (Inicio,Final)

DR = Dirección de Retorno

f (?,6)

main() x 3

DR System

VR (?,1)

n 3

factorial(3) DR $A

VR (?,6)

n 2

factorial(2) DR $B

VR (?,2)

n 1

factorial(1) DR $B

VR (?,1)

n 0

factorial(0) DR $B

VR (?,1)

Estado de la pila para factorial(3)

Segmento de pila

18


El árbol de recursión permite obtener una visión gráfica global de la complejidad de un algoritmo recursivo, así como de la forma en la que se producen las llamadas recursivas.

Esta información puede resultar de gran utilidad a la hora de decidir si el enfoque recursivo realizado para el problema es apropiado o por el contrario no resulta adecuado y es mejor buscar otro enfoque (por ejemplo, iterativo).

En un árbol de recursión cada nodo representa una subllamada recursiva, incluyendo en el contenido del nodo el valor de los parámetros de llamada.

Los nodos hoja en el árbol representan los casos base de la recursión.

19


Ejemplo: árbol de recursión de la función fibonacci(6):

6

5

3

2 1

4

2

4

2 1

2 1

3

2 3

1 0 1 0

1 0

1 0

1 0




El mecanismo de expansión de recurrencias para calcular el tiempo de

ejecución de un algoritmo recursivo con entrada n (T(n)) es el siguiente:

1. Se tiene la ecuación de recurrencia que expresa el tiempo de

ejecución del caso base (suponemos n=1) y del caso general (n>1).

2. Se sustituye T(n) por su definición recurrente. Al aparecer entonces

T(m) con m<n en la derecha, se vuelve a sustituir por su definición

recurrente en la derecha, hasta que todos los términos T(m) para m>1

se hayan reemplazado por fórmulas que impliquen sólo T(1).

3. Por inducción en i obtenemos la Forma Cerrada para T(n).

4. La expansión terminará cuando se alcance T(1) en el lado derecho

de la forma cerrada. Como T(1) siempre es constante, se tiene una

fórmula para T(n) en función de n y de algunas constantes.




Ejemplo: Factorial

Ecuación de recurrencia:

T(0) = c1

T(n) = T(n-1) + c2 si n>0

Expansión de recurrencias:

T(n) = T(n-1)+c2 = [T(n-2)+c2]+c2 = T(n-2)+2c2 = [T(n-3)+c2]+2c2 = T(n-3)+3c2

Forma cerrada para T(n) (por inducción en i):

T(n) = T(n-i) + i c2

La expansión terminará cuando se alcance T(0) en el lado derecho de la forma

cerrada, es decir, cuando n-i=0, por tanto i=n. Sustituyendo en la forma

cerrada i por n se obtiene:

T(n) = T(0) + n c2 = c1 + n c2

Esto demuestra que T(n) es O(n).



1.7 Recursión vs Iteración

La recursión implica múltiples llamadas y el uso de la pila interna para almacenar, en cada llamada recursiva, los parámetros de llamada, variables locales y dirección de retorno, lo que hace que en general sea más ineficiente que el diseño iterativo. Siempre es posible sustituir un algoritmo recursivo por un algoritmo iterativo que utilice una pila. Casos en los que no se debe utilizar la recursión: 1. Recursividad de cola 2. Árbol de recursión lineal (ejemplo, factorial) 3. Árbol de recursión ramificado, pero con nodos repetidos (ejemplo Fibonacci)

Conclusión: La recursión se deberá utilizar cuando, además de facilitar el diseño del algoritmo, genere un árbol de recursión ramificado y con nodos no repetidos.




Multiplicación n · m ( m 0 )

Caso Base: ( m = 0 ) n · 0 = 0

Caso General: ( m > 0 ) n · m = n + n · (m - 1)

// m>=0 (versión recursiva)

int multiplica(int n, int m) {

if (m==0) return 0;

return n+multiplica(n,m-1);

}

// m>=0 (versión iterativa)

int multiplica(int n, int m) {

int res = 0;

while(m>0){ res+=n; m--; }

return res;

}




División entera n / m ( n 0 y m > 0 )

Caso Base: ( n < m ) n / 0 = 0

Caso General: ( n m ) n / m = 1 + ( n – m) / m

// n>=0 && m>0 (versión recursiva)

int divide(int n, int m) {

if (n<m) return 0;

return 1+divide(n-m,m);

}

// n>=0 && m>0 (versión iterativa)

int divide(int n, int m) {

int res = 0;

while(n>=m) { res++; n-=m;}

return res;

}




Módulo n % m ( n 0 y m > 0 )

Caso Base: ( n < m ) n % m = n

Caso General: ( n m ) n % m = ( n – m ) % m

// n>=0 && m>0 (versión recursiva)

int modulo(int n, int m) {

if (n<m) return n;

return modulo(n-m,m);

}

// n>=0 && m>0 (versión iterativa)

int modulo(int n, int m) {

while(n>=m) n-=m;

return n;

}




Potencia nm ( ( m > 0 ) o ( ( m = 0 ) y ( n != 0 ) ) )

Caso Base: ( m = 0 ) n 0 = 1

Caso General: ( m > 0 ) n m = n · n m - 1

// (m>0) || ((m==0)&&(n!=0)) (versión recursiva)

int potencia(int n, int m) {

if (m==0) return 1;

return n*potencia(n,m-1);

}

// (m>0) || ((m==0)&&(n!=0)) (versión iterativa)

int potencia(int n, int m) {

int res = 1;

while(m>0){ res*=n; m--; }

return res;

}




Factorial n! ( n 0 )

Caso Base: ( n = 0 ) 0! = 1

Caso General: ( n > 0 ) n! = n · ( n – 1 )!

// n>=0 (versión recursiva)


if (n==0) return 1;

return n*factorial(n-1);

}

// n>=0 (version iterativa)


int res = 1;

while(n>0){ res*=n; n--; }

return res;

}




Fibonacci fib(n) ( n 0 )

Caso Base: ( n 1 ) fib(n) = n

Caso General: ( n > 1 ) fib(n) = fib(n-2) + fib(n-1)

// n>=0 (versión recursiva)

int fibonacci(int n) {

if (n<=1) return n;

return fibonacci(n-2)+fibonacci(n-1);

}

// n>=0 (version iterativa)

int fibonacci(int n) { if (n<=1) return n; int aux[n+1]; aux[0] = 0; aux[1] = 1; for(int i=2; i<=n; i++) aux[i] = aux[i-2] + aux[i-1]; return aux[n]; }

tp 1 recursividad

Documents