{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MiniEP4 - MAC0110 - Introdução à Computação"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NOME: insira seu nome\n",
    "\n",
    "NUSP: insira seu número USP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parte 0 - Testes automatizados\n",
    "\n",
    "**NÃO ALTERE O CÓDIGO ABAIXO**\n",
    "\n",
    "Rode o trecho de código abaixo após terminar a tarefa para verificar se \n",
    "suas funções estão funcionando como o esperado. Não é necessário \n",
    "entender o código abaixo, mas já é possível entender :). \n",
    "\n",
    "Lembrando que, na correção, utilizaremos também testes adicionais."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 298,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tudo OK :)"
     ]
    }
   ],
   "source": [
    "import Statistics\n",
    "\n",
    "function example_function(n)\n",
    "    if n <= 0\n",
    "        return n\n",
    "    else\n",
    "        example_function(n - 1)\n",
    "    end\n",
    "end\n",
    "\n",
    "function test()\n",
    "    if fibo2(1) != 1 ||\n",
    "            fibo2(2) != 1||\n",
    "            fibo2(5) != 5||\n",
    "            fibo2(10) != 55\n",
    "            fibo2(50) != 12586269025\n",
    "        return \"Erro. Verifique sua função fibo2(n)\"\n",
    "    end\n",
    "    \n",
    "    test_a = Statistics.median([@elapsed example_function(150000) for i = 1:50])\n",
    "    test_b = Statistics.median([@elapsed fibo2(100000) for i = 1:50])\n",
    "    if test_a < test_b\n",
    "        return \"Parece que a sua implementação está muito lenta...\"\n",
    "    end\n",
    "    \n",
    "    return \"Tudo OK :)\"\n",
    "end\n",
    "\n",
    "print(test())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parte 1 - Função recursiva fibo2(a, b, n)\n",
    "\n",
    "Em sala, vocês viram a função recursiva `fibo(n)`, que calculava o n-ésimo número da sequência de Fibonacci. Vocês também viram que esta versão era extremamente ineficiente.\n",
    "\n",
    "Crie uma função recursiva `fibo2(n)` que recebe o parâmetro `n`, e retorna o n-ésimo número da sequência de Fibonacci, fazendo apenas uma chamada recursiva. Ou seja, sua função tem como objetivo ser mais eficiente do que a vista em sala.\n",
    "\n",
    "Você não precisa verificar se o valor de _n_ é válido. Ou seja, se _n_ não é negativo.\n",
    "\n",
    "**Obs:** você _DEVE_ usar recursão para resolver este exercício.\n",
    "\n",
    "**Dica:** Crie uma função auxiliar `fibo2(a, b, n)` para fazer o cálculo. Sabemos que para calcularmos o n-ésimo número da sequência basta fazermos `fibo(n - 1) + fibo(n - 2)`. Para resolver esse exercício, tente pensar ao contrário. Começamos com `1 + 1`, seguido de `2 + 1`, `3 + 2`... Pense em como utilizar os parâmetros `a` e `b` para isto."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "fibo2 (generic function with 2 methods)"
      ]
     },
     "execution_count": 290,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# escreva o código da parte 1 aqui\n",
    "\n",
    "function fibo2(a, b, n)\n",
    "    if n <= 2\n",
    "        return a\n",
    "    else\n",
    "        return fibo2(a + b, a, n-1)\n",
    "    end\n",
    "end\n",
    "\n",
    "function fibo2(n)\n",
    "    fibo2(1, 1, n)\n",
    "end"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Parte 2 - Comparando tempos\n",
    "\n",
    "Vamos utilizar o macro `@time` para calcular o tempo gasto em sua nova função `fibo2(n)` e comparar com a versão `fibo(n)` vista em sala. Rode o trecho de código abaixo, observe os tempos e responda: há diferença entre os tempos das duas versões? Qual o motivo por trás disso?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Tempo fibo(50): 0.343302865\n",
      "Tempo fibo2(50): 0.006946959\n"
     ]
    }
   ],
   "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",
    "\n",
    "println(\"Tempo fibo(50): \", @elapsed fibo(40))\n",
    "println(\"Tempo fibo2(50): \", @elapsed fibo2(40))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "_Responda as perguntas aqui_\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Playground\n",
    "\n",
    "Utilize a área abaixo para testar suas funções, criar novas e brincar com a linguagem. Essa parte não será avaliada."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 288,
   "metadata": {},
   "outputs": [],
   "source": [
    "# utilize essa área como playground"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.3.1",
   "language": "julia",
   "name": "julia-1.3"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.3.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}