Recursões simples

Pode ser que um algoritmo recursivo tenha apenas uma chamada recursiva. Muitas vezes, dependo de quando essa chamada é realizada (se no início ou no final do corpo da função), essas funções podem ser reescritas de maneira iterativa. Ainda assim, é muito mais fácil pensar recursivamente!

Trabalhando com listas:

a) Defina uma função recursiva para somar os elementos de uma lista.

b) Faça uma função recursiva que calcula o elemento máximo em um vetor.

c) Faça uma função recursiva que calcula o elemento mínimo em um vetor.

d) Faça uma função recursiva que calcula a média dos elementos de um vetor.
Trabalhando com matrizes:

a) Escreva uma função recursiva para decidir se uma matriz é simétrica.

b) Escreva uma função recursiva para transpor uma matriz quadrada.
Trabalhando com strings:

a) Faça uma função recursiva para decidir se uma palavra é palíndroma (exemplos de palíndromos são osso, somos, radar).

b) Faça uma função recursiva que receba uma string com valores separados por vírgula, e devolva uma lista. Por exemplo, para a string "ana,beto,carla", a função deverá devolver ["ana", "beto", "carla"].
Vamos mostrar uma tabela de valores de funções definidas recursivamente:

a) Defina uma função recursiva para mostrar na tela os valores do fatorial, começando de $1$ até um dado $n$.

b) Defina uma função recursiva para mostrar na tela os $n$ primeiros termos da sequência de Fibonacci.
Faça um programa em Python que calcule o máximo divisor comum (MDC) de dois números $m$, $n$. Você deve utilizar a seguinte regra do cálculo do MDC:

$$ mdc(m, n) = \begin{cases} m & \text{ se } n = 0 \text{ e }\\ mdc(n, m \% n) & \text{ se } n > 0. \end{cases} $$
Escreva uma função para calcular $a \cdot b$ usando apenas adição, onde $a$ e $b$ são inteiros não negativos.

Leitura de algoritmos recursivos

Pensar recursivamente não é algo gratuito. Isso requer muita prática, tanto na resolução de problemas, quanto na leitura de algoritmos recursivos. Por isso, é importante que as questões seguintes sejam respondidas sem um computador.

Vamos simular função. Sem o auxílio do computador, desenhe a pilha de chamadas com os valores das variáveis locais para cada chamada quando a função a seguir é executada com ${a = 48 + X + Y}$ e $b = 37$, onde $X$ corresponde aos dois últimos dígitos de seu RA e $Y$ aos dois primeiros. Descreva o que ela faz e dê um nome adequado.
```
def misterio(a, b):
    if (a < b):
        return 0
    else:
        return 1 + misterio(a - b, b)
```

Agora vamos ler funções. Para cada uma das funções abaixo, explique o que ela faz, claro, sem utilizar um computador! Se conseguir descobrir o que elas fazem rapidamente, você não precisará fazer testes de mesa, mas sempre pode ser útil simular as primeiras chamadas.

a) Uma operação binária.

def calcular(a, b):
    if (b == 1):
        return a
    else:
        return a * calcular(a, b - 1)

b) Outra operação binária.

def calcular(a, b):
    if (b == 1):
        return a
    else:
        return a + calcular(a, b - 1)

c) Não sei lidar com esse inteiro, tente você.

def eu(n):
    if n == 0:
        return True
    else:
        return voce(n - 1)

def voce(n):
    if n == 1:
        return True
    else:
        return eu(n - 1)

d) Muitos bits pra mim.

def agregar(lista, n):
    if n == 0:
        return 0
    else:
        return 2 * agregar(lista, n - 1) + lista[n-1]

e) Sou o primeiro.

 def pintar(matriz, i, j, n):
     if n <= 2:
         matriz[i][j] = 1
         matriz[i][j + 1] = 0
         matriz[i + 1][j] = 0
         matriz[i + 1][j + 1] = 1
     else:
         m = n // 2
         pintar(matriz, i, j, m)
         pintar(matriz, i, j + m, m)
         pintar(matriz, i + m, j, m)
         pintar(matriz, i + m, j + m, m)

Pilha de chamadas:

a) Considere a seguinte implementação de fatorial:
```
def fatorial(n):
    if n == 1:
        resposta = 1
    else:
        ultimo = fatorial(n - 1)
        resposta = ultimo * anterior
    return resposta
```
Faça uma representação da memória do computador no momento em que a chamada fatorial(1) retorna. Suponha que a chamada inicial é fatorial(3).

b) Agora, considere a seguinte função:
```
 def fibonacci(n):
     if n == 1 or n == 2:
         resposta = 1
     else:
         ultimo = fibonacci(n - 1)
         penultimo = fibonacci(n - 2)
         resposta = ultimo + penultimo
     return resposta
```
Faça uma representação da memória do computador na segunda vez em que uma chamada fibonacci(1) retorna. Suponha que a chamada inicial é fibonacci(4).

Recursão

(Notas de aula do Prof. Flávio) Vamos calcular o determinate de uma matriz usando cofatores. Seja $A$ uma matriz quadrada de ordem $n$. O menor complementar, $M_{ij}$, de um elemento $a_{ij}$ da matriz $A$ é definido como o determinante da matriz quadrada de ordem $(n - 1)$ obtida a partir da matriz $A$, excluindo os elementos da linha $i$ e da coluna $j$. O cofator $\alpha_{ij}$ de $A$ é definido como:

$$ \alpha_{ij} = (-1)^{i+j}M_{ij}. $$

O determinante de uma matriz quadrada $A$ de ordem $n$ pode ser calculado usando os cofatores da linha $i$ da seguinte maneira:

$$ det(A) = \alpha_{i1} a_{i1} + \alpha_{i2} a_{i2} + \dots + \alpha_{in} a_{in}. $$

O mesmo cálculo pode ser feito pelos cofatores da coluna $j$ da seguinte maneira:

$$ det(A) = \alpha_{1j} a_{1j} + \alpha_{2j} a_{2j} + \dots + \alpha_{nj} a_{nj}. $$

Faça uma rotina recursiva para calcular o determinante de uma matriz de ordem $n$ usando o método descrito acima. (Observe que existem outros métodos mais eficientes para se calcular o determinante, mas não os descreveremos aqui.)
Faça uma função recursiva para calcular $n \choose k$ sabendo que

$$ {n \choose n} = 1, \quad {n \choose 1} = n \quad \mbox{e} \quad {n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}. $$
Uma planta de uma casa é representada por uma matriz de caracteres onde # representa parede e . representa um espaço vazio. Escreva uma função que conte o número de cômodos na casa. No exemplo abaixo existem 5 cômodos.
O cadeado de Alice, que é de combinação de $n$ números como o da figura abaixo, enferrujou-se e ficou com o seguinte defeito: toda vez que gira um número, o número imediatamente acima gira junto. O seu objetivo é ajudar Alice a obter a combinação da sua senha pessoal: uma sequência de $n$ zeros! Como o cadeado está enferrujado, deve-se girar o menor número de vezes possível. A seguir, você deverá escrever uma função recursiva que receba o tamanho do cadeado $n$ e os $n$ números da combinação atual de cima para baixo e instrua Alice a abrir o cadeado.

a) Em português: descreva o(s) caso(s) básicos do problema e descreva a instância do subproblema no caso geral.

b) Escreva a função recursiva completa.

Divisão e conquista

(Notas de aula do prof. Flávio) Um vetor tem $2^{k} -1$ valores inteiros (figura (a)), onde $k$ é um inteiro positivo, $k \ge 1$. Este vetor representa uma figura hierárquica (figura (b)) da seguinte maneira:

Você pode imaginar que este vetor está representando uma árvore genealógica de 3 níveis. Infelizmente, o usuário do programa que faz uso deste vetor necessita de algo mais amigável para ver esta estrutura. Faça uma rotina recursiva que dado este vetor $v$ e o valor $k$, imprime as seguintes linhas:

Dica: às vezes a função recursiva precisa resolver um problema um pouquinho mais geral que o original. E se o desenho tivesse que começar na coluna $x$ do terminal?
Faça uma função recursiva para calcular $x^n$, onde $n$ é um número grande. Tente fazer a função mais rápida que puder.
O método da bisseção ou busca binária é naturalmente recursivo:

a) Implemente o método da bisseção recursivamente para encontrar a raiz quadrada de um número.

b) Escreva uma função recursiva que receba um vetor ordenado decrescentemente e um número $x$. A função deverá devolver o menor índice do vetor que contém $x$ ou None se $x$ não estiver no vetor.
Faça uma função recursiva para buscar um elemento em uma lista (não necessariamente ordenada) usando a estratégia de divisão e conquista.

a) Compare com uma função iterativa para o mesmo problema e tente explicar porque ambas implementações (iterativa e recursiva) gastam praticamente o mesmo tempo.

b) Agora suponha que você tenha vários processadores e que eles possam executar ao mesmo tempo sobre a mesma lista. Você consegue traçar em uma estratégia para melhorar significativamente o tempo de busca desse elemento?
(difícil) Vimos dois algoritmos para multiplicar uma lista de números inteiros: uma versão iterativa tradicional e uma versão recursiva baseada em divisão e conquista que divide a lista em duas sublistas de mesmo tamanho.

a) Argumente que ambos algoritmos realizam o mesmo número de multiplicações no total.

b) Crie uma lista de 100000 números aleatórios entre 1 e 3 e execute os dois algoritmos. Há muita diferença no tempo de execução?

c) Crie outra lista de 100000 números aleatórios, mas dessa vez entre 10000000 e 30000000. Dessa vez deve haver uma diferença significativa no tempo de execução. Qual algoritmo foi mai rápido? Por quê?

Algoritmos de ordenação recursivos

Implemente a função intercalar que falta para o algoritmo do merge-sort.
O algoritmo quick-sort, assim como o algoritmo merge-sort, é baseado em divisão e conquista. A diferença principal é a forma com que os algoritmos dividem o problema. Enquanto no merge-sort apenas dividimos a lista no meio sem trocar os elementos de posição, no quick-sort reorganizamos os elementos em duas partes, não necessariamente de mesmo tamanho. A função particionar abaixo escolhe um elemento pivô arbitrário e reoganiza a lista de forma que todos os elementos antes do pivô sejam menores que o pivô e que todos os elementos após o pivô sejam maiores.
```
 def particionar(lista, inicio, fim):
     # TODO: implemente essa função
     return posicao_pivo

 def quick_sort(lista, inicio, fim):
     if inicio < fim:
         posicao_pivo = particionar(lista, inicio, fim)
         quick_sort(lista, inicio, posicao_pivo - 1)
         quick_sort(lista, posicao_pivo + 1, fim)
```
Implemente a função particionar que falta para o algoritmo do quick-sort.
Aplique o algoritmo de particionamento do quick-sort sobre a lista $(13,19,9,5,12,21,7,4,11,2,6,6)$ com pivô igual a 6.
Qual o valor retornado pelo algoritmo de particionamento se todos os elementos do vetor tiverem valores iguais?
Faça uma execução passo-a-passo do quick-sort com a lista $(4,3,6,7,9,10,5,8)$.
Modifique o algoritmo quick-sort para ordenar vetores em ordem decrescente.
Mostre passo a passo a execução da função merge considerando dois sub-vetores: $(3,5,7,10,11,12)$ e $(4,6,8,9,11,13,14)$.
Faça uma execução passo-a-passo do merge-sort para o vetor: $(30, 45, 21, 20, 6, 7 15, 100, 65, 33)$.
Re-escreva o algoritmo merge-sort para que este passe a ordenar um vetor em ordem decrescente.

Exercícios criativos

Joãozinho, aluno de algoritmos, definiu a sequência de Joãozinho da seguinte forma: um elemento é dado pela soma dos dois posteriores e é um para os dois primeiros. Justifique cada afirmação com que concordar ou implemente uma função para calcular o $n$-ésimo número de Joãozinho.

a) A sequência não está bem definida, já que não existe sequência de números que satisfaçam o que ele deseja.

b) Não é possível construir uma função recursiva porque reduzimos o problema de tamanho $n$ para dois problemas de tamanhos maiores $n+1$ e $n+2$.

c) Não pode haver uma base para a recursão porque o valor de cada elemento depende de um número infinito de outros elementos.
A torre de Hanói é um brinquedo com três estacas A, B e C e discos de tamanhos diferentes. O objetivo é mover todos os discos da estaca A para a estaca C respeitando as seguintes regras:
- Apenas um disco pode ser movido de cada vez.
- Um disco só pode ser colocado sobre um disco maior.
a) Tente escrever uma função recursiva que receba um número $n$ do teclado e instrua o usuário a resolver a torre de Hanói com $n$ discos. Tente argumentar porque sua função realiza o menor número de movimentos possível.

b) Um desafio: (Manber) Vamos resolver uma variante do problema. O objetivo ainda é mover todos os discos para uma estaca respeitando as regras acima, mas agora os discos podem estar espalhados entre as três estacas. Cada uma tem um número qualquer de discos, mas eles ainda respeitam a propriedade de que um disco só pode estar sobre um disco maior. Tente escrever uma função recursiva que receba a configuração dos discos espalhados nas estacas e mostre uma sequência de instruções para mover todos os discos para a última estaca.