PDF de programación - Introducción a la recursividad

Introducción a la recursividad

Diseño y Análisis de Algoritmos

Introducción a la recursividad

Contenidos

Contenidos

1

Introducción

2 Ejemplos

3 Problemas variados

4 Problemas combinatorios

URJC

DAA

2 / 52

Introducción a la recursividad

Introducción

Introducción

URJC

DAA

3 / 52

Introducción a la recursividad

Introducción

¿Qué es la recursividad?

La mayoría de programadores piensa que la recursividad:

“surge cuando una rutina se llama a sí misma”

Es cierto, pero la recursividad es mucho más que eso

Debemos alejarnos de esa visión tan estrecha

Herramienta muy potente para la resolución de problemas
computacionales y matemáticos

No hay que evitarla porque “parezca” difícil

Es fundamental para el diseño de algoritmos, y por tanto, en la
asignatura

URJC

DAA

4 / 52

Introducción a la recursividad

Introducción

¿Qué es la recursividad?

Definición de descendientes, según el diccionario de la Real
Academia Española:

Descendientes: “hijos, nietos o personas que descienden de otra”

Es recursiva, pero no es muy clara. . .

Descender : “proceder, por natural propagación, de un mismo principio
o persona común, que es la cabeza de la familia”

No es recursiva, pero requiere saber qué significa “natural
propagación”, o “cabeza de familia”. . .

La siguiente es mucho mejor

“los hijos y los descendientes de los hijos”

∅

D(p) =

H(p) ∪ D(H(p))

si H(p) = ∅
si H(p) = ∅

H: hijos, D: descendientes, p: persona

URJC

DAA

5 / 52

Introducción a la recursividad

Introducción

¿Cuándo es útil aplicar la recursividad?

Especialmente útil cuando la “estructura” del problema, algoritmo o
los datos no es “lineal”:

Por supuesto, la recursividad también se puede emplear con
“estructuras lineales”

URJC

DAA

6 / 52

Iteración / BuclesArrays, listas, ...Grafos, Árboles, ...Recursividad Introducción a la recursividad

Introducción

Conceptos clave en la recursividad

La descomposición/simplificación de problemas

Debemos ser capaces de reconocer que para resolver un problema
primero podemos resolver subproblemas idénticos al original, pero
más sencillos o de menor tamaño

El concepto de inducción

Construimos nuestra solución suponiendo que ya sabemos la
solución a problemas más simples

El paradigma de programación declarativa

Hay que pensar en qué se va a hacer mucho más que en cómo se va a
hacer

URJC

DAA

7 / 52

Introducción a la recursividad

Introducción

Descomposición/simplificación de problemas

En general, simplificar, transformar, o descomponer un problema
en otros más sencillos o de menor tamaño suele ser una buena idea

La recursividad surge cuando este proceso genera problemas más
simples, o de menor tamaño, idénticos al original

URJC

DAA

8 / 52

sssssssProblemapDescomposiciónde problemasppppppSoluciónCombinaciónde solucionesResolución AUTOMÁTICA(salvo para los casos base) Introducción a la recursividad

Introducción

Descomposición/simplificación de problemas

Problemas muy sencillos o triviales

Casos base

Suelen aparecer cuando el “tamaño” del problema es muy pequeño

Problemas idénticos al original pero de menor tamaño

Casos recursivos

Aparecen cuando simplificamos el problema, de manera que los nuevos
subproblemas se aproximen a los casos base

Generalmente, hay que “reducir” parámetros hacia los casos base
n ← n − 1, n ← n/2, . . .

URJC

DAA

9 / 52

Introducción a la recursividad

Introducción

Concepto de inducción

Pensemos en los pasos que tomamos para realizar una demostración
por inducción

S(n) =

i =

n(n + 1)

2

S(1) =

i = 1 =

1(1 + 1)

2

n

i=1

1

i=1

n

i=1

1 Partimos de un caso base, para el que se cumple la definición

2 Suponiendo que se verifica para n − 1, demostrar que se cumple

para n

S(n) =

i = n +

i =

n−1

i=1

por la hipótesis de inducción, suponemos que se verifica para n − 1:


n(n − 1)

n(n − 1)

n(n + 1)

n2 + n

+ n =

=

+

=

2n
2

=

2

2

2

URJC

2
DAA

10 / 52

Introducción a la recursividad

Introducción

Concepto de inducción

Pensemos en los pasos que tomamos para implementar de manera
recursiva:

n

S(n) =

i

i=1

1 Establecer el caso base caso base: S(1) = 1 (también vale S(0) = 0)
2 Suponiendo que conocemos la solución a S(n − 1), construimos la

solución para S(n):

S(n) = n + S(n − 1)

Lo cual origina el siguiente algoritmo:

if(n==1)

return 1;

1 int sumatorio(int n){
2
3
4
5
6 }

else

return n + sumatorio(n-1);

URJC

DAA

11 / 52

Introducción a la recursividad

Introducción

El paradigma de programación declarativa

En el ejemplo anterior, no nos preocupa cómo se calculará S(n − 1),
nos vale con saber qué se calcula

En general, hay que pensar en qué se va a hacer mucho más que en
cómo se va a hacer

Suponemos que sabemos qué se resuelve (el subproblema), pero no
nos interesa saber cómo

A diferencia del paradigma imperativo, evitaremos pensar en cómo se
modifican los parámetros y variables a medida que se ejecuta un
programa paso a paso

URJC

DAA

12 / 52

Introducción a la recursividad

Introducción

El paradigma de programación declarativa

No perdemos tiempo en pensar cómo se resolverán los subproblemas

Si podemos, evitaremos pensar en el árbol de recursión

Por ejemplo, para números de Fibonacci saber que
F (n) = F (n − 1) + F (n − 2) es suficiente

Pensar en el árbol de recursión generalmente no aclara nada

URJC

DAA

13 / 52

76543210121032101432101210532101432101210 Introducción a la recursividad

Introducción

Plantilla para diseñar algoritmos recursivos

1 Reconocer los casos base

2 Simplificar o reducir el problema original hacia los casos base

3 Completar la solución, suponiendo que ya sabemos resolver los

subproblemas simplificados

URJC

DAA

14 / 52

Introducción a la recursividad

Introducción

Tipos de recursividad

Lineal (no final)

f (n, A) =



Lineal final (por cola)

si n = 1
si n > 1

g (n) = f



n,

1

1



1
0

1,2

1
A(i − 1)

si i = 1
si i ≥ 2

A(i) =

0
A(i − 1) + B(i − 1)

si i = 1
si i ≥ 2

g (n) = B(n)+A(n)

f (n, y ) =

f (n − 1, y + f (n − 2, 0))

si n = 1, 2
si n ≥ 3

g (n) = f (n, 0)

URJC

DAA

15 / 52

I
A · f (n − 1, A)



1 +n−2

1

i=1 f (i)



Múltiple



Mutua

B(i) =

Anidada

f (n, a, b) =

f (n) =

1 + y

a
f (n − 1, a + b, a)

si n = 0
si n ≥ 1

g (n) = f (n, 0, 1)

si n = 1, 2
si n ≥ 3

g (n) = f (n)

Introducción a la recursividad

Ejemplos

Ejemplos

URJC

DAA

16 / 52

Introducción a la recursividad

Ejemplos

Suma de los primeros n números naturales

n

i=1

i

S(n) =

1 Reconocer los casos base sencillos o triviales

S(1) = 1 y S(0) = 0

2 Simplificar o reducir el problema original hacia los casos base

El datos de entrada es n ≥ 0. Como los casos base aparecen para n = 1
y n = 0, lo lógico es reducir n, ¿pero en cuánto?

n ← n − 1 origina un algoritmo sencillo
n ← n/2, suponiendo n par, presenta dificultades (aunque conduciría a
un algoritmo más eficiente ya que disminuye n más rápidamente)

URJC

DAA

17 / 52

Introducción a la recursividad

Ejemplos

Suma de los primeros n números naturales

3 Completar la solución, suponiendo que ya sabemos resolver los

subproblemas simplificados

Supongo que conozco S(n − 1). ¿Qué operación necesitamos para
conseguir S(n)?

S(n) = S(n − 1) + n

es lo más sencillo

Supongo que conozco S(n/2). ¿Qué operación necesitamos para
conseguir S(n)?

n/2

n

S(n) =

i +

i = S(n/2) + ??? =

i=1

i=n/2+1

Se puede demostrar que:

S(n) = S(n/2) +

3n2
8

+

n
4

pero esto no siempre se ve

URJC

DAA

18 / 52

Introducción a la recursividad

Ejemplos

Suma de los primeros n números naturales

En este caso podemos simplificar la expresión:

S(n) = 2S(n/2) +

n2
4

esto es un poco más fácil

o

S(n) = 4S(n/2) − n
2

ahorras una multiplicación

URJC

DAA

19 / 52

(n/2)2S(n/2)S(n/2)S(n/2)S(n/2)S(n/2)S(n/2) Introducción a la recursividad

Ejemplos

Suma de los primeros n números naturales

Se pueden plantear funciones más sofisticadas (pero no
necesariamente más eficientes):

si n = 0

si n = 1

si n > 1 y n par

si n > 1 y n impar

0

1



3S( n
3S( n−1

S(n) =

2 ) + S( n

2 − 1)

2 ) + S( n+1
2 )

Esta función vale tanto para valores de n pares como impares

URJC

DAA

20 / 52

Introducción a la recursividad

Ejemplos

Nivel de recursividad

Apreciación subjetiva de alumnos de segundo curso de Grado en
Ingeniería Informática sobre su nivel de recursividad

¡Vamos a darle la vuelta a estos resultados!

URJC

DAA

21 / 52

0123450510152025Histograma: "Mi nivel de recursividad es excelente"(1 muy en desacurdo, 5 muy de acuerdo) Introducción a la recursividad

Ejemplos

Ejercicios que debéis saber hacer:

Producto lento (usando
sumas)

Suma lenta (usando
incrementos y decrementos
de uno en uno)

Sumar los dígitos de un
número

Contar los dígitos de un
número

Factorial

Potencia

Coeficientes binomiales

Números de Fibonacci

Sumatorio general

Escribir un número invertido

Torres de Hanoi

URJC

DAA

22 / 52

Introducción a la recursividad

Ejemplos

Ejemplos básicos

Producto lento para números naturales

Suma lenta para números naturales

f (a, b) =

a
a + f (a, b − 1)

f (a, b) =

a
f (a + 1, b − 1)

Sumar los dígitos de un número

f (n) =

n
n %10 + f (n/10)

Contar los dígitos de un número

f (n) =

1
1 + f (n/10)

si n < 10
si n ≥ 10

0



si b = 0
si b = 1
si b ≥ 2

si b = 0
si b ≥ 1

si n < 10
si n ≥ 10

URJC

DAA

23 / 52

Introducción a la recursividad

Ejemplos

Ejemplos básicos

Factorial

Potencia



n! =

pn =



1
n · (n − 1)!

1
p · pn−1

si n = 0
si n > 0

si n = 0
si n > 0

Coeficiente Binomial



n



p

=

Números de Fibonacci



1

n−1
+n−1


p−1

p

si (n = p)