introducao_recursividade.html 30 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683
  1. <!--
  2. Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
  3. Introdução à recorrência/recursividade em algoritmos
  4. LInE (Laboratory of Informatics in Education) - http://www.usp.br/line
  5. IME - USP
  6. Material didático
  7. Pode usar livrevemente este material para fins não comerciais, devendo sempre fazer referência à autoria.
  8. Sugestões/apontamento são bem vindos: leo@ime.usp.br (favor indicar no assunto "material de introducao 'a programacao")
  9. Prof. Leônidas de Oliveira Brandão
  10. http://www.ime.usp.br/~leo
  11. http://line.ime.usp.br
  12. http://www.matemtica.br
  13. -->
  14. <meta http-equiv='Content-Type' content='text/html; charset=UTF-8'>
  15. <meta name='keywords' content='mac0122, material, professores, leonidas de oliveira brandao'>
  16. <link rel='stylesheet' type='text/css' href='css_img_js_conf/all.css'>
  17. <link rel='stylesheet' type='text/css' href='css_img_js_conf/line_introducao_programacao.css'>
  18. <script src="css_img_js_conf/defineLInE.js"></script> <!-- referencia documentos internos -->
  19. <div class="pagina">
  20. <center><p>[
  21. <a href="#ideia" title="Ideia de recursividade">Ideia</a> &nbsp; | &nbsp;
  22. <a href="#exemplo" title="Exemplo de recursividade: fatorial n!">Exemplo</a> &nbsp; | &nbsp;
  23. <a href="#implementacao" title="Implementando funcoes recursivas">Funções</a> &nbsp; | &nbsp;
  24. <a href="#execucao" title="execucao da funcao recursiva fatorial">Execução</a> &nbsp; | &nbsp;
  25. <a href="#pg1" title="P.A. recursiva">P.A.</a> &nbsp; | &nbsp;
  26. <a href="#binarios" title="gerando recursivamente os binarios com k bits">Binários</a> &nbsp; | &nbsp;
  27. <a href="#hanoi" title="Problema das Torres de Hanoi">Hanói</a> &nbsp; | &nbsp;
  28. <a href="#fibonacci" title="nao fazer Fibonacci recursivo">Fibonacci</a> &nbsp;
  29. ]</p>
  30. </center>
  31. <p class="secao">Introdução à recorrência/recursividade em algoritmos</p>
  32. <p>
  33. Nesta seção examinaremos o conceito de <b>algoritmos recorrentes</b>, ou <b>recursivos</b>.
  34. A ideia de recursividade é a de um processo que é definido a partir de si próprio.
  35. No caso de um algoritmo, esse é definido invocando a si mesmo.
  36. <br/>
  37. Outros materiais sobre recursividade:
  38. <a href="#" onclick="trocaPagina('introducao_recursividade_exemplos.html')" title="detalhes sobre a implementacao do faotorial recursivo e busca binaria">fatorial recursivo e busca binária</a>;
  39. <a href="#" onclick="trocaPagina('introducao_recursividade_binarios.html')" title="ver a solucao para a geracao de numeros binarios">sobre gerao de números binários</a>.
  40. </p>
  41. <p>
  42. Exemplos de imagens envolvendo recursividade são os <i>fractais</i> geométricos,
  43. como no fractal que apelidamos de <i>Tetra-Círculo</i>, formado por circunferências com metade do raio original,
  44. construídas a partir dos pontos médios entre seus polos e seu centro, como na imagem abaixo.
  45. <center>
  46. <img src="img/recorrencia_fractal_tetracirculo.gif" title="formacao do Tetra-Circulo com niveis de recorrencia 0, 1 e 2" width="550" />
  47. <br/>
  48. <i>Fig. 1. Representações dos 3 primeiros níveis de recorrência para construir o fractal <b>tetra-círculo</b>.</i>
  49. </center>
  50. </p>
  51. <p>
  52. Após estudarem o material dessa página, examinem
  53. <a href="#" onclick="trocaPagina('introducao_recursividade_exemplos.html')" title="outros exemplos e como depurar">essa página</a>
  54. que tem mais exemplos de algoritmos recursivos.
  55. </p>
  56. <a name="ideia">
  57. <p class="secao">Ideia de recursividade</p>
  58. </a>
  59. <p>
  60. Na área da computação, existe um importante projeto cujo nome é uma brincadeira envolvendo recursividade, o projeto <b>GNU</b>.
  61. Uma das página do projeto, na qual é explicado o significado do acrônimo <i>GNU</i>, encontramos:
  62. <i>The name 'GNU' is a recursive acronym for <a href="http://www.gnu.org/" title="examine o GNU.org">"GNU's Not Unix"</a></i>.
  63. Que em uma tradução direta poderia ser:
  64. <i>GNU não é Unix</i>,
  65. </p>
  66. <p>
  67. Um outro exemplo de recursividade pode ser obtido ao conectar uma câmera à uma tela de computador, jogando a imagem capturada
  68. para a tela, usando como foco de captura a própria tela. Criamos a imagem a seguir dessa forma (usando <i>software</i> do projeto <i>GNU</i>).
  69. <center>
  70. <img src="img/recorrencia_tela_menor_limpa.png" title="camera filmando a si mesma" width="550" /><br/>
  71. <i>Fig. 2. Filmando uma tela com o resultado da filmagem.</i>
  72. </center>
  73. </p>
  74. <a name="introducao">
  75. <p class="secao">Exemplo inicial de função recursiva</p>
  76. </a>
  77. <p>
  78. Vamos examinar dois exemplos simples funções recursivas, que apenas imprimem um contador.
  79. Mas ilustraremos o comportamento em uma delas fazendo um impressão <b>antes</b> e na outra <b>após</b> a volta
  80. da chamada recursiva.
  81. <br/>
  82. <i>Simulando a função <b>pre(n,k)</b></i>. Alguma outra função invoca inicialmente
  83. <tt style="color:#00C;">pre(0,3)</tt>, ao entrar <tt style="color:#00C;">0!=3</tt> então executa
  84. <tt><verd>print</verd>(" k=%d" % 0)</tt> e dai a chamada
  85. <tt style="color:#00C;">pre(0+1,3)</tt>. Dentro de
  86. <tt style="color:#00C;">pre(1,3)</tt>, como <tt style="color:#00C;">1!=3</tt>, executa <tt><verd>print</verd>(" k=%d" % 1)</tt> e dai invoca
  87. <tt style="color:#00C;">pre(1+1,3)</tt>. Dentro de
  88. <tt style="color:#00C;">pre(2,3)</tt>, como <tt style="color:#00C;">2!=3</tt>, executa <tt><verd>print</verd>(" k=%d" % 2)</tt> e dai invoca
  89. <tt style="color:#00C;">pre(2+1,3)</tt>. Dentro de
  90. <tt style="color:#00C;">pre(3,3)</tt>, como <tt style="color:#00C;">3==3</tt>, executa <tt style="color:#00C;">return</tt>, voltando para a chamada
  91. <tt style="color:#00C;">pre(2,3)</tt>, mas não existe mais comandos a partir do ponto de retorno, então volta para a chamada
  92. <tt style="color:#00C;">pre(1,3)</tt>, na qual novamente não existe mais comandos, então volta para a chamada
  93. <tt style="color:#00C;">pre(0,3)</tt>, na qual novamente não existe mais comandos, então volta para a função que primeiro chamou a função.
  94. </p>
  95. <center>
  96. <table><tr><td>
  97. <table class="tbCodeLinCol">
  98. <tr class="tbCodeLinColH"><th colspan="2">Exemplo de Funções recursivas com impressão antes e depois da chamada recursiva</th></tr>
  99. <tr><th>C </th> <th>Python</th></tr>
  100. <tr valign="top"><td><table class="tbCode">
  101. <tr><td><pre><incl1>#include</incl1> &lt;stdio.h&gt;
  102. <verm>void</verm> pre (<verm>int</verm> k, <verm>int</verm> N) {
  103. if (k==N) return;
  104. <verd>printf</verd>(" k=%d\n", k);
  105. pre(k+1, N);
  106. }
  107. <verm>void</verm> pos (<verm>int</verm> k, <verm>int</verm> N) {
  108. if (k==N) return;
  109. pos(k+1, N);
  110. <verd>printf</verd>(" k=%d\n", k);
  111. }
  112. <verm>void</verm> main (<tt style="color:#15007f;">void</tt>) {
  113. <verd>printf</verd>("pre:\n");
  114. pre(0, 3);
  115. <verd>printf</verd>("pos:\n");
  116. pos(0, 3);
  117. }</pre></td></tr>
  118. </table></td>
  119. <td><table class="tbCode"><pre><verm>def</verm> pre (k, N) :
  120. if (k==N) : return;
  121. <tt style="color:#0000df;">print</tt>(" k=%d" % k);
  122. pre(k+1, N);
  123. <verm>def</verm> pos (k, N) :
  124. if (k==N) : return;
  125. pos(k+1, N);
  126. <tt style="color:#0000df;">print</tt>(" k=%d" % k);
  127. <verm>def</verm> main () :
  128. <tt style="color:#0000df;">print</tt>("pre:");
  129. pre(0, 3);
  130. <tt style="color:#0000df;">print</tt>("pos:");
  131. pos(0, 3);
  132. main();
  133. </pre></td></tr>
  134. </table></td></tr>
  135. </table></td><td>
  136. <table>
  137. <tr><td align="center"><img src="img/img_recursividade1_pre.png" title="sequencia de chamadas das funcoes 'pre'" width="250"/></td></tr>
  138. <tr><td align="center"><img src="img/img_recursividade1_pos.png" title="sequencia de chamadas das funcoes 'pos'" width="250"/></td></tr>
  139. <tr><td><i>Fig. 3. As imagens ilustram as <b>pilhas de execução</b> para as funções <tt style="color:#00C;">pre(0,3)</tt> e <tt style="color:#00C;">pos(0,3)</tt>.</td></tr>
  140. </table></td><td>
  141. </table>
  142. </center>
  143. </p>
  144. <a name="exemplo">
  145. <p class="secao">Exemplo de função ou definição recursiva</p>
  146. </a>
  147. <p>
  148. Para entender um novo conceito é sempre interessante examiná-lo sob alguma perpectiva conhecida, assim talvez valha a pena pensar na definição (simplificada) recursiva do conceito
  149. de <b>expressão aritmética (EA)</b>. O conceito de EA é introduzido ainda no ensino fundamental, mas de modo informal, a partir de exemplos, então como fazer para definir formalmente o conceito?
  150. Uma maneira de fazer isso é usar novamente uma definição recorrente, vejamos com fazer isso usando apenas operadores de soma e de subtração:
  151. <pre> EA := constante
  152. EA := EA + EA
  153. EA := EA * EA
  154. EA := (EA)
  155. EA := -EA</pre>
  156. </p>
  157. <p>
  158. Ou seja, na regra 1 trata do caso básico, qualquer constante numérica, por definição é uma EA (isso define a "base da recorrência"). As demais regras definem recursivamente uma EA, por exemplo, se EA1 e EA2 são uma expressões aritméticas corretas, então também são expressões aritméticas corretas as composições "EA + EA", "EA * EA", "(EA)" e "-EA".
  159. Experimente o conceito com "2" e "2-3" no lugar de EA1 e EA2.
  160. </p>
  161. <p>
  162. Entretanto, chamamos a atenção para essa definição ser uma simplificação, pois ela não elimina ambiguidades, e.g., para a expressão (sintaticamente correta) "2+3*2", existem dois possíveis resultados...
  163. Pois a sequência <tt>EA -> EA+EA -> 2+EA -> 2+EA*EA -> 2+EA*2 -> 2+3*2 -> 2+6 -> 8</tt> resulta 8, mas
  164. <tt>EA -> EA*EA -> EA*2 -> EA+EA*2 -> 2+3*2 -> 5*2 -> 10</tt>
  165. resulta 10. Para entender a ordem das substituições veja a imagem abaixo.
  166. </p>
  167. <p>
  168. <center>
  169. <img src="img/img_recorrencia_exp_arit_1.jpg" title="arvore de reconhecimento de EA resultando em 8" width="150"/> &nbsp;&nbsp;
  170. <img src="img/img_recorrencia_exp_arit_2.jpg" title="arvore de reconhecimento de EA resultando em 10" width="150"/>
  171. <br/>
  172. <i>Fig. 4. A árvore da esquerda produz como resultado para a expressão o valor 8 e a da direita resulta 10.</i>
  173. </center>
  174. </p>
  175. <p>
  176. Outro exemplo interessante é função fatorial, geralmente apresentada no Ensino Médio como <tt>n! = 1, sempre que n=0, caso contrário n! = n*(n-1)!</tt>.
  177. Ou seja, no caso geral, a definição da função usa ela própria, de modo recorrente, esse é o princípio de uma função recursiva/recorrente.
  178. Usando a notação usual de função matemática, a função fatorial pode ser definida como: <tt>f:D->I, sendo f(n) = { 1, se n=0; n*f(n-1), se n>0}</tt>.
  179. </p>
  180. <p>
  181. Um primeiro exemplo de função matemática intrinsicamente recursiva é a <i>função fatorial</i> (digamos <i>fat: IN -&gt; IN</i>).
  182. Geralmente no Ensino Médio essa função é apresentada de modo informal, a partir de exemplos:
  183. <i>fat(0) = 1</i>,
  184. <i>fat(1) = 1</i>,
  185. <i>fat(2) = 2</i> e
  186. generaliza-se afirmando que
  187. <i>fat(n) = n x (n-1) x (n-2) x ... x 2 x 1</i>.
  188. E o sentido das reticências é inferido.
  189. </p>
  190. <p>
  191. Mas pode-se apresentar uma definição foraml para <i>fatorial</i> dizendo-se que
  192. o fatorial de <i>0</i>, é <i>1</i> e que
  193. o fatorial de <i>n</i>, para <i>n &gt; 0</i>, é
  194. o produtudo de <i>n</i> pelo fatorial de <i>n-1</i>, ou seja,
  195. <!-- <br/>f(n) = { 1, se n=0; n*f(n-1), se n>0 }</i>
  196. $f:\mathbb{N}\rightarrow\mathbb{N}\\ f(n)=\left\{\begin{array}{ll} 1, & n=0\\ n*\mathbf{\textit{f(n-1)}}, & n>0\end{array}\right.$
  197. -->
  198. <center><img src="img/img_fatorial_def.png" title="f(n) = { 1, se n=0; n*f(n-1), se n&gt;0 }" width="250"/>
  199. <!-- <table>
  200. <tr><td></td> <td>&nbsp;&nbsp;/ 1, se n=0</td></tr>
  201. <tr><td> fat(n) = </td> <td>{</td></tr>
  202. <tr><td></td> <td>&nbsp;&nbsp;\ n x <b>fat(n-1)</b>, se n &gt; 0.</td></tr></table> -->
  203. </center>
  204. </p>
  205. <p>
  206. Assim, como no <i>lado direito</i> da definição da função <i>fatorial</i> usa-se a própria função
  207. <i>fatorial</i>, essa é uma definição recursiva.
  208. Todas as funções recursivas tem essa característica, o nome da função aparecer tanto à esquerda,
  209. quanto à direita do símbolo de atribuição (<i>=</i>).
  210. </p>
  211. <p>
  212. De modo prático, sem nos preocuparmos ainda com a implementação e execução de um algoritmo,
  213. para computar, por exemplo,
  214. <i>fat(4) = 4 x fat(3) = 4 x 3 x fat(2) = 4 x 3 x 2 x fat(1) = 4 x 3 x 2 x 1 x fat(0) = 4 x 3 x 2 x 1 x 1 = 24</i>.
  215. Para ver com mais detalhes como é realizada as chamadas recursivas na função fatorial,
  216. <a href="#" onclick="trocaPagina('introducao_recursividade_exemplos.html')" title="detalhes sobre a implementacao do faotorial recursivo">siga este apontador</a>.
  217. </p>
  218. <a name="implementacao">
  219. <p class="secao">Implementando recursiva para fatorial em <i>C</i> e em <i>Python</i></p>
  220. </a>
  221. <p>
  222. Geralmente as liguagens de programação permitem definições recursivas de funções.
  223. Comecemos examinando precisamente a função fatorial.
  224. Implementando-a de modo <b>iterativo</b> fazemos algo como <tt>fat = 1; for i de 2 até N : fat = fat * i;</tt>,
  225. ou seja, usamos uma variável contadora para enumerar os naturais entre 2 e N e interrompemos a repetição quanto
  226. <tt>i</tt> chegar a <tt>N</tt>.
  227. </p>
  228. <p>
  229. No caso da definição recursiva de <i>fatorial</i>, o processo de chamada recursiva deve ser interrompido quanto
  230. <tt>n</tt> tiver o valor <tt>0</tt>.
  231. Então essa condição deve aparece no início da definição da função (caso contrário, ocorrerá um <i>laço infinito</i>).
  232. Na tabela abaixo, apresentamos implementações recursivas para a função <i>fatorial</i>
  233. tanto na linguagem <b>C</b>, quanto em <b>Python</b>.
  234. </p>
  235. <center>
  236. <table class="tbCodeLinCol">
  237. <tr class="tbCodeLinColH"><th colspan="2">Função fatorial implementada recursivamente</th></tr>
  238. <tr><th>C </th> <th>Python</th></tr>
  239. <tr valign="top"><td><table class="tbCode">
  240. <tr><td><pre><incl1>#include</incl1> &lt;stdio.h&gt;
  241. <cyan>// Fatorial recursivo</cyan>
  242. <verm>int</verm> fatRec (<verm>int</verm> n) {
  243. if (n==0) return 1; <cyan>// final de recorrencia</cyan>
  244. return n * fatRec(n-1); <cyan>// senao devolve n x "o fatorial de n-1" (inducao)</cyan>
  245. }
  246. <cyan>// experimente invocar esta versao com msg para rastrear execucao</cyan>
  247. <verm>int</verm> fatRecDepuracao (<verm>int</verm> n) {
  248. <verm>int</verm> aux;
  249. if (n==0) { <verd>printf</verd>("fat(%d)\n", n); return 1; } <cyan>// final de recorrencia</cyan>
  250. aux = n * fatRecDepuracao(n-1); <cyan>// senao devolve n x "o fatorial de n-1" (inducao)</cyan>
  251. <verd>printf</verd>("fat(%d): devolve %d\n", n, aux);
  252. return aux;
  253. }
  254. <verm>int</verm> main (<verm>void</verm>) {
  255. <verm>int</verm> n;
  256. <verd>scanf</verd>("%d", &n);
  257. <verd>printf</verd>("O fatorial de %d e': %d\n", n, fatRec(n));
  258. return 1;
  259. }</pre></td></tr>
  260. </table></td>
  261. <td><table class="tbCode"><pre><cyan># Fatorial recursivo</cyan>
  262. <verm>def</verm> fatRec (n) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
  263. if (n==0) : return 1; <cyan># final de recorrencia</cyan>
  264. return n * fatRec(n-1); <cyan># senao devolve n x "o fatorial de n-1" (inducao)</cyan>
  265. <cyan># experimente invocar esta versao com msg para rastrear execucao</cyan>
  266. <verm>def</verm> fatRecDepuracao (n) :
  267. if (n==0) : <tt style="color:#0000df;">print</tt>("fat(%d)" % n); return 1; <cyan># final de recursao (final de "laco")</cyan>
  268. aux = n * fatRecDepuracao(n-1); <cyan># senao faca mais um "passo" (inducao)</cyan>
  269. <tt style="color:#0000df;">print</tt>("fat(%d): devolve %d\n", n, aux);
  270. return aux;
  271. <verm>def</verm> main () :
  272. n = int(input());
  273. <tt style="color:#0000df;">print</tt>("O fatorial de %d e': %d" % (n, fatRec(n)));
  274. main();
  275. </pre></td></tr>
  276. </table></td></tr>
  277. </table></center>
  278. </p>
  279. <a name="execucao">
  280. <p class="secao">Execução de funções recursivas</p>
  281. </a>
  282. <p>
  283. Vamos usar o exemplo do fatorial para ilustrar como é possível que o computador execute funções recursivas.
  284. O truque computacional é mais ou menos o seguinte:
  285. ao fazer a chamada <i>fat(n)</i>, em um contexto que denominaremos <i>n</i>,
  286. <ol>
  287. <li> inicia-se a execução do comando <i>n x fat(n-1)</i>, mas <i>fat(n-1)</i> ainda não é conhecido,
  288. desse modo registra-se em uma "pilha" (empilhar) este ponto de execução; e
  289. </li>
  290. <li> invoca-se novamente a função, dessa vez com <i>fat(n-1)</i> (contexto <i>n-1</i>);
  291. </li>
  292. <li> quando o computador tiver finalmente o valor para <i>fat(n-1)</i>, desempilha-se o contexto <i>n</i>
  293. (portanto, volta-se ao cômputo de <i>n x fat(n-1)</i>, mas agora <i>fat(n-1)</i> é conhecido),
  294. realiza-se a produto e devolve o resultado.
  295. </li>
  296. </ol>
  297. </p>
  298. <p>
  299. Exemplificando esse processo na função <tt>fatRec</tt> com <i>parâmetro efetivo</i> com valor <i>4</i>, ou seja, <i>f(4)</i>,
  300. executa-se o comando <tt>4 * fatRec(3)</tt> e, quando o computador tiver conseguido computar <tt>fatRec(3)</tt>,
  301. esse valor (<i>6</i>) é substituido no contexto <i>4</i> (i.e., <tt>4 * 6</tt>) e devolve-se o resultado desse produto
  302. (<i>24</i>).
  303. </p>
  304. <p>
  305. Vamos detalhar um pouco mais esse processo de recorrência, mas agora usando <tt>fatRec(3)</tt>.
  306. Na primeir coluna indicamos a ordem de execução de cada instrução (<tt>Ord.</tt>), na segunda o contexto <tt>n</tt>
  307. <pre style="font-size:0.8em">Ord. n Imprimir (esquema de execução)
  308. 1 3 fatRec(3)
  309. 2 2 = 3 * fatRec(2) --> fatRec(2)
  310. 3 1 = 2 * fatRec(1) --> fatRec(1)
  311. 4 0 = 1 * fatRec(0) --> fatRec(0)
  312. 5 0 = 1 <cyan>// final recorrencia, volta onde foi chamado</cyan>
  313. 6 1 = 1 * 1 = 1 <cyan>// final recorrencia 'fatRec(1)', volta para quem chamou</cyan>
  314. 7 2 = 2 * 1 = 2 <cyan>//</tt> final recorrencia 'fatRec(2)', volta para quem chamou</cyan>
  315. 8 3 = 3 * 2 = 6 <cyan>// final recorrencia 'fatRec(3)' e dai imprime o valor 6</tt></pre>
  316. </p>
  317. <p>
  318. Note que na ordem de cada instrução, separamos o comando <tt>k * fatRec(k-1)</tt> em duas instruções,
  319. primeiro obter o valor de <tt>fatRec(k-1)</tt>, digamos <tt>FK</tt>, e depois a instrução <tt>k * FK</tt>.
  320. </p>
  321. <a name="pg1">
  322. <p class="secao">Outro exemplo de função recursiva: cômputo da progressão de razão 1</p>
  323. </a>
  324. <p>
  325. Para um outro exemplo de implementação recursiva podemos usar o cômputo da progressão de razão 1, e.g. a soma dos
  326. naturais até <i>n</i>.
  327. <center>
  328. <i>Tab. 3. Códigos em <i>C</i> e em <i>Python</i> para computar <i>0+1+2+3+4+...+(n-1)+n</i> de modo recursivo.</i>
  329. <table class="tbCodeLinCol">
  330. <tr class="tbCodeLinColH"><th colspan="2">A soma dos naturais até <i>n</i></th></tr>
  331. <tr><th>C </th> <th>Python</th></tr>
  332. <tr><td><table class="tbCode"><pre><incl1>#include</incl1> &lt;stdio.h&gt;
  333. <cyan>// P.A.</cyan>
  334. <verm>int</verm> somaRec (<verm>int</verm> n) {
  335. if (n==0) return 0; <cyan>// final de recorrencia</cyan>
  336. return n + somaRec(n-1); <cyan>// senao devolve n + soma ate n-1 (inducao)</cyan>
  337. }
  338. <verm>int</verm> main (<verm>void</verm>) {
  339. <verm>int</verm> n;
  340. <verd>scanf</verd>("%d", &n);
  341. <verd>printf</verd>("A soma dos naturais ate' %d e': %d\n", n, somaRec(n));
  342. return 1;
  343. }</pre></td></tr>
  344. </table></td>
  345. <td><table class="tbCode"><pre><cyan># P.A.</cyan>
  346. <verm>def</verm> somaRec (n) :
  347. if (n==0) : return 0; <cyan># final de recorrencia</cyan>
  348. return n + somaRec(n-1); <cyan># senao devolve n + soma ate n-1 (inducao)</cyan>
  349. <verm>def</verm> main () :
  350. n = int(input());
  351. <tt style="color:#0000df;">print</tt>("A soma dos naturais ate' %d e': %d" % n, somaRec(n));
  352. main();
  353. </pre></td></tr>
  354. </table></td></tr>
  355. </table></center>
  356. </p>
  357. <p>
  358. Note que <b>não</b> é necessário colocar a palavra reservada <tt>else</tt> após o <tt>if</tt>, pois
  359. a linha após o comando <tt>if</tt> só será executada se, e somente se,
  360. a condição da seleção resultar falso, ou seja, se o comando subordinado ao <tt>if</tt> NÃO for
  361. executado.
  362. Por que mesmo? (se não deduzir a razão, consulte a <a href="#notaA" title="examinar a resposta">nota A</a> ao final)
  363. </p>
  364. <p>
  365. Experimente copiar os códigos para a função fatorial e para a enumeração dos primeiros naturais,
  366. eventualmente coloque mais mensagens para depuração (e.g. imprimir <tt>Entrei na funcao com n=%d</tt>
  367. e <tt>Chamei recursivamente com n-1=%d</tt>) e certifique-se que entendeu bem recorrência.
  368. </p>
  369. <a name="binarios">
  370. <p class="secao">Como gerar ordenadamente todos os números binário de <i>k</i> dígitos</p>
  371. </a>
  372. <p>
  373. Um exemplo interessante para ilustrar o quanto alguns programas ficam mais simples se deduzidos na forma recursiva é desenhar um algoritmo
  374. para gerar todos os números binários com exatamente <i>k</i> <i>bits</i> (considerandos os "zeros à esquerda").
  375. </p>
  376. <p>
  377. <center><table><tr><td><pre>Decimal Binário | Decimal Binário
  378. 0 0000 | 8 1000
  379. 1 0001 | 9 1001
  380. 2 0010 | 10 1010
  381. 3 0011 | 11 1011
  382. 4 0100 | 12 1100
  383. 5 0101 | 13 1101
  384. 6 0110 | 14 1110
  385. 7 0111 | 15 1111</pre></td>
  386. <td>&nbsp;&nbsp;&nbsp;&nbsp;
  387. <img src="img/img_recursividade_arvore_binaria.png" title="arvore binaria para gerar palavras de 3 bits" width="250"/>
  388. <br/>
  389. <i>Fig. 5. Ilustração da sequência recursiva a ser seguida pelo algoritmo.</i>
  390. </tr></table>
  391. <i>Exemplo: todos os binários com até 4 dígitos (com seu correspondente decimal à esquerda)</i>
  392. </center>
  393. </p>
  394. <p>
  395. Antes de ler o texto explicando como resolver este problema, pense um pouco sobre ele. Primeiro, tente por alguns minutos
  396. esquematizar um algoritmo para resolver o problema de modo iterativo (<i>não recursivo</i>), depois tente resolvê-lo de modo recursivo.
  397. Se conseguir resolver o desafio, poderá pereceber o quanto a recorrência simplifica a resolução desse problema.
  398. </p>
  399. <p>
  400. Entretanto, se você está com dificuldades para resolver o problema,
  401. <a href="#" onclick="trocaPagina('introducao_recursividade_binarios.html" title="ver a solucao para a geracao de numeros binarios">siga este apontador</a>
  402. para ver uma sugestão de como estruturar o pensamento para resolver o problema de forma recursiva.
  403. </p>
  404. <p>
  405. Agora que você sabe como gerar todos os binários com até <i>k</i> dígitos, pense em generalizar a problema, ou seja,
  406. gerar todos os números, em qualquer base, com até <i>k</i> dígitos.
  407. Espero que perceba que essa generalização é bem simples para quem resolveu o caso com base 2 (binário).
  408. </p>
  409. <p>
  410. As duas seções seguintes são conceitualmente mais sofisticadas, portanto mais difíceis de ser compreendidas por
  411. um aluno de um curso introdutório de programação, em particular, a próxima seção sobre as Torres de Hanói é mais difícil.
  412. Desse modo, estude-as apenas se estiver muito confortável com o conceito de recorrência.
  413. </p>
  414. <a name="hanoi">
  415. <p class="secao">Problema das Torres de Hanói</p>
  416. </a>
  417. <p>
  418. Pode-se notar nos exemplos anteriores que um algoritmo recursivo (geralmente) é mais simples de ser codificado.
  419. Um exemplo que ilustra ainda melhor essa facilidade é implementar um algoritmo para simular (ou computar) os movimentos
  420. do <b><a href="http://www.matematica.br/ihanoi" target="_blank" title="veja o problema no iMática">problema das Torres de Hanói</a></b>.
  421. <p>
  422. <p>
  423. Neste problema o objetivo é mover <i>n</i> discos da haste <i>A</i> para a haste <i>C</i>, seguindo as regras do "jogo"
  424. (e.g., nunca um disco maior pode ficar sobre um de diâmetro menor).
  425. Assim, para mover os <i>n</i> pode-se supor que exista um algoritmo que consiga realizar a movimentação mínima
  426. de <i>n-1</i> discos (indução) e invocá-lo para retirar todos os <i>n-1</i> discos que estão sobre si, movendo-os
  427. para a haste auxiliar <i>B</i>.
  428. Isso libera também a haste <i>C</i> e pode-se mover o maior disco de <i>A</i> para <i>C</i>, com o menor nũmero possível
  429. de moviemtos: apenas 1.
  430. Então, pode-se novamente invocar o algoritmo para mover otimamente os <i>n-1</i> que estão na haste <i>B</i> para a haste
  431. <i>C</i>, resolvendo o problema.
  432. </p>
  433. <p>
  434. A ideia acima está representada nas figuras abaixo e dela percebe-se claramente um algoritmo recursivo para resolver o
  435. problema.
  436. <center>
  437. <img src="img/ihanoi1.png" title="n discos em A"/>
  438. <img src="img/ihanoi2.png" title="maior em A, n-1 em B"/>
  439. <img src="img/ihanoi3.png" title="n-1 em B, maior em C"/>
  440. <img src="img/ihanoi4.png" title="n discos em C"/>
  441. <br/>
  442. <i>Fig. 6. Ilustração da sequência de movimentação mínima para 3 discos.</i>
  443. </center>
  444. </p>
  445. </p>
  446. Assim, movimentar minimamente os discos de A para C pode ser esquematizado no seguinte algoritmo recursivo:
  447. <pre>moverHanoi(n, A, C, B) - mover n discos de A para C, usando a haste B
  448. se n==1, entao mover disco do topo da haste A para a haste C - final de recorrencia
  449. senao
  450. moverHanoi(n-1, A, B, C) - mover otimamente n-1 discos de A para C (libera o ultimo)
  451. mover disco do topo da haste A para a haste C
  452. moverHanoi(n-1, B, C, A) - mover otimamente n-1 discos de B para C</pre>
  453. </p>
  454. <a name="fibonacci">
  455. <p class="secao">Nem todo algoritmo recursivo é eficiente</p>
  456. </a>
  457. <p>
  458. Entretanto, a recursividade pode não ser eficiente! O melhor exemplo de ineficiência é tentar implementar um algoritmo recursivo
  459. para gerar a <b>sequência de Fibonacci</b>: <i>1</i>, <i>1</i>, <i>2</i>, <i>3</i>, <i>5</i>, <i>8</i>, <i>13</i>, ...
  460. ou seja, matemamticamente podemos definir a função de Fibonacci <i>F<sub>n</sub> = 1</i>, se <i>n=1</i> ou <i>n=2</i>, senão
  461. <i>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></i>, para todo <i>n>2</i>.
  462. </p>
  463. <p>
  464. Uma implementação iterativa eficiente para gerar o <i>n</i>-ésimo termo da sequência de <i>Fibonacci</i> pode ser:
  465. <tt>F1=1; F2=1; for i de 3 até N : F = F1+F2; F1=F2; F2=F;</tt>
  466. </p>
  467. <p>
  468. Novamente a implementação recursiva tem um código mais "enxuto", porém exponencialmente ineficiente!
  469. Isso está ilustrado no código abaixo que implementa ambos e compara o tempo de execução tanto em <b>C</b> quanto em
  470. <b>Python</b>.
  471. <center>
  472. <table class="tbCodeLinCol">
  473. <tr class="tbCodeLinColH"><th colspan="2">A soma dos naturais até <i>n</i></th></tr>
  474. <tr><th>C </th> <th>Python</th></tr>
  475. <tr><td><table class="tbCode"><pre><incl1>#include</incl1> &lt;stdio.h>
  476. <incl1>#include</incl1> &lt;time.h> <cyan>// clock_t, clock()</cyan>
  477. <cyan>// Fibonacci iterado</cyan>
  478. <verm>int</verm> fib (n) { <cyan>// os finalizadores ';' sao opcionais em Python</cyan>
  479. <verm>int</verm> i, F1=1, F2=1, F;
  480. if (n&lt;3) return 1;
  481. for (i=3; i&lt;=n; i++) {
  482. F = F1+F2;
  483. F1 = F2;
  484. F2 = F;
  485. }
  486. return F;
  487. }
  488. <cyan>// Fibonacci recursivo</cyan>
  489. <verm>int</verm> fibRec (n) { <cyan>// os finalizadores ';' sao opcionais em Python</cyan>
  490. if (n==1 || n==2) return 1; <cyan>// final de recorrencia</cyan>
  491. return fibRec(n-1) + fibRec(n-2); <cyan>// senao devolve</cyan>
  492. }
  493. <verm>int</verm> main (<verm>void</verm>) {
  494. <verm>int</verm> n, fibA; clock_t tempo_inicial, tempo_final;
  495. <verd>scanf</verd>("%d", &n);
  496. tempo_inicial = clock(); <cyan>// "dispara o cronometro"...</cyan>
  497. fibA = fib(n);
  498. tempo_final = clock();
  499. <verd>printf</verd>("Iterativo: %3d - %3d em %f segundos\n",
  500. n, fibA, (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
  501. tempo_inicial = clock(); <cyan>// "dispara o cronometro"...</cyan>
  502. fibA = fibRec(n);
  503. tempo_final = clock();
  504. <verd>printf</verd>("Recursivo: %3d - %3d em %f segundos\n",
  505. n, fibA, (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
  506. return 1;
  507. }</pre></td></tr>
  508. </table></td>
  509. <td><table class="tbCode"><pre><tt style="color:#15007f;">import</tt> time; # para tempo 'time.time()'
  510. <cyan># Fibonacci iterado</cyan>
  511. <verm>def</verm> fib (n) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
  512. F1=1; F2=1;
  513. if (n<3) : return 1;
  514. for i in range(3, n+1) :
  515. F = F1+F2;
  516. F1 = F2;
  517. F2 = F;
  518. return F;
  519. <cyan># Fibonacci recursivo</cyan>
  520. <verm>def</verm> fibRec (n) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
  521. if (n==1 or n==2) : return 1; <cyan># final de recorrencia</cyan>
  522. return fibRec(n-1) + fibRec(n-2); <cyan># senao devolve</cyan>
  523. <verm>def</verm> main () :
  524. n = int(input());
  525. tempo_inicial = time.time(); <cyan># "dispara o cronometro"...</cyan>
  526. fibA = fib(n);
  527. tempo_final = time.time();
  528. <tt style="color:#0000df;">print</tt>("Iterativo: %3i - %3i em %f segundos" %
  529. (n, fibA, (tempo_final - tempo_inicial)));
  530. tempo_inicial = time.time(); <cyan># "dispara o cronometro"...</cyan>
  531. fibA = fibRec(n);
  532. tempo_final = time.time();
  533. <tt style="color:#0000df;">print</tt>("Recursivo: %3i - %3i em %f segundos" %
  534. (n, fibA, (tempo_final - tempo_inicial)));
  535. main();</pre></td></tr>
  536. </table></td></tr>
  537. </table></center>
  538. </p>
  539. <p>
  540. Se desejar tentar resolver o <i title="jogo proposto por Edouard Lucas em 1883">problema das Torres de Hanói</i>
  541. <a href="http://www.matematica.br/ihanoi" target="_blank"
  542. title="seguir para nossa implementação para a Torres de Hanói em JavaScript">seguir este apontador</a>.
  543. </p>
  544. <p class="porque">
  545. <a name="notaA">
  546. <!-- Tab. 3. Códigos em <i>C</i> e em <i>Python</i> para computar <i>0+1+2+3+4+...+(n-1)+n</i> de modo recursivo. -->
  547. <b>A</b>. Por que o código da tabela 1
  548. (seção <a href="#pg1" title="Outro exemplo de função recursiva: cômputo da progressão de razão 1">P.A. de razão 1</a>)
  549. não precisa de <tt>else</tt>?
  550. <br/>
  551. Note que traduzindo os comandos da função <tt>somaRec</tt> para o <i>Portugol</i>, ele seria:
  552. <br/>
  553. <tt>
  554. &nbsp; &nbsp; se (n==0) devolva 0; <cyan>//# final de recorrencia</cyan><br/>
  555. &nbsp; &nbsp; devolva n + somaRec(n-1);
  556. </tt>
  557. <br/>
  558. Assim, se a condição <tt>n==0</tt> resultar <i>verdadeiro</i>, então o comando <tt>devolva 0</tt>
  559. é executado, voltando para quem invocou <tt>somaRec(0)</tt> (que pode ser <tt>somaRec(1)</tt> ou a
  560. função <tt>main</tt>, se tinha sido digitado <i>0</i> para <tt>n</tt>).
  561. Desse modo, a única possibilidade do comando <tt>devolva n + somaRec(n-1)</tt> ser executado é
  562. <tt>n==0</tt> resultar <i>falso</i>
  563. e portanto a reservada <tt>else</tt> é desnecessária.
  564. </a>
  565. </p>
  566. <p class="autoria">
  567. <a href="https://www.ime.usp.br/~leo" target="_blank" title="seguir para a pagina do prof. Leônidas">Leônidas de Oliveira Brandão</a><br/>
  568. <a href="http://www.ime.usp.br/~leo" target="_blank" title="seguir para a página do LInE">http://line.ime.usp.br</a>
  569. </p>
  570. <p class="rodape">
  571. <b>Alterações</b>:<br/>
  572. 2020/08/20: acertos no formato<br/>
  573. 2020/08/15: novo formato, pequenas revisões<br/>
  574. 2020/08/13: novo formato, pequenas revisões<br/>
  575. 2020/06/18: novas imagens "img/img_fatorial_def.png" e "img/img_fatorial_fat3.png"; nova seção "Exemplo inicial de função recursiva"<br/>
  576. 2019/06/03: extensáo da seção "Exemplo de função ou definição recursiva";<br/>
  577. 2018/06/18: nova seção "como gerar binários";<br/>
  578. 2018/06/03: acrescentado versoes 'fatRecDepuracao(...)';<br/>
  579. 2018/06/03: versao inicial
  580. </p>
  581. </div>