{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"provenance":[],"authorship_tag":"ABX9TyOxsrDsXe/XD6UyyA2eq0vG"},"kernelspec":{"name":"python3","display_name":"Python 3"},"language_info":{"name":"python"}},"cells":[{"cell_type":"code","execution_count":1,"metadata":{"id":"x52tbTD_ik_F","executionInfo":{"status":"ok","timestamp":1679005786193,"user_tz":180,"elapsed":5,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}}},"outputs":[],"source":["def fatorial( n ):\n","  if n == 0:\n","    return 1\n","  else:\n","    return n * fatorial( n - 1 )"]},{"cell_type":"code","source":["print( fatorial( 5 ) )"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"C80ekzWDivRN","executionInfo":{"status":"ok","timestamp":1679005836261,"user_tz":180,"elapsed":3,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}},"outputId":"167cbd7f-2608-4098-eeb1-89fe8c3f45c4"},"execution_count":4,"outputs":[{"output_type":"stream","name":"stdout","text":["120\n"]}]},{"cell_type":"code","source":["def fatorial_nr( n ):\n","  retval = 1\n","\n","  for i in range( 2, n + 1 ):\n","    retval *= i\n","\n","  return retval"],"metadata":{"id":"Q-M6elyIi1jX","executionInfo":{"status":"ok","timestamp":1679005966773,"user_tz":180,"elapsed":6,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}}},"execution_count":5,"outputs":[]},{"cell_type":"code","source":["print( fatorial_nr( 3 ) )"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"cT_UN4xmjd2z","executionInfo":{"status":"ok","timestamp":1679005986366,"user_tz":180,"elapsed":5,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}},"outputId":"058d5843-32f5-44f5-aeb1-1d10a98fe2f3"},"execution_count":9,"outputs":[{"output_type":"stream","name":"stdout","text":["6\n"]}]},{"cell_type":"code","source":["def fib( n, a = 1, b = 1 ):\n","  if n == 0:\n","    return a\n","  elif n== 1:\n","    return b\n","  else:\n","    return fib( n - 1 ) + fib( n - 2 )"],"metadata":{"id":"CJ5HoM4pjgDK","executionInfo":{"status":"ok","timestamp":1679006299455,"user_tz":180,"elapsed":5,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}}},"execution_count":10,"outputs":[]},{"cell_type":"markdown","source":["# Exercício:\n","\n","É possível implementar recursivamente a função acima sem o crescimento exponencial no número de chamadas recursivas?"],"metadata":{"id":"5rdkAb2ElGEi"}},{"cell_type":"code","source":["print( fib( 5 ) )"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"TqCPwTJJkvFD","executionInfo":{"status":"ok","timestamp":1679006470980,"user_tz":180,"elapsed":337,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}},"outputId":"cc8af428-8d38-4e00-edbb-ffc9474606ce"},"execution_count":15,"outputs":[{"output_type":"stream","name":"stdout","text":["8\n"]}]},{"cell_type":"code","source":["def hanoi( n, orig = 'A', dest = 'C', aux = 'B', count = 0 ):\n","\n","  if n == 1:\n","    print( f'Mova o disco do topo do pino {orig} para o pino {dest}' )\n","    return count + 1\n","  else:\n","    count = hanoi( n - 1, orig, aux, dest, count )\n","    count = hanoi( 1, orig, dest, aux, count )\n","    count = hanoi( n - 1, aux, dest, orig, count )\n","\n","    return count"],"metadata":{"id":"ZljddVPqlTrS","executionInfo":{"status":"ok","timestamp":1679008052170,"user_tz":180,"elapsed":424,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}}},"execution_count":25,"outputs":[]},{"cell_type":"code","source":["count = hanoi( 5 )\n","print( count )"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"IOU4fp8wpV4K","executionInfo":{"status":"ok","timestamp":1679008168614,"user_tz":180,"elapsed":8,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}},"outputId":"7015e677-c523-4219-bbdb-b0617381bc1e"},"execution_count":29,"outputs":[{"output_type":"stream","name":"stdout","text":["Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino A para o pino B\n","Mova o disco do topo do pino C para o pino B\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino B para o pino A\n","Mova o disco do topo do pino B para o pino C\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino A para o pino B\n","Mova o disco do topo do pino C para o pino B\n","Mova o disco do topo do pino C para o pino A\n","Mova o disco do topo do pino B para o pino A\n","Mova o disco do topo do pino C para o pino B\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino A para o pino B\n","Mova o disco do topo do pino C para o pino B\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino B para o pino A\n","Mova o disco do topo do pino B para o pino C\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino B para o pino A\n","Mova o disco do topo do pino C para o pino B\n","Mova o disco do topo do pino C para o pino A\n","Mova o disco do topo do pino B para o pino A\n","Mova o disco do topo do pino B para o pino C\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino A para o pino B\n","Mova o disco do topo do pino C para o pino B\n","Mova o disco do topo do pino A para o pino C\n","Mova o disco do topo do pino B para o pino A\n","Mova o disco do topo do pino B para o pino C\n","Mova o disco do topo do pino A para o pino C\n","31\n"]}]},{"cell_type":"code","source":["print( count )"],"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"bqRYJqMKpZSR","executionInfo":{"status":"ok","timestamp":1679008070275,"user_tz":180,"elapsed":5,"user":{"displayName":"Elias Salomão Helou Neto","userId":"05204382143186061711"}},"outputId":"9e3bf004-7930-440f-d683-85c88b3d1392"},"execution_count":27,"outputs":[{"output_type":"stream","name":"stdout","text":["7\n"]}]},{"cell_type":"code","source":[],"metadata":{"id":"DunMgNGerfdJ"},"execution_count":null,"outputs":[]}]}