14. Recursividad#

(★☆☆, ★★☆, ★★★) Esta notación indica la dificultad de cada ejercicio, de menor a mayor.

★☆☆ Para cada inciso, implementá una función recursiva que reciba un número z y un entero k y retorne:
1. z + k (sumando unos),
2. z * k (sumas sucesivas), y
3. z ^ k (multiplicaciones sucesivas).
★☆☆ Implementar una función recursiva que retorne la cantidad de dígitos de un número entero.
★☆☆ Implementar una función recursiva que reciba un entero no negativo y retorne dicho número espejado, es decir, para el 1234 retorna 4321.
★☆☆ Escribir una función recursiva que calcule la suma de Gauss, es decir, \(S(n)= 1 + 2 + 3 + ··· + n\).
★☆☆ Implementar una función recursiva que dados dos números n y b retorne True si n es potencia de b.
★☆☆ Escribir una función recursiva que encuentre el elemento máximo de una lista.
★☆☆ Escribir una función recursiva que calcule el n-ésimo número de la sucesión de Fibonacci. La misma se define como:

\(F_0 = 0\)

\(F_1 = 1\)

\(F_n = F_{n-1} + F_{n-2}\).

Dibuje un esquema (árbol de recursividad) de las llamadas recursivas para n = 6.
★★☆ Implementar una función recursiva que calcule el máximo común divisor (gcd) de 2 enteros x e y. El gcd de los enteros x e y es el mayor entero que divide a ambos números con resto cero.
- Resuelva primero por fuerza bruta: comience a probar números desde y en orden descendiente.
- Una mejora es utilizar la siguiente definición recursiva:
- si y es igual a 0, entonces gcd(x, y) es x
- si no gcd(x, y) es gcd(y, x % y).
- Un tercer algoritmo es:
```
   si m y n son iguales:
       m es el gcd
   si m es mayor a n:
       el gcd(m, n) es gcd(m - n, n)
   si no:
       el gcd(m, n) es gcd(m, n - m)
```
★☆☆ Escribir una función recursiva que dado un arreglo de números, retorne el máximo, usando dividir y conquistar.
★★☆ El triángulo de Pascal es un arreglo triangular de números que se define de la siguiente manera:
- Las filas se enumeran desde n = 0, de arriba hacia abajo.
- Los valores de cada fila se enumeran desde k = 0 (de izquierda a derecha).
- Los valores que se encuentran en los bordes del triángulo son 1.
- Cualquier otro valor se calcula sumando los dos valores contiguos de la fila de arriba.
Triángulo de Pascal

Entonces, por ejemplo el numero en la posicion (n, k) = (5, 2) es 10.
1. Escribir una función recursiva pascal(n, k) que calcule el número correspondiente. Tener en cuenta que:
  - pascal(n, 0) = pascal(n, n) = 1 si n >= 0
  - pascal(n, k) = pascal(n - 1, k) + pascal(n - 1, k - 1) si 0 < k < n.
2. Dibujar el árbol de recursividad para alguna llamada de interés.
★★☆ Escribir una función recursiva que sirva como anotador de un game de tenis, hasta ganar el game.

Reglas de un game de tenis:
- Si consideramos los puntajes de tenis como 0, 15, 30, 40, 50 (Ventaja), 60 (Game), un jugador gana el game siempre que alcanza los 60 puntos.
- Si un jugador A con 40 puntos anota, y el otro jugador B tiene menos de 40 puntos, entonces A pasa directamente a 60 puntos y gana el game.
- Si, en cambio, ambos jugadores tienen 40 puntos, quien anota pasa a tener 50 puntos, o ventaja.
- Cuando un jugador tiene ventaja, puede ocurrir que gane el siguiente tanto, en cuyo caso gana el game, o puede ocurrir que el oponente gane el tanto, entonces pasan a tener ambos 40 puntos nuevamente.
Ejemplo de ejecución:
```
A    B
00 - 00

Quien ganó el punto? <A>

-------------------------

A    B
15 - 00

Quien ganó el punto? <B>

-------------------------

A    B
15 - 15

Quien ganó el punto? <A>

-------------------------

A    B
30 - 15

Quien ganó el punto? <A>

-------------------------

A    B
40 - 15

Quien ganó el punto? <A>

-------------------------

A gana el game!
```

★☆☆ Escribir una especificación apropiada para la siguiente función. Se asume que n es un número entero:

def f(n):
    s = str(n)

    if len(s) <= 1:
        return s

    return s[-1] + f(int(s[:-1]))

★★☆ Dadas las siguientes funciones:

def g(x):
    return h(str(x))

def h(x):
    if len(xs) == 1:
        return int(xs)

    n = int(xs[0]) + int(xs[1])

    if len(xs) == 2:
        return n
    else:
        return n + h(xs[2:])

¿Qué retorna g(2112)?
Escriba una especificación para la función h().

★★★ Tenemos una tupla de tuplas donde, para cada tupla, se cumple siempre lo siguiente:
- La tupla tiene 3 elementos.
- El primer elemento de la tupla (izquierda) es None o una tupla como las que aquí se describen.
- El segundo elemento (centro) es un número.
- El tercer elemento de la tupla (derecha) es None o una tupla como las que aquí se describen.
- Todos las tuplas que se encuentren a la izquierda de una dada tupla, contienen números menores al número central de esa dada tupla.
- Todas las tuplas que se encuentren a la derecha de una dada tupla, contienen números mayores al número central de esa dada tupla.
Por ejemplo, la siguiente tupla cumple lo mencionado:
```
(((None, 4.2, None), 9.8, None), 17.5, ((None, 21.32, None), 28, (None, 32.7, None)))
```
Esto lo podemos dibujar como:
```
                          ( , 17.5, )
                           /       \
               ( , 9.8, None)      ( , 28, )
                /                   /     \
(None, 4.2, None)     (None, 21.32, None) (None, 32.7, None)
```
- Escribir una función recursiva que, mediante la estrategia de división y conquista, dada una variable con la tupla de tuplas y un número devuelva si el número está presente en la tupla de tuplas o no.
- Dar ejemplos de ejecución del código declarando las variables y funciones utilizadas.