Recursividaden c++

Metodolog´ de la Programaci´n II ıa o

Recursividad

Objetivos

Entender el concepto de recursividad. Conocer los fundamentos del dise˜o de algoritmos n recursivos. Comprender la ejecuci´n de algoritmos recursivos. o Aprender a realizar trazas de algoritmos recursivos. Comprender las ventajas e inconvenientes de la recursividad.

Recursividad

2

3.1 Concepto de Recursividad

Larecursividad constituye una de las herramientas m´s potentes en programaci´n. Es un concepto a o matem´tico conocido. Por ejemplo, a Definici´n recursiva o n! = 1 si n = 0 n · (n − 1)! si n > 0

Demostraci´n por inducci´n: demostrar para un o o caso base y despu´s para un tama˜o n, considee n rando que est´ demostrado para valores menores a que n.
 



Una funci´n que se llama a s´ mismase o ı denomina recursiva



Podemos usar recursividad si la soluci´n de un o problema est´ expresada en funci´n de si misma, a o aunque de menor tama˜o y conocemos la soluci´n n o no-recursiva para un determinado caso.
Recursividad 3

Ventajas: No es necesario definir la secuencia de pasos exacta para resolver el problema. Desventajas: Podr´ ser menos eficiente. ıa Para que una definici´nrecursiva est´ completao e mente identificada es necesario tener un caso base que no se calcule utilizando casos anteriores y que la divisi´n del problema converja a ese caso base. o 0! = 1

Ejemplo: xn = 1 si n = 0 x · xn−1 si n > 0

Recursividad

4

Ejemplo: C´lculo del factorial con n=3. a
3! = 3 * 2! 3! = 3 * 2! 2! = 2 * 1!

(1)
3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 0!

(2)
3! = 3 * 2!2! = 2 * 1! 1! = 1 * 0! 0! = 1 (caso base)

(3)
3! = 3 * 2! 2! = 2 * 1! 1! = 1 * 1 1

(4)
3! = 3 * 2! 2! = 2 * 1 1! = 1 * 1 = 1

(5)
3! = 3 * 2 2! = 2 * 1 = 2

(6)
3! = 3 * 2 = 6

(7)
Recursividad

(8)
5

3.2 Dise˜o de algoritmos recursivos n

Para resolver un problema, el primer paso ser´ la a identificaci´n de un algoritmo recursivo, es decir, o descomponer el problema deforma que su soluci´n o quede definida en funci´n de ella misma pero para o un tama˜o menor y la tarea a realizar para un caso n simple. . Tendremos que dise˜ar: casos base, casos genen rales y la soluci´n en t´rminos de ellos. o e Casos base: Son los casos del problema que se resuelve con un segmento de c´digo sin recursivio dad.
 

Siempre debe existir al menos un caso base
 

El n´meroy forma de los casos base son hasta u cierto punto arbitrarios. La soluci´n ser´ mejor o a cuanto m´s simple y eficiente resulte el conjunto a de casos seleccionados.

Recursividad

6

Casos generales: Si el problema es suficientemente complejo, la soluci´n se expresa, de forma recuro siva, como la uni´n de o 1. La soluci´n de uno o m´s subproblemas (de o a igual naturaleza pero menortama˜o). n 2. Un conjunto de pasos adicionales. Estos pasos junto con las soluciones a los subproblemas componen la soluci´n al problema general que o queremos resolver.
' $

Los casos generales siempre deben avanzar hacia un caso base. Es decir, la llamada recursiva se hace a un subproblema m´s a peque˜o y, en ultima instancia, los casos n ´ generales alcanzar´n un caso base. a
& %

Recursividad7

Ejemplo: // Solucion no estructurada int factorial (int n) { if (n==0) //Caso base return 1; else //Caso general return n*factorial(n-1); } // Solucion estructurada int factorial (int n) { int resultado; if (n==0) //Caso base resultado = 1; else //Caso general resultado = n*factorial(n-1); return resultado; }

Recursividad

8

3.3 Ejecuci´n de un m´dulo recursivo o o
En general, enla pila se almacena el entorno asociado a las distintas funciones que se van activando. En particular, en un m´dulo recursivo, cada llao mada recursiva genera una nueva zona de memoria en la pila independiente del resto de llamadas. Ejemplo: Ejecuci´n del factorial con n=3. o 1. Dentro de factorial, cada llamada return n*factorial(n-1); genera una nueva zona de memoria en la pila, siendo n-1...