{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " # Aula de 23 de Março\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos continuar explorando as possibilidade da recursão. Para isso, a ideia é resolver um problema clássico, a da séria de fibonacci.\n",
    "\n",
    "A ideia é bem simples, a base da série, $F_1 e F_2$ valem ambos 1. Para seguir em frente e encontrar $F_3$, basta somar $F_1$ e $F_2$.\n",
    "Só que isso é válido para qualquer $F_n$, ou seja $F_n = F_{n-1} + F_{n-2}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mas, antes de pensar em resolver o problema, vamos a boa prática de hoje. Será que dá para imaginar qual seria o resultado esperado, possibilitando a criação de testes automatizados, mesmo antes de começar?\n",
    "\n",
    "A resposta é simples e é positiva, mas para isso é bem importante conhecer a assinatura da função que vamos usar. Pensando nisso, se queremos que uma função devolva o n-ésimo número de Fibonacci, precisamos de uma função que receba um parâmetro inteiro $n$. Que tal?\n",
    "\n",
    "__function fibo(n)__\n",
    "\n",
    "Conhecendo a função podemos pensar em testes para ela como?\n",
    "\n",
    "__fibo(1) == 1 __\n",
    "\n",
    "__fibo(3) == 2 __\n",
    "\n",
    "__fibo(10) == 55__\n",
    "\n",
    "Conhecendo alguns resultados podemos escrever testes automatizados:\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Deu certo para 1\n",
      "Deu certo para 2\n",
      "Deu certo para 10\n",
      "Final dos testes\n"
     ]
    }
   ],
   "source": [
    "function testafibo()\n",
    "  if fibo(1) == 1\n",
    "    println(\"Deu certo para 1\")\n",
    "  end\n",
    "  if fibo(3) == 2\n",
    "    println(\"Deu certo para 2\")\n",
    "  end\n",
    "  if fibo(10) == 55\n",
    "    println(\"Deu certo para 10\")\n",
    "  end\n",
    "  println(\"Final dos testes\")\n",
    "end\n",
    "testafibo()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A função de testes acima verifica se a função __fibo()__ devolve o resultado correto para três casos. Mas, ela tem um defeito, ela imprime mensagens demais, o que pode ser ruim. Considerando isso, vamos ver o primeiro fundamento importante com relação a testes automatizados.\n",
    "\n",
    "## Se o teste passou, ele deve indicar apenas isso\n",
    "\n",
    "Levando em conta o que foi escrito acima, podemos mudar o nosso teste para:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Final dos testes\n"
     ]
    }
   ],
   "source": [
    "function testafibo()\n",
    "  if fibo(1) != 1\n",
    "    println(\"Não deu certo para 1\")\n",
    "  end\n",
    "  if fibo(3) != 2\n",
    "    println(\"Não deu certo para 2\")\n",
    "  end\n",
    "  if fibo(10) != 55\n",
    "    println(\"Não eu certo para 10\")\n",
    "  end\n",
    "  println(\"Final dos testes\")\n",
    "end\n",
    "testafibo()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Agora de posse da nossa função de testes, podemos escrever a nossa função de Fibonacci"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function fibo(n)\n",
    "    if n <= 2\n",
    "        return 1\n",
    "    else\n",
    "        return fibo(n - 1) + fibo(n - 2)\n",
    "    end\n",
    "end\n",
    "fibo(5)"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "É interessante notar que apesar de ser um dos exemplos clássicos de uso de recursão, o algoritmo acima é extremamente ineficiente. A razão é simples, cada vez que é feita a chamada, toda os valores de Fibonacci são recalculados para os valores de $n$ e $n - 1$.Veja o exemplo para 5 abaixo.\n",
    "\n",
    "![fibo5.png](fibo5.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos ver agora um outro problema, o cálculo do maior divisor comum entre dois números através do algoritmo de Euclides. Basicamente ele diz que o MDC de dois números $a$ e $b$, é igual ao MDC de $b$ e $r$, onde $r = a \\% b$.\n",
    "Quando esse resto for zero, chegamos a solução, que é $b$.\n",
    "\n",
    "Vamos a um exemplo abaixo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Os números são: 3 7 e o resto é: 3\n",
      "Os números são: 7 3 e o resto é: 1\n",
      "Os números são: 3 1 e o resto é: 0\n"
     ]
    },
    {
     "ename": "DivideError",
     "evalue": "DivideError: integer division error",
     "output_type": "error",
     "traceback": [
      "DivideError: integer division error",
      "",
      "Stacktrace:",
      " [1] rem(::Int64, ::Int64) at ./int.jl:233",
      " [2] top-level scope at In[51]:15"
     ]
    }
   ],
   "source": [
    "a = 3\n",
    "b = 7\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "a = b\n",
    "b = r\n",
    "r = a % b\n",
    "println(\"Os números são: \", a, \" \", b, \" e o resto é: \", r)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Inspirado no exemplo acima, podemos começar escrevendo uns testes para a nossa função, lembrando sempre que so devemos apontar os casos de erro ou o final dos testes.\n",
    "\n",
    "Vamos usar o seguinte cabeçalho: __function MDC(a, b)__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Acabou os testes\n"
     ]
    }
   ],
   "source": [
    "# Aqui vamos escrever os testes da função MDC(a, b)\n",
    "function testaMDC()\n",
    "    if MDC(3298, 2031)!= 1\n",
    "        println(\"deu erro, para 3298 e 2031\")\n",
    "    end\n",
    "    if MDC(120, 36)!= 12\n",
    "        println(\"deu erro, para 120 e 36\")\n",
    "    end\n",
    "    if MDC(36, 120)!= 12\n",
    "        println(\"deu erro, para 36 e 120\")\n",
    "    end    \n",
    "    println(\"Acabou os testes\")\n",
    "end\n",
    "\n",
    "testaMDC()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "MDC (generic function with 1 method)"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Aqui vamos escrever a função MDC(a, b)\n",
    "function MDC(a, b)\n",
    "    r = a % b\n",
    "    if r == 0\n",
    "        return b\n",
    "    elseif r == 1\n",
    "        return 1\n",
    "    else\n",
    "        return MDC(b, r)\n",
    "    end\n",
    "end    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "36"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "36 % 120\n"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Para acabar a aula, vamos ver que recursão apesar de ser simples, não é tão simples, pois exige um bom esforço mental. Qual é o resultado da função abaixo se ela é chamada com 4?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "function misterio(n)\n",
    "    if n <= 2      \n",
    "        return n\n",
    "    else\n",
    "        return misterio(n - 1) + n * misterio(n -2)\n",
    "    end\n",
    "end \n",
    "misterio(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "misterio(4) = m(3) + 4 * m(2)\n",
    "m(3) = m(2) + 3 * m(1) = 2 + 3 = 5\n",
    "m(2) = 2 "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.1.1",
   "language": "julia",
   "name": "julia-1.1"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.1.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}