15.Funções Recursivas.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    },
    "toc": true
   },
   "source": [
    "<h1>Table of Contents<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\" style=\"margin-top: 1em;\"><ul class=\"toc-item\"><li><span><a href=\"#Funções-Recursivas\" data-toc-modified-id=\"Funções-Recursivas-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Funções Recursivas</a></span><ul class=\"toc-item\"><li><span><a href=\"#Fatorial\" data-toc-modified-id=\"Fatorial-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Fatorial</a></span></li><li><span><a href=\"#Torres-de-Hanoi\" data-toc-modified-id=\"Torres-de-Hanoi-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Torres de Hanoi</a></span></li><li><span><a href=\"#Palíndromo\" data-toc-modified-id=\"Palíndromo-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Palíndromo</a></span></li><li><span><a href=\"#Números-de-Fibonacci\" data-toc-modified-id=\"Números-de-Fibonacci-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Números de Fibonacci</a></span></li><li><span><a href=\"#Algoritmo-Recursivo\" data-toc-modified-id=\"Algoritmo-Recursivo-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Algoritmo Recursivo</a></span></li><li><span><a href=\"#Recursão-com-memoização\" data-toc-modified-id=\"Recursão-com-memoização-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Recursão com memoização</a></span><ul class=\"toc-item\"><li><span><a href=\"#Exercício\" data-toc-modified-id=\"Exercício-1.6.1\"><span class=\"toc-item-num\">1.6.1&nbsp;&nbsp;</span>Exercício</a></span></li></ul></li><li><span><a href=\"#Recursão-com-Backtracking-(Retrocesso)\" data-toc-modified-id=\"Recursão-com-Backtracking-(Retrocesso)-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Recursão com Backtracking (Retrocesso)</a></span></li><li><span><a href=\"#O-Problema-das-oito-Damas-do-Xadrez\" data-toc-modified-id=\"O-Problema-das-oito-Damas-do-Xadrez-1.8\"><span class=\"toc-item-num\">1.8&nbsp;&nbsp;</span>O Problema das oito Damas do Xadrez</a></span></li><li><span><a href=\"#Exercício\" data-toc-modified-id=\"Exercício-1.9\"><span class=\"toc-item-num\">1.9&nbsp;&nbsp;</span>Exercício</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Funções Recursivas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Uma função é chamada de recursiva se o corpo da função chama a própria função, direta ou indiretamente. Ou seja, o processo de execução do corpo de uma função recursiva pode, por sua vez, exigir a aplicação dessa função novamente. As funções recursivas não usam nenhuma sintaxe especial em Python, mas requerem algum esforço para entender e criar.\n",
    "\n",
    "Um padrão comum pode ser encontrado no corpo de muitas funções recursivas. O\n",
    "corpo começa com um caso base, uma declaração condicional que define o\n",
    "comportamento da função para as entradas que são mais fáceis de processar. No\n",
    "caso do fatorial de um número inteiro positivo, o caso base é o fatorial de $1$,\n",
    "que, por definição tem o valor $1$. Note que algumas funções recursivas poderão ter\n",
    "múltiplos casos base.\n",
    "\n",
    "Os casos base são seguidos por uma ou mais chamadas recursivas. As chamadas\n",
    "recursivas sempre têm um certo caráter: eles simplificam o problema original. As\n",
    "funções recursivas expressam a computação, simplificando os problemas de forma\n",
    "incremental."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Fatorial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "As funções recursivas muitas vezes resolvem os problemas de maneira diferente\n",
    "das abordagens iterativas. Considere a função\n",
    "para calcular o fatorial de $4$, isto é,  $4! = 4*3*2*1 = 24$.\n",
    "Uma implementação natural usando uma declaração while acumula o total\n",
    "multiplicando juntos cada inteiro positivo até n."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def fact_iter (n):\n",
    "    total, k = 1, 1\n",
    "    while k <= n:\n",
    "        total, k = total * k, k + 1\n",
    "    return total\n",
    "\n",
    "fact_iter (4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Por outro lado, uma implementação recursiva de fatorial pode expressar o\n",
    "fatorial de $n$ (ou $n!$) em termos do fatorial de $n-1$, isto é, $(n-1)!$, e o caso base\n",
    "da recursão é a forma mais simples do problema: $1! = 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%load_ext tutormagic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%%tutor -l python3 --tab --heapPrimitives\n",
    "def fact(n):\n",
    "    if n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n * fact(n-1)\n",
    "\n",
    "fact(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Essas duas funções fatoriais diferem conceitualmente. A função iterativa constrói o resultado a partir do caso base $1$, para o total final, multiplicando-se sucessivamente cada termo. A função recursiva, por outro lado, constrói o resultado diretamente do termo final, $n$, e o resultado do problema mais simples, fatorial $(n-1)$.\n",
    "\n",
    "À medida que a recursão \"desenrola\" através de sucessivas aplicações da função fatorial para instâncias de problemas mais simples e simples, o resultado é eventualmente construído a partir do caso base. A recursão termina passando o argumento $1$ para a função fatorial; o resultado de cada chamada depende do próximo até o caso base ser atingido."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Torres de Hanoi"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Uma aplicação muito elegante de resolução de problemas recursivos é a solução\n",
    "para um quebra-cabeças de matemática geralmente chamado de Torre de Hanói.\n",
    "Existem várias lendas a respeito da origem do jogo, a mais conhecida diz\n",
    "respeito a um templo Hindu, situado no centro do universo. Diz-se que Brahma\n",
    "supostamente havia criado uma torre com 64 discos de ouro e mais duas estacas\n",
    "equilibradas sobre uma plataforma. Brahma ordenou aos monges do templo que movessem todos os\n",
    "discos de uma estaca para outra seguindo as suas instruções. As regras eram\n",
    "simples: apenas um disco poderia ser movido por vez e nunca um disco maior\n",
    "deveria ficar por cima de um disco menor. Segundo a lenda, quando todos os\n",
    "discos fossem transferidos de uma estaca para a outra, o templo iria\n",
    "desmoronar."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O video a seguir mostra uma versão contendo apenas seis discos. A tarefa é mover\n",
    "a torre da primeira estaca para a terceira estaca, usando a estaca central\n",
    "como uma espécie de lugar de repouso temporário durante o processo.\n",
    "É interessante observar que o número mínimo de \"movimentos\" para conseguir\n",
    "transferir todos os discos da primeira estaca à terceira é $2^n - 1$, sendo $n$ o\n",
    "número de discos. Logo, para solucionar um Hanói de 6 discos, como no video\n",
    "foram necessários 63 movimentos.\n",
    "Para solucionar um Hanói de 7 discos, são necessários 127 movimentos;\n",
    "Para solucionar um Hanói de 15 discos, são necessários 32.767 movimentos;\n",
    "Para solucionar um Hanói de 64 discos, como diz a lenda, são necessários\n",
    "18.446.744.073.709.551.615 movimentos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<video controls src=\"videos/hanoi.webm\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Queremos desenvolver um algoritmo para esse quebra-cabeças. Você pode pensar em\n",
    "nosso algoritmo como um conjunto de etapas que precisam se realizadas ou\n",
    "como um programa que gera um conjunto de instruções. Por exemplo, se rotularmos\n",
    "as três estacas A, B e C. As instruções podem começar assim:\n",
    "\n",
    "- Mover o disco de A para C.\n",
    "- Mover o disco de A para B.\n",
    "- Mover o disco de C para B.\n",
    "- ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Este é um enigma difícil para a maioria das pessoas resolver. Claro, isso não é\n",
    "surpreendente, já que a maioria das pessoas não é treinada no projeto de\n",
    "algoritmos. O processo de solução é bastante simples, se você sabe sobre a\n",
    "recursão.  Comecemos por considerar alguns casos realmente fáceis. Suponha que tenhamos\n",
    "uma versão do quebra-cabeça com apenas um disco. Mover uma torre que consiste\n",
    "em um único disco é bastante simples; basta removê-lo de A e colocá-lo em\n",
    "C. Problema resolvido. OK, e se houver dois discos? Preciso obter o maior dos\n",
    "dois discos para postar C, mas o menor está sentado em cima dele. Eu preciso\n",
    "mover o disco menor para fora do caminho. Eu posso fazer isso, movendo-o para\n",
    "a estaca B. Agora, o disco grande em A, é claro, eu posso movê-lo para C e, em\n",
    "seguida, mover o disco menor da estaca B para a estaca C. Pronto."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Agora vamos pensar sobre uma torre de tamanho três. Para mover o disco maior\n",
    "para a estaca C, primeiro preciso mover os dois discos menores para fora do\n",
    "caminho. Os dois discos menores formam uma torre de tamanho 2. Usando o\n",
    "processo que descrevi acima, eu poderia mover essa torre (de dois discos) para a\n",
    "estaca B, e isso liberaria o maior disco para que eu possa movê-lo para\n",
    "a estaca C. Então eu só tenho que mover a torre de dois discos da estaca B para\n",
    "a estaca C. Resolver o caso do disco três resume-se em três etapas:\n",
    "\n",
    "1. Mova a torre de dois discos de A para B.\n",
    "2. Mova um disco de A para C.\n",
    "3. Mova a torre de dois discos de B para C."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A primeira e terceira etapas envolvem mover uma torre de tamanho dois.\n",
    "Felizmente, já descobrimos como fazer isso. É como resolver o quebra-cabeça com\n",
    "dois discos, exceto que movemos a torre de A para B usando C como o lugar de\n",
    "repouso temporário e, em seguida, de B para C usando A como temporário.\n",
    "Acabamos de desenvolver o esboço de um algoritmo recursivo simples para o\n",
    "processo geral de mover uma torre de qualquer tamanho de uma estaca para outra."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Algoritmo**: mover a torre de n-discos da fonte para o destino através do local\n",
    "de repouso:\n",
    "\n",
    "- **passo 1**: mova a torre de (n-1) discos da fonte para o lugar de repouso;\n",
    "- **passo 2**: mova a torre de 1 disco da origem para o destino;\n",
    "- **passo 3**: mova a torre de (n-1) discos do lugar de repouso para o destino."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Qual é o argumento básico para este processo recursivo? Observe como um\n",
    "movimento de n discos resulta em dois movimentos recursivos de n - 1 discos.\n",
    "Uma vez que estamos reduzindo n  de 1 a cada vez, o tamanho da torre\n",
    "eventualmente será 1. Uma torre de tamanho 1 pode ser movida diretamente,\n",
    "simplesmente movendo um único disco; não precisamos de chamadas recursivas para\n",
    "remover discos que estão acima. Corrigindo nosso algoritmo geral para incluir o\n",
    "caso base nos dá um algoritmo de movimento completo."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "**Exercicio**: Seu exercício será codificá-lo em Python. Lembre-se que a função `moveTower`\n",
    "precisará de parâmetros para representar o tamanho da torre, $n$; a estaca\n",
    "fonte; a estaca de destino; e a estaca de repouso temporário.  Vocês podem usar\n",
    "um int para $n$ e as strings \"A\", \"B\" e \"C\" para representar as estacas.\n",
    "Escreva também uma pequena função `hanoi` que invoca a função moveTower para\n",
    "mover uma torre de tamanho $n$ da estaca A para a estaca C e teste o algoritmo\n",
    "para os valores 3 e 4.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# Solução:\n",
    "def moveTower(n, source, dest, temp):\n",
    "    if n == 1:\n",
    "        print(\"Move disk from\", source, \"to\", dest+\".\")\n",
    "    else:\n",
    "        moveTower(n-1, source, temp, dest)\n",
    "        moveTower(1, source, dest, temp)\n",
    "        moveTower(n-1, temp, dest, source)\n",
    "        \n",
    "def hanoi(n):\n",
    "    moveTower(n, \"A\", \"C\", \"B\")        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "hanoi(6)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Veja como isso foi fácil? Às vezes, usar recursão pode tornar os problemas\n",
    "difíceis, quase triviais.  Então, nossa solução para a Torre de Hanói é um\n",
    "algoritmo \"trivial\" que requer apenas poucas linhas de código. O problema deste\n",
    "algoritmo está na eficiência do mesmo, quero dizer, quantas etapas ele requer\n",
    "para resolver um problema de tamanho determinado. Neste caso, a dificuldade é\n",
    "determinada pelo número de discos na torre. A questão que queremos responder é\n",
    "quantas etapas é necessária para mover uma torre de tamanho n?  Apenas olhando\n",
    "a estrutura do nosso algoritmo, você pode ver que mover uma torre de tamanho n\n",
    "exige que movamos uma torre do tamanho n-1 duas vezes, uma vez para deslocá-la\n",
    "para o maior disco e novamente para colocá-la novamente. Se adicionarmos outro\n",
    "disco à torre, essencialmente duplicamos o número de etapas necessárias para\n",
    "resolvê-lo. Em geral, resolver um quebra-cabeça de tamanho $n$ exigirá $2^n -\n",
    "1$ etapas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Os cientistas da computação chamam isso de um algoritmo de tempo exponencial,\n",
    "uma vez que a medida do tamanho do problema, $n$, aparece no expoente desta\n",
    "fórmula. Os algoritmos exponenciais explodem muito rapidamente e só podem ser\n",
    "resolvidos praticamente em tamanhos relativamente pequenos, mesmo nos\n",
    "computadores mais rápidos. Apenas para ilustrar o ponto, se nossos monges\n",
    "realmente começaram com uma torre de apenas 64 discos e movido um disco a cada\n",
    "segundo, 24 horas por dia, todos os dias, sem cometer um erro, ainda assim eles levariam\n",
    "mais de 580 bilhões de anos para completar sua tarefa. Considerando que o\n",
    "universo tem cerca de 15 bilhões de anos agora, não estou muito preocupado em\n",
    "virarmos poeira ainda.  Mesmo que o algoritmo para Torres de Hanoi seja fácil\n",
    "de expressar, pertence a uma classe conhecida como problemas intratáveis. Estes\n",
    "são problemas que requerem muito poder de computação (tempo ou memória) para\n",
    "serem resolvidos na prática, exceto para os casos mais simples."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Palíndromo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Um palíndromo é uma palavra, frase ou qualquer outra sequência de unidades (como uma cadeia de DNA) que tenha a propriedade de poder ser lida tanto da direita para a esquerda como da esquerda para a direita. Num palíndromo, normalmente são desconsiderados os sinais ortográficos (diacríticos ou de pontuação), assim como o espaços entre palavras. Exemplos:\n",
    "- radar\n",
    "- Socorram-me, subi no ônibus em Marrocos.\n",
    "- Was it a car or a cat I saw?\n",
    "- Olé! Maracujá, caju, caramelo.\n",
    "\n",
    "As frases formando um palíndromo também são chamadas de anacíclicas. Implemente uma função que verifica se um string é palíndromo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "code_folding": [],
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# solução\n",
    "def isPalindrome(s):\n",
    "    \n",
    "    def toChars(s):\n",
    "        s = s.lower()\n",
    "        ans = ''\n",
    "        for c in s:\n",
    "            if c in 'abcdefghijklmnopqrstuvwxyz':\n",
    "                ans = ans + c\n",
    "        return ans\n",
    "    \n",
    "    def isPal(s):\n",
    "        if len(s) <= 1:\n",
    "            return True\n",
    "        else:\n",
    "            return s[0] == s[-1] and isPal(s[1:-1])\n",
    "        \n",
    "    return isPal(toChars(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "# testes:\n",
    "print(isPalindrome(\"radar\"))\n",
    "print(isPalindrome(\"Socorram-me, subi no ônibus em Marrocos.\"))\n",
    "print(isPalindrome(\"Qualquer texto\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Números de Fibonacci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Os números de Fibonacci são os números na seguinte sequência de números inteiros, chamados de seqüência de Fibonacci, e caracterizados pelo fato de que cada número após os dois primeiros é a soma dos dois precedentes:\n",
    "\n",
    "```python\n",
    "0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...\n",
    "```\n",
    "\n",
    "Por definição, os dois primeiros números na sequência Fibonacci são 0 e 1, e cada número subsequente é a soma dos dois anteriores.\n",
    "\n",
    "A sequência $F_n$ dos números de Fibonacci é definida pela relação de recorrência:\n",
    "\n",
    "$F_{n} = F_{n-1} + F_{n-2}$, com $F_{0} = 0$ e $F_{1} = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Os números de Fibonacci aparecem muitas vezes em matemática, tanto que existe uma revista inteira dedicada ao estudo, o \\textit{Fibonacci Quarterly}. As aplicações dos números Fibonacci incluem algoritmos computacionais, como a técnica de busca Fibonacci e a estrutura de dados de heap Fibonacci, e gráficos chamados cubos Fibonacci utilizados para interligar sistemas paralelos e distribuídos. Eles também aparecem em configurações biológicas, como ramificação em árvores, filotaxis (o arranjo de folhas em um caule), os brotos de frutas de um abacaxi, a floração de uma alcachofra, uma samambaia desencadeada e o arranjo de brácteas de um cone de pinho (https://en.wikipedia.org/wiki/Fibonacci_number).  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A figura abaixo mostra uma parede de azulejos cujos comprimentos laterais são números sucessivos de Fibonacci:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![fibbonaci](img/fibonacci.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Algoritmo Recursivo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def fib(n):\n",
    "    if n == 0:\n",
    "        return 0\n",
    "    elif n == 1:\n",
    "        return 1\n",
    "    else:\n",
    "        return fib(n-1) + fib(n-2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "fib(35)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Vocês podem ter notado que quanto maior o argumento dado mais tempo a função leva para ser executada. Além disso, o tempo de execução aumenta rapidamente. Para entender por que, considere a Figura abaixo. Ela mostra o gráfico de chamada de fibonacci com n=4:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "![fibo](img/fibo.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "O gráfico de chamada mostra um conjunto de frames com linhas que unem cada frame aos frames das funções chamadas. Na parte de cima do gráfico, `fibonacci` com n=4 chama `fibonacci` com n=3 e n=2. Por sua vez, `fibonacci` com n=3 chama `fibonacci` com n=2 e n=1. E assim por diante.\n",
    "\n",
    "Contem quantas vezes fibonacci(0) e fibonacci(1) são chamadas. Essa é uma solução ineficiente para o problema, e piora conforme o argumento se torna maior."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursão com memoização"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Uma solução é acompanhar os valores que já foram calculados, guardando-os em um dicionário. Um valor calculado anteriormente que é guardado para uso posterior é chamado de memo. Aqui está uma versão com memoização de fibonacci:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "known = {0:0, 1:1}\n",
    "def fibonacci(n):\n",
    "    if n in known:\n",
    "        return known[n]\n",
    "    res = fibonacci(n-1) + fibonacci(n-2)\n",
    "    known[n] = res\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "%%time\n",
    "fibonacci(500)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "`known` é um dicionário que monitora os números de Fibonacci que já conhecemos. Começando com dois itens: 0 mapeia a 0 e 1 mapeia a 1.\n",
    "\n",
    "Sempre que `fibonacci` é chamada, ela verifica `known`. Se o resultado já estiver lá, pode voltar imediatamente. Se não for o caso, é preciso calcular o novo valor, acrescentá-lo ao dicionário e devolvê-lo.\n",
    "\n",
    "Ao executarmos essa versão de `fibonacci` podemos comparar com a original e descobrir que ela é muito mais rápida."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercício\n",
    "Considerando os termos da seqüência de Fibonacci cujos valores não excedam quatro milhões, encontre a soma dos termos com valor par."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Recursão com Backtracking (Retrocesso)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Muitos problemas podem ser resolvidos enumerando-se de forma sistemática todas as possibilidades de arranjos que formam uma solução para um problema. Vimos em aulas anteriores o seguinte exemplo:\n",
    "\n",
    "- Determinar todas as soluções inteiras de um sistema linear como:\n",
    "\n",
    "$$x_1 + x_2 + x_3 = C$$ com $$x_1 ≥ 0, x_2 ≥ 0, x_3 ≥ 0, C ≥ 0$$ e todos inteiros."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Algoritmo:\n",
    "\n",
    "- Para cada possível valor de $x_1$ entre $0$ e $C$\n",
    "- Para cada possível valor de $x_2$ entre $0$ e $C−x_1$\n",
    "- Faça:\n",
    "$$x_3 = C − (x_1 + x_2)$$\n",
    "\n",
    "- Imprima a solução $x_1 + x_2 + x_3 = C$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Abaixo temos o código de uma solução para o problema com $n = 3$ variáveis e constante $C$ passada como parâmetro:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def solution(C):\n",
    "    for x1 in range (0, C + 1):\n",
    "        for x2 in range (0, C - x1 + 1):\n",
    "            x3 = C - x1 - x2\n",
    "            print(\"%d +%d +%d =%d\" %(x1, x2, x3, C))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Nossa quetão é como resolver este problema para o caso geral, onde $n$ e $C$ são parâmetros?\n",
    "\n",
    "$$x_1 +x_2 +...+x_{n−1} +x_n = C$$\n",
    "\n",
    "A princípio deveríamos ter $n − 1$ laços encaixados. Mas não sabemos o valor de $n$. Só saberemos durante a execução do programa. A técnica de recursão pode nos ajudar a lidar com este problema:\n",
    "\n",
    "- Construir uma função com um único laço e que recebe uma variável $k$\n",
    "como parâmetro.\n",
    "- A variável $k$ indica que estamos setando os possíveis valores de $x_k$.\n",
    "- Para cada valor de $x_k$ devemos setar o valor de $x_{k+1}$ de forma recursiva!\n",
    "- Se $k == n$ basta setar o valor da última variável."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Em Python teremos uma função com o seguinte protótipo:\n",
    "\n",
    "```\n",
    "def solution(n, C, k, R, x):\n",
    "```\n",
    "\n",
    "A variável R terá o valor da constante C menos os valores já setados para variáveis em chamadas recursivas anteriores, i.e,\n",
    "\n",
    "$R = C − x_1 − . . . − x_{k−1}.$\n",
    "\n",
    "A lista x corresponde aos valores das variáveis.  Lembre-se que em Python a lista começa na posição 0, por isso as variáveis serão $x[0], . . . , x[n − 1]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Primeiramente temos o caso de parada (quando $k == n − 1$):\n",
    "\n",
    "```\n",
    "def solution(n, C, k, R, x):\n",
    "    if (k == n − 1):\n",
    "        #imprimindo a solução\n",
    "        for i in range (0 , n−1):\n",
    "            print(”%d + ” %x[i], end=””)\n",
    "        print(”%d =%d” %(R, C))\n",
    "     # ...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A função completa é:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "def solution(n, C, k, R, x):\n",
    "    if k == n - 1:\n",
    "        #imprimindo a solução\n",
    "        for i in range (0, n-1):\n",
    "            print(\"%d + \" %x[i], end=\"\")\n",
    "        print(\"%d = %d\" %(R, C))\n",
    "    else:\n",
    "        #seta cada possível valor de x[k] e faz recursão\n",
    "        for x[k] in range(0, R + 1):\n",
    "            solution(n, C, k + 1, R - x[k], x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A chamada inicial da função deve ter $k = 0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [],
   "source": [
    "import sys\n",
    "\n",
    "# Just to simulate command line call\n",
    "sys.argv = ['backtrack.py', 4, 7]\n",
    "# Comment this line in a real script.\n",
    "\n",
    "if len(sys.argv) != 3:\n",
    "    print(\"Usage: python backtrack.py n [num vars] C [cte int]\")\n",
    "else:\n",
    "    n = int(sys.argv[1])\n",
    "    C = int(sys.argv[2])\n",
    "    x = [0 for i in range(n)]\n",
    "    solution(n, C, 0, C, x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Um algoritmo de backtracking começa em um estado de inicialização predefinido e, em seguida, muda de estado em estado em busca de um estado final desejado. Em cada ponto do caminho, quando há uma escolha entre vários estados alternativos, o algoritmo escolhe um, possivelmente ao acaso, e continua. Se o algoritmo chegar a um estado que representa um resultado indesejável, ele retrocede (faz backtrack) até o último ponto em que houve uma alternativa inexplorada e tenta esta. Desta forma, o algoritmo busca de forma exaustiva em todos os estados ou atinge o estado final desejado.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A recursão é aplicada para retrocesso chamando uma função recursiva cada vez que um estado alternativo é considerado. A função recursiva testa o estado atual, e se é um estado final, o sucesso é relatado por todo o caminho de volta na cadeia de chamadas recorrentes. Caso contrário, existem duas possibilidades: (1) A função recursiva chama a si mesma num estado adjacente não testado; ou (2) Todos os estados adjacentes foram testados e a função recursiva relata falha na função que o chamou. Neste esquema, os registros de ativação na pilha de chamadas servem como a memória do sistema, de modo que, quando o controle retorna a uma função recursiva, pode retomar o lugar que deixou."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## O Problema das oito Damas do Xadrez"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "No problema das oito Damas no tabuleiro de Xadrez, oito damas são\n",
    "colocadas em um tabuleiro 8X8 de tal forma que as damas não se ameaçam.\n",
    "Uma dama pode atacar qualquer outra peça na mesma linha, coluna ou diagonal,\n",
    "então pode haver no máximo uma dama em cada linha, coluna e diagonal do\n",
    "tabuleiro. Não é óbvio que existe uma solução, mas a figura a seguir mostra uma."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<img src=\"img/damas.png\" alt=\"Drawing\" style=\"width: 800px;\"/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Backtracking é a melhor abordagem para resolver este\n",
    "problema:\n",
    "\n",
    "(a): colocamos a primeira dama no quadrado (0, 0) da\n",
    "coluna 0. Colocamos a segunda dama na coluna 1 no primeiro quadrado não\n",
    "atacado, ou seja (2, 1). Aplicando a mesma estratégia às colunas 2, 3 e 4,\n",
    "colocamos damas em quadrados (4, 2), (1, 3) e (3, 4).\n",
    "\n",
    "(b): Quando tentamos colocar uma dama na coluna 5, descobrimos que todos os\n",
    "quadrados estão sendo atacados, então voltamos para a coluna 4 e colocamos a\n",
    "dama no próximo quadrado, não sob ataque, o que é (7, 4)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "(c): No entanto, todos os quadrados da coluna 5 ainda estão sob ataque, e\n",
    "devemos voltar atrás para a coluna 4 novamente. Não há quadrados não testados\n",
    "na coluna 4, e voltamos para a coluna 3, onde tentamos o próximo quadrado não\n",
    "atacado em (6, 3). Agora podemos avançar novamente para a coluna 5 e assim por\n",
    "diante. Desta forma, encontraremos uma solução se houver uma.  Aqui está um\n",
    "algoritmo recursivo baseado na estratégia descrita. Inicialmente, o algoritmo é\n",
    "chamado com o valor de col igual a 0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def canPlaceQueen(col, board)\n",
    "    for each row in the board\n",
    "        if board[row][col] is not under attack\n",
    "            if col is the rightmost one\n",
    "                place a queen at board[row][col]\n",
    "                return True\n",
    "            else:\n",
    "                place a queen at board[row][col]\n",
    "                if canPlaceQueen(col + 1, board)\n",
    "                    return True\n",
    "                else\n",
    "                    remove the queen at board[row][col] (backtrack to previous column)\n",
    "    return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Exercício\n",
    "\n",
    "Escreva um programa em Python que tenta colocar $n$ damas com segurança em um tabuleiro $n$ X $n$. O programa deve imprimir uma solução ou uma mensagem dizendo que não há solução."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Solve N Queen Problem using backtracking\n",
    "\n",
    "global N\n",
    "\n",
    "def printSolution(board):\n",
    "    for i in range(N):\n",
    "        for j in range(N):\n",
    "            print(board[i][j], end=\" \")\n",
    "        print()\n",
    "\n",
    "\n",
    "# A utility function to check if a queen can\n",
    "# be placed on board[row][col]. Note that this\n",
    "# function is called when \"col\" queens are\n",
    "# already placed in columns from 0 to col -1.\n",
    "# So we need to check only left side for\n",
    "# attacking queens\n",
    "def isSafe(board, row, col):\n",
    "\n",
    "    # Check this row on left side\n",
    "    for i in range(col):\n",
    "        if board[row][i] == 1:\n",
    "            return False\n",
    "\n",
    "    # Check upper diagonal on left side\n",
    "    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):\n",
    "        if board[i][j] == 1:\n",
    "            return False\n",
    "\n",
    "    # Check lower diagonal on left side\n",
    "    for i, j in zip(range(row, N, 1), range(col, -1, -1)):\n",
    "        if board[i][j] == 1:\n",
    "            return False\n",
    "\n",
    "    return True\n",
    "\n",
    "\n",
    "def solveNQUtil(board, col):\n",
    "    # base case: If all queens are placed\n",
    "    # then return true\n",
    "    if col >= N:\n",
    "        return True\n",
    "\n",
    "    # Consider this column and try placing\n",
    "    # this queen in all rows one by one\n",
    "    for i in range(N):\n",
    "\n",
    "        if isSafe(board, i, col):\n",
    "            # Place this queen in board[i][col]\n",
    "            board[i][col] = 1\n",
    "\n",
    "            # recur to place rest of the queens\n",
    "            if solveNQUtil(board, col+1):\n",
    "                return True\n",
    "\n",
    "            # If placing queen in board[i][col]\n",
    "            # doesn't lead to a solution, then go back\n",
    "            board[i][col] = 0\n",
    "\n",
    "    # if the queen can not be placed in any row in\n",
    "    # this colum col then return false\n",
    "    return False\n",
    "\n",
    "\n",
    "def solveNQ():\n",
    "    board = [[0 for _ in range(N)] for _ in range(N)]\n",
    "\n",
    "    if not solveNQUtil(board, 0):\n",
    "        print(\"Solution does not exist\")\n",
    "    else:\n",
    "        printSolution(board)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    N = int(input())\n",
    "    solveNQ()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "livereveal": {
   "theme": "solarized",
   "transition": "slide"
  },
  "toc": {
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}