PDF de programación - Tema 7 - Recursividad

Tema 7

Recursividad

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.1 Introducción
El concepto de recursión aparece en varias situaciones de la vida cotidiana,
aunque en muchas no sabemos que estamos en presencia de este
concepto, por ejemplo, sacar fotocopias de fotocopias, tomar una fotografía a
otra fotografía.
La recursión como herramienta de programación permite definir un objeto –
por ejemplo una estructura de datos - en términos de si mismo. Un caso
concreto de recursión ya visto en apartados anteriores son las listas
circulares, en donde una lista se llama a si misma.

Un ejemplo clásico en matemática es el factorial de un número, potencia o la
serie de Fibonacci.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.1 Concepto
Un programa o subprograma que se llama a si mismo se dice que es
recursivo.
El concepto de recursividad está ligado, en los lenguajes de programación,
al concepto de procedimiento o función. Un procedimiento o función es
recursivo cuando durante una invocación a él puede ser invocado a su vez él
mismo.
La recursividad es una de las formas de control más importantes en la
programación. Los procedimientos recursivos son la forma más natural de
representación de muchos algoritmos.
Un razonamiento recursivo tiene dos partes: la base y la regla recursiva de
construcción. La base no es recursiva y es el punto tanto de partida como de
terminación de la definición.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.1 Concepto
Entonces:

Base:

La secuenciación,

iteración condicional y selección son
estructuras válidas de control que pueden ser consideradas como
enunciados.

Regla recursiva: Las estructuras de control que se pueden formar

combinando de manera válida la secuenciación iteración condicional y
selección también son válidos.
Un conjunto de objetos está definido recursivamente siempre que:

(B) algunos elementos del conjunto se especifican explícitamente
(R) el resto de los elementos del conjunto se definen en términos de

los elementos ya definidos
donde

(B) se llama base
(R) se llama cláusula recursiva

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.1 Concepto
Observaciones:
1. El procedimiento se llama a si mismo
2. El problema se resuelve, resolviendo el mismo problema pero de tamaño
menor
3. La manera en la cual el tamaño del problema disminuye asegura que el
caso base eventualmente se alcanzará.

La recursividad es un método poderoso usado en inteligencia artificial, su
poder es que algunos conceptos complejos pueden expresarse en una forma
simple. Una definición recursiva difiere de una definición circular en que tiene
una forma de escapar de su expansión infinita. Este escape se encuentra en
la definición o porción no recursiva o terminal de la definición.

Las fórmulas recursivas pueden aplicarse a situaciones tales como prueba
de teoremas, solución de problemas combinatorios, algunos acertijos, etc.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.1 Concepto
Ejemplo 1: Factorial
Definición:

factorial (n) = n!
si n > 0
factorial (n) = n*n-1*n-2* ... * 1 si n > 0

el valor de 0! se define como factorial (0) = 1

Su definición recursiva es:

factorial (n) = 1
--> Base
factorial (n) = n* factorial (n-1)si n > 0 --> Regla recursiva

si n = 0

así para calcular el factorial de 4:

factorial (4) = 4 * factorial (3) = 4 * 6 = 24
factorial (3) = 3 * factorial (2) = 3 *2 = 6
factorial (2) = 2 * factorial (1) = 2 * 1 = 2
factorial (1) = 1 * factorial (0) = 1 * 1 = 1

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
La recursión puede darse de dos maneras:
Directa: El subprograma se llama directamente a si mismo. En la figura 7.1
el subprograma R, en alguna parte se llama a si mismo.

Subprograma R

....................................................

....................................................

....................................................

....................................................

llamada al subprograma R

....................................................

....................................................

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
Indirecta: Un programa llama a otro subprograma y este a su vez al primero El
subprograma A llama al B y este a su vez llama al primero A, es decir que luego de
tantas llamadas el control regresa al subprograma A. Otro caso de recursión indirecta
es el caso b) de la figura, que muestra como un subprograma llama a otro y este a un
tercero y una vez ejecutado el subprograma vuelve a donde fue llamado. En el
ejemplo de la figura el programa A llama al B y este al C; cuando finaliza la ejecución
C vuelve a donde fue llamado B y este a su vez al subprograma A – programa inicio.

Subprograma A

Subprograma A

llamada a B

llamada a B

llamada a A

Subprograma B

Subprograma B

llamada a C

Subprograma C

caso a)

caso b)

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

toda

definición
En
de
un
recursiva
problema
debe
se
establecer un estado
básico.
Es decir un
estado en el cual la
solución no se presente
de manera recursiva,
sino
directamente.
la entrada
Además
(datos) del problema
debe ir acercándose al
estado básico.

7. Recursividad
7.2 Recursion Directa e Indirecta
¿Cómo funciona la recursividad?

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
4!=4*3!

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
4!=4*3!

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
3!=3*2!

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
2!=2*1!

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
1!=1*0!=1*1

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
El factorial de un número entero positivo n se define como el producto del
mismo por el factorial del número anterior, siendo el estado básico
definido como 0! = 1.
Simbólicamente se expresa:

n! =

1

n * (n-1)!

si

si

n = 0

n > 0

Por lo que el factorial de:
0! = 1
1! = 1 * 0!
2! = 2 * 1! Esta definición de n! es recursiva ya que se

refiere a sí misma cuando invoca (n

– 1) !
3! = 3 * 2!
4! = 4 * 3!
..........
n! = n * (n-1)!

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.2 Recursion Directa e Indirecta
Luego nuestra función podría ser:
Function Factorial ( n : Integer ) : Integer;
begin
Condición de Salida
If n < 2 Then Factorial := 1
else Factorial := n * Factorial ( n – 1);
Cada llamada
nos acerca a
la salida

end;

Recursividad Infinita

Es muy importante que toda función recursiva tenga un caso en el que no se llame a
sí misma, o las llamadas serían infinitas y el programa no tendría fin.

Notese que si no chequeara inicialmente si n=0, la función se invocaría a sí misma
infinitas veces y nunca terminaría de ejecutarse (en realidad en poco tiempo daría
error). Por eso, siempre una función recursiva tiene una condición inicial en la que no
debe llamarse a sí misma.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad

7.3 Funcionamiento Interno

En la figura se ilustra el funcionamiento interno de la función factorial
para el caso en que N = 4.

Subprograma FAC(4)

factorial (4)

4 * 3!

Subprograma FAC(3)

factorial (3)

3 * 2!

Subprograma FAC(2)

factorial (2)

2 * 1!

Subprograma FAC(1)

factorial (1)

1 * 0!

devuelve FAC = 6

devuelve FAC = 2

devuelve FAC = 1

llamada a FAC(3)

llamada a FAC(2)

llamada a FAC(1)

llamada a FAC(0)

Subprograma FAC(0)

factorial (0)

devuelve FAC = 1

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

1

7. Recursividad

7.3 Funcionamiento Interno

Cuando esta función es invocada, por ejemplo, para hallar el factorial del
número 3, se crean en la memoria de la computadora las siguientes
instancias:

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad

7.3 Funcionamiento Interno

y al finalizar comienza el retorno a la invocación anterior efectuándose las
acciones que habían quedado pendientes.:

una

cómo

Observe
nueva
invocación a la función Factorial,
cuando aún no se ha terminado
la invocación anterior, no afecta
el valor de la variable local n que
se creó en la invocación anterior.
Esto
el
principio
las
funciones
procedimientos
recursivos, y que hace de estos
un mecanismo cualitativamente
superior;

esencialmente
fundamental de

es

o

la

función

o
por

cada instancia interrumpida
del
de
procedimiento,
una
llamada a otro procedimiento
o función, conserva sus datos
locales, aún
cuando el
o
procedimiento
función
pueda
ser
nuevamente
invocado.

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

7. Recursividad
7.4 Ejemplos

Ejemplo 1: Potencia de un numero
Definición recursiva para elevar un número a una potencia: Un número
elevado a la potencia cero produce la unidad; la potencia de un número se
obtiene multiplicándolo por sí mismo elevando a la potencia menos uno.
Por ejemplo:

32 = 3*(31) = 3*(3*30) = 3*(3*1)= 3*(3) = 9

J.T.P. Maria Eugenia Valesani - Programacion 1 - Fa.Ce.Na.

El algoritmo de resolución
ALGOR