Programación En C - Recursividad

http://computacion.cs.cinvestav.mx/~efranco
efranco.docencia@gmail.com

           

Recursión Programación recursiva Tipos de recursión Ejemplo: Factorial ¿Por qué escribir programas recursivos? ¿Cómo escribir una función en forma recursiva? ¿Qué pasa si se hace una llamada recursiva que no termina? Ejercicio de clase ¿Cuándo usar recursividad? ¿Cuándo NO usar recursividad?Recursión vs. Iteración Practica 05
Recursividad (Edgardo A. Franco) 2



La recursión o recursividad es un concepto amplio, con muchas variantes, y difícil de precisar con pocas palabras.

Recursividad (Edgardo A. Franco)

3

Recursividad (Edgardo A. Franco)

4



La Matrushka es una artesanía tradicional rusa. Es una muñeca de madera que contiene otra muñeca más pequeñadentro de sí. Esta muñeca, también contiene otra muñeca dentro. Y así, una dentro de otra.

Recursividad (Edgardo A. Franco)

5



La recursividad es un concepto fundamental en matemáticas y en computación. Es una alternativa diferente para implementar estructuras de repetición (iteración). Se puede usar en toda situación en la cual la solución pueda ser expresada como una secuencia demovimientos, pasos o transformaciones gobernadas por un conjunto de reglas no ambiguas.
6





Recursividad (Edgardo A. Franco)



La recursión es un recurso muy poderoso que permite expresar soluciones simples y naturales a ciertos tipos de problemas. Es importante considerar que no todos los problemas son naturalmente recursivos. Un objeto recursivo es aquel que aparece en ladefinición de si mismo, así como el que se llama a sí mismo.



Recursividad (Edgardo A. Franco)

7



Las funciones recursivas se componen de:
 Paso base: una solución simple para un caso particular (puede

haber más de un paso base). La secuenciación, iteración condicional y selección son estructuras válidas de control que pueden ser consideradas como enunciados.  Paso recursivo: unasolución que involucra volver a utilizar la función original, con parámetros que se acercan más al paso base. Los pasos que sigue el paso recursivo son los siguientes:
▪ El procedimiento se llama a sí mismo. ▪ El problema se resuelve, resolviendo el mismo problema pero de tamaño menor. ▪ La manera en la cual el tamaño del problema disminuye asegura que el paso base eventualmente se alcanzará.8

Recursividad (Edgardo A. Franco)



Asimismo, puede definirse un programa en términos recursivos, como una serie de pasos básicos, o paso base (también conocido como condición de parada), y un paso recursivo, donde vuelve a llamarse al programa. En un programa recursivo, esta serie de casos recursivos debe ser finita, terminando con un paso base. Es decir, a cada paso recursivo sereduce el número de pasos que hay que dar para terminar, llegando un momento en el que no se verifica la condición de paso a la recursividad. Ni el paso base ni el paso recursivo son necesariamente únicos.
Recursividad (Edgardo A. Franco) 9









Por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a otro Q y éste a su vez llama a P odirecta si P llama a P.
 Directa:

el programa directamente a si mismo.

o

subprograma

se

llama

 Indirecta: el subprograma llama a otro subprograma, y

éste, en algún momento, llama nuevamente al primero.

Recursividad (Edgardo A. Franco)

10

Escribe un programa que calcule el factorial (!) de un entero no negativo. :
 El factorial de n esta dado por:
������������! =
������=1

������

������! = 1 ������ 2 ������ 3 ������ 4 ������ … ������ ������ − 1 ������ ������

Recursividad (Edgardo A. Franco)

11

Definición recursiva del factorial: ������! =
     

1 ������ − 1 ! ������
   

→ ������������ ������ = 0 → sin ������ ≥ 1

0! = 1 1! = 1 2! = 2 3! = 6 4! = 24 5! = 120

2! = 2 * 1! 3! = 3 * 2! 4! = 4 * 3! 5! = 5 * 4!...