123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683 |
- <!--
- Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
- Introdução à recorrência/recursividade em algoritmos
- LInE (Laboratory of Informatics in Education) - http://www.usp.br/line
- IME - USP
- Material didático
- Pode usar livrevemente este material para fins não comerciais, devendo sempre fazer referência à autoria.
- Sugestões/apontamento são bem vindos: leo@ime.usp.br (favor indicar no assunto "material de introducao 'a programacao")
- Prof. Leônidas de Oliveira Brandão
- http://www.ime.usp.br/~leo
- http://line.ime.usp.br
- http://www.matemtica.br
- -->
- <meta http-equiv='Content-Type' content='text/html; charset=UTF-8'>
- <meta name='keywords' content='mac0122, material, professores, leonidas de oliveira brandao'>
- <link rel='stylesheet' type='text/css' href='css_img_js_conf/all.css'>
- <link rel='stylesheet' type='text/css' href='css_img_js_conf/line_introducao_programacao.css'>
- <script src="css_img_js_conf/defineLInE.js"></script> <!-- referencia documentos internos -->
- <div class="pagina">
- <center><p>[
- <a href="#ideia" title="Ideia de recursividade">Ideia</a> |
- <a href="#exemplo" title="Exemplo de recursividade: fatorial n!">Exemplo</a> |
- <a href="#implementacao" title="Implementando funcoes recursivas">Funções</a> |
- <a href="#execucao" title="execucao da funcao recursiva fatorial">Execução</a> |
- <a href="#pg1" title="P.A. recursiva">P.A.</a> |
- <a href="#binarios" title="gerando recursivamente os binarios com k bits">Binários</a> |
- <a href="#hanoi" title="Problema das Torres de Hanoi">Hanói</a> |
- <a href="#fibonacci" title="nao fazer Fibonacci recursivo">Fibonacci</a>
- ]</p>
- </center>
- <p class="secao">Introdução à recorrência/recursividade em algoritmos</p>
- <p>
- Nesta seção examinaremos o conceito de <b>algoritmos recorrentes</b>, ou <b>recursivos</b>.
- A ideia de recursividade é a de um processo que é definido a partir de si próprio.
- No caso de um algoritmo, esse é definido invocando a si mesmo.
- <br/>
- Outros materiais sobre recursividade:
- <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>;
- <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>.
- </p>
- <p>
- Exemplos de imagens envolvendo recursividade são os <i>fractais</i> geométricos,
- como no fractal que apelidamos de <i>Tetra-Círculo</i>, formado por circunferências com metade do raio original,
- construídas a partir dos pontos médios entre seus polos e seu centro, como na imagem abaixo.
- <center>
- <img src="img/recorrencia_fractal_tetracirculo.gif" title="formacao do Tetra-Circulo com niveis de recorrencia 0, 1 e 2" width="550" />
- <br/>
- <i>Fig. 1. Representações dos 3 primeiros níveis de recorrência para construir o fractal <b>tetra-círculo</b>.</i>
- </center>
- </p>
- <p>
- Após estudarem o material dessa página, examinem
- <a href="#" onclick="trocaPagina('introducao_recursividade_exemplos.html')" title="outros exemplos e como depurar">essa página</a>
- que tem mais exemplos de algoritmos recursivos.
- </p>
- <a name="ideia">
- <p class="secao">Ideia de recursividade</p>
- </a>
- <p>
- Na área da computação, existe um importante projeto cujo nome é uma brincadeira envolvendo recursividade, o projeto <b>GNU</b>.
- Uma das página do projeto, na qual é explicado o significado do acrônimo <i>GNU</i>, encontramos:
- <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>.
- Que em uma tradução direta poderia ser:
- <i>GNU não é Unix</i>,
- </p>
- <p>
- Um outro exemplo de recursividade pode ser obtido ao conectar uma câmera à uma tela de computador, jogando a imagem capturada
- 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>).
- <center>
- <img src="img/recorrencia_tela_menor_limpa.png" title="camera filmando a si mesma" width="550" /><br/>
- <i>Fig. 2. Filmando uma tela com o resultado da filmagem.</i>
- </center>
- </p>
- <a name="introducao">
- <p class="secao">Exemplo inicial de função recursiva</p>
- </a>
- <p>
- Vamos examinar dois exemplos simples funções recursivas, que apenas imprimem um contador.
- Mas ilustraremos o comportamento em uma delas fazendo um impressão <b>antes</b> e na outra <b>após</b> a volta
- da chamada recursiva.
- <br/>
- <i>Simulando a função <b>pre(n,k)</b></i>. Alguma outra função invoca inicialmente
- <tt style="color:#00C;">pre(0,3)</tt>, ao entrar <tt style="color:#00C;">0!=3</tt> então executa
- <tt><verd>print</verd>(" k=%d" % 0)</tt> e dai a chamada
- <tt style="color:#00C;">pre(0+1,3)</tt>. Dentro de
- <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
- <tt style="color:#00C;">pre(1+1,3)</tt>. Dentro de
- <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
- <tt style="color:#00C;">pre(2+1,3)</tt>. Dentro de
- <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
- <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
- <tt style="color:#00C;">pre(1,3)</tt>, na qual novamente não existe mais comandos, então volta para a chamada
- <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.
- </p>
- <center>
- <table><tr><td>
- <table class="tbCodeLinCol">
- <tr class="tbCodeLinColH"><th colspan="2">Exemplo de Funções recursivas com impressão antes e depois da chamada recursiva</th></tr>
- <tr><th>C </th> <th>Python</th></tr>
- <tr valign="top"><td><table class="tbCode">
- <tr><td><pre><incl1>#include</incl1> <stdio.h>
- <verm>void</verm> pre (<verm>int</verm> k, <verm>int</verm> N) {
- if (k==N) return;
- <verd>printf</verd>(" k=%d\n", k);
- pre(k+1, N);
- }
- <verm>void</verm> pos (<verm>int</verm> k, <verm>int</verm> N) {
- if (k==N) return;
- pos(k+1, N);
- <verd>printf</verd>(" k=%d\n", k);
- }
- <verm>void</verm> main (<tt style="color:#15007f;">void</tt>) {
- <verd>printf</verd>("pre:\n");
- pre(0, 3);
- <verd>printf</verd>("pos:\n");
- pos(0, 3);
- }</pre></td></tr>
- </table></td>
- <td><table class="tbCode"><pre><verm>def</verm> pre (k, N) :
- if (k==N) : return;
- <tt style="color:#0000df;">print</tt>(" k=%d" % k);
- pre(k+1, N);
- <verm>def</verm> pos (k, N) :
- if (k==N) : return;
- pos(k+1, N);
- <tt style="color:#0000df;">print</tt>(" k=%d" % k);
- <verm>def</verm> main () :
- <tt style="color:#0000df;">print</tt>("pre:");
- pre(0, 3);
- <tt style="color:#0000df;">print</tt>("pos:");
- pos(0, 3);
- main();
- </pre></td></tr>
- </table></td></tr>
- </table></td><td>
- <table>
- <tr><td align="center"><img src="img/img_recursividade1_pre.png" title="sequencia de chamadas das funcoes 'pre'" width="250"/></td></tr>
- <tr><td align="center"><img src="img/img_recursividade1_pos.png" title="sequencia de chamadas das funcoes 'pos'" width="250"/></td></tr>
- <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>
- </table></td><td>
- </table>
- </center>
- </p>
- <a name="exemplo">
- <p class="secao">Exemplo de função ou definição recursiva</p>
- </a>
- <p>
- 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
- 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?
- Uma maneira de fazer isso é usar novamente uma definição recorrente, vejamos com fazer isso usando apenas operadores de soma e de subtração:
- <pre> EA := constante
- EA := EA + EA
- EA := EA * EA
- EA := (EA)
- EA := -EA</pre>
- </p>
- <p>
- 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".
- Experimente o conceito com "2" e "2-3" no lugar de EA1 e EA2.
- </p>
- <p>
- 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...
- 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
- <tt>EA -> EA*EA -> EA*2 -> EA+EA*2 -> 2+3*2 -> 5*2 -> 10</tt>
- resulta 10. Para entender a ordem das substituições veja a imagem abaixo.
- </p>
- <p>
- <center>
- <img src="img/img_recorrencia_exp_arit_1.jpg" title="arvore de reconhecimento de EA resultando em 8" width="150"/>
- <img src="img/img_recorrencia_exp_arit_2.jpg" title="arvore de reconhecimento de EA resultando em 10" width="150"/>
- <br/>
- <i>Fig. 4. A árvore da esquerda produz como resultado para a expressão o valor 8 e a da direita resulta 10.</i>
- </center>
-
- </p>
- <p>
- 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>.
- 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.
- 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>.
- </p>
- <p>
- Um primeiro exemplo de função matemática intrinsicamente recursiva é a <i>função fatorial</i> (digamos <i>fat: IN -> IN</i>).
- Geralmente no Ensino Médio essa função é apresentada de modo informal, a partir de exemplos:
- <i>fat(0) = 1</i>,
- <i>fat(1) = 1</i>,
- <i>fat(2) = 2</i> e
- generaliza-se afirmando que
- <i>fat(n) = n x (n-1) x (n-2) x ... x 2 x 1</i>.
- E o sentido das reticências é inferido.
- </p>
- <p>
- Mas pode-se apresentar uma definição foraml para <i>fatorial</i> dizendo-se que
- o fatorial de <i>0</i>, é <i>1</i> e que
- o fatorial de <i>n</i>, para <i>n > 0</i>, é
- o produtudo de <i>n</i> pelo fatorial de <i>n-1</i>, ou seja,
- <!-- <br/>f(n) = { 1, se n=0; n*f(n-1), se n>0 }</i>
- $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.$
- -->
- <center><img src="img/img_fatorial_def.png" title="f(n) = { 1, se n=0; n*f(n-1), se n>0 }" width="250"/>
- <!-- <table>
- <tr><td></td> <td> / 1, se n=0</td></tr>
- <tr><td> fat(n) = </td> <td>{</td></tr>
- <tr><td></td> <td> \ n x <b>fat(n-1)</b>, se n > 0.</td></tr></table> -->
- </center>
- </p>
- <p>
- Assim, como no <i>lado direito</i> da definição da função <i>fatorial</i> usa-se a própria função
- <i>fatorial</i>, essa é uma definição recursiva.
- Todas as funções recursivas tem essa característica, o nome da função aparecer tanto à esquerda,
- quanto à direita do símbolo de atribuição (<i>=</i>).
- </p>
- <p>
- De modo prático, sem nos preocuparmos ainda com a implementação e execução de um algoritmo,
- para computar, por exemplo,
- <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>.
- Para ver com mais detalhes como é realizada as chamadas recursivas na função fatorial,
- <a href="#" onclick="trocaPagina('introducao_recursividade_exemplos.html')" title="detalhes sobre a implementacao do faotorial recursivo">siga este apontador</a>.
- </p>
- <a name="implementacao">
- <p class="secao">Implementando recursiva para fatorial em <i>C</i> e em <i>Python</i></p>
- </a>
- <p>
- Geralmente as liguagens de programação permitem definições recursivas de funções.
- Comecemos examinando precisamente a função fatorial.
- Implementando-a de modo <b>iterativo</b> fazemos algo como <tt>fat = 1; for i de 2 até N : fat = fat * i;</tt>,
- ou seja, usamos uma variável contadora para enumerar os naturais entre 2 e N e interrompemos a repetição quanto
- <tt>i</tt> chegar a <tt>N</tt>.
- </p>
- <p>
- No caso da definição recursiva de <i>fatorial</i>, o processo de chamada recursiva deve ser interrompido quanto
- <tt>n</tt> tiver o valor <tt>0</tt>.
- 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>).
- Na tabela abaixo, apresentamos implementações recursivas para a função <i>fatorial</i>
- tanto na linguagem <b>C</b>, quanto em <b>Python</b>.
- </p>
- <center>
- <table class="tbCodeLinCol">
- <tr class="tbCodeLinColH"><th colspan="2">Função fatorial implementada recursivamente</th></tr>
- <tr><th>C </th> <th>Python</th></tr>
- <tr valign="top"><td><table class="tbCode">
- <tr><td><pre><incl1>#include</incl1> <stdio.h>
- <cyan>// Fatorial recursivo</cyan>
- <verm>int</verm> fatRec (<verm>int</verm> n) {
- if (n==0) return 1; <cyan>// final de recorrencia</cyan>
- return n * fatRec(n-1); <cyan>// senao devolve n x "o fatorial de n-1" (inducao)</cyan>
- }
- <cyan>// experimente invocar esta versao com msg para rastrear execucao</cyan>
- <verm>int</verm> fatRecDepuracao (<verm>int</verm> n) {
- <verm>int</verm> aux;
- if (n==0) { <verd>printf</verd>("fat(%d)\n", n); return 1; } <cyan>// final de recorrencia</cyan>
- aux = n * fatRecDepuracao(n-1); <cyan>// senao devolve n x "o fatorial de n-1" (inducao)</cyan>
- <verd>printf</verd>("fat(%d): devolve %d\n", n, aux);
- return aux;
- }
- <verm>int</verm> main (<verm>void</verm>) {
- <verm>int</verm> n;
- <verd>scanf</verd>("%d", &n);
- <verd>printf</verd>("O fatorial de %d e': %d\n", n, fatRec(n));
- return 1;
- }</pre></td></tr>
- </table></td>
- <td><table class="tbCode"><pre><cyan># Fatorial recursivo</cyan>
- <verm>def</verm> fatRec (n) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
- if (n==0) : return 1; <cyan># final de recorrencia</cyan>
- return n * fatRec(n-1); <cyan># senao devolve n x "o fatorial de n-1" (inducao)</cyan>
- <cyan># experimente invocar esta versao com msg para rastrear execucao</cyan>
- <verm>def</verm> fatRecDepuracao (n) :
- if (n==0) : <tt style="color:#0000df;">print</tt>("fat(%d)" % n); return 1; <cyan># final de recursao (final de "laco")</cyan>
- aux = n * fatRecDepuracao(n-1); <cyan># senao faca mais um "passo" (inducao)</cyan>
- <tt style="color:#0000df;">print</tt>("fat(%d): devolve %d\n", n, aux);
- return aux;
- <verm>def</verm> main () :
- n = int(input());
- <tt style="color:#0000df;">print</tt>("O fatorial de %d e': %d" % (n, fatRec(n)));
- main();
- </pre></td></tr>
- </table></td></tr>
- </table></center>
- </p>
- <a name="execucao">
- <p class="secao">Execução de funções recursivas</p>
- </a>
- <p>
- Vamos usar o exemplo do fatorial para ilustrar como é possível que o computador execute funções recursivas.
- O truque computacional é mais ou menos o seguinte:
- ao fazer a chamada <i>fat(n)</i>, em um contexto que denominaremos <i>n</i>,
- <ol>
- <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,
- desse modo registra-se em uma "pilha" (empilhar) este ponto de execução; e
- </li>
- <li> invoca-se novamente a função, dessa vez com <i>fat(n-1)</i> (contexto <i>n-1</i>);
- </li>
- <li> quando o computador tiver finalmente o valor para <i>fat(n-1)</i>, desempilha-se o contexto <i>n</i>
- (portanto, volta-se ao cômputo de <i>n x fat(n-1)</i>, mas agora <i>fat(n-1)</i> é conhecido),
- realiza-se a produto e devolve o resultado.
- </li>
- </ol>
- </p>
- <p>
- 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>,
- executa-se o comando <tt>4 * fatRec(3)</tt> e, quando o computador tiver conseguido computar <tt>fatRec(3)</tt>,
- esse valor (<i>6</i>) é substituido no contexto <i>4</i> (i.e., <tt>4 * 6</tt>) e devolve-se o resultado desse produto
- (<i>24</i>).
- </p>
- <p>
- Vamos detalhar um pouco mais esse processo de recorrência, mas agora usando <tt>fatRec(3)</tt>.
- Na primeir coluna indicamos a ordem de execução de cada instrução (<tt>Ord.</tt>), na segunda o contexto <tt>n</tt>
- <pre style="font-size:0.8em">Ord. n Imprimir (esquema de execução)
- 1 3 fatRec(3)
- 2 2 = 3 * fatRec(2) --> fatRec(2)
- 3 1 = 2 * fatRec(1) --> fatRec(1)
- 4 0 = 1 * fatRec(0) --> fatRec(0)
- 5 0 = 1 <cyan>// final recorrencia, volta onde foi chamado</cyan>
- 6 1 = 1 * 1 = 1 <cyan>// final recorrencia 'fatRec(1)', volta para quem chamou</cyan>
- 7 2 = 2 * 1 = 2 <cyan>//</tt> final recorrencia 'fatRec(2)', volta para quem chamou</cyan>
- 8 3 = 3 * 2 = 6 <cyan>// final recorrencia 'fatRec(3)' e dai imprime o valor 6</tt></pre>
- </p>
- <p>
- Note que na ordem de cada instrução, separamos o comando <tt>k * fatRec(k-1)</tt> em duas instruções,
- primeiro obter o valor de <tt>fatRec(k-1)</tt>, digamos <tt>FK</tt>, e depois a instrução <tt>k * FK</tt>.
- </p>
- <a name="pg1">
- <p class="secao">Outro exemplo de função recursiva: cômputo da progressão de razão 1</p>
- </a>
- <p>
- 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
- naturais até <i>n</i>.
- <center>
- <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>
- <table class="tbCodeLinCol">
- <tr class="tbCodeLinColH"><th colspan="2">A soma dos naturais até <i>n</i></th></tr>
- <tr><th>C </th> <th>Python</th></tr>
- <tr><td><table class="tbCode"><pre><incl1>#include</incl1> <stdio.h>
- <cyan>// P.A.</cyan>
- <verm>int</verm> somaRec (<verm>int</verm> n) {
- if (n==0) return 0; <cyan>// final de recorrencia</cyan>
- return n + somaRec(n-1); <cyan>// senao devolve n + soma ate n-1 (inducao)</cyan>
- }
- <verm>int</verm> main (<verm>void</verm>) {
- <verm>int</verm> n;
- <verd>scanf</verd>("%d", &n);
- <verd>printf</verd>("A soma dos naturais ate' %d e': %d\n", n, somaRec(n));
- return 1;
- }</pre></td></tr>
- </table></td>
- <td><table class="tbCode"><pre><cyan># P.A.</cyan>
- <verm>def</verm> somaRec (n) :
- if (n==0) : return 0; <cyan># final de recorrencia</cyan>
- return n + somaRec(n-1); <cyan># senao devolve n + soma ate n-1 (inducao)</cyan>
- <verm>def</verm> main () :
- n = int(input());
- <tt style="color:#0000df;">print</tt>("A soma dos naturais ate' %d e': %d" % n, somaRec(n));
- main();
- </pre></td></tr>
- </table></td></tr>
- </table></center>
- </p>
- <p>
- Note que <b>não</b> é necessário colocar a palavra reservada <tt>else</tt> após o <tt>if</tt>, pois
- a linha após o comando <tt>if</tt> só será executada se, e somente se,
- a condição da seleção resultar falso, ou seja, se o comando subordinado ao <tt>if</tt> NÃO for
- executado.
- Por que mesmo? (se não deduzir a razão, consulte a <a href="#notaA" title="examinar a resposta">nota A</a> ao final)
- </p>
- <p>
- Experimente copiar os códigos para a função fatorial e para a enumeração dos primeiros naturais,
- eventualmente coloque mais mensagens para depuração (e.g. imprimir <tt>Entrei na funcao com n=%d</tt>
- e <tt>Chamei recursivamente com n-1=%d</tt>) e certifique-se que entendeu bem recorrência.
- </p>
- <a name="binarios">
- <p class="secao">Como gerar ordenadamente todos os números binário de <i>k</i> dígitos</p>
- </a>
- <p>
- Um exemplo interessante para ilustrar o quanto alguns programas ficam mais simples se deduzidos na forma recursiva é desenhar um algoritmo
- para gerar todos os números binários com exatamente <i>k</i> <i>bits</i> (considerandos os "zeros à esquerda").
- </p>
- <p>
- <center><table><tr><td><pre>Decimal Binário | Decimal Binário
- 0 0000 | 8 1000
- 1 0001 | 9 1001
- 2 0010 | 10 1010
- 3 0011 | 11 1011
- 4 0100 | 12 1100
- 5 0101 | 13 1101
- 6 0110 | 14 1110
- 7 0111 | 15 1111</pre></td>
- <td>
- <img src="img/img_recursividade_arvore_binaria.png" title="arvore binaria para gerar palavras de 3 bits" width="250"/>
- <br/>
- <i>Fig. 5. Ilustração da sequência recursiva a ser seguida pelo algoritmo.</i>
- </tr></table>
- <i>Exemplo: todos os binários com até 4 dígitos (com seu correspondente decimal à esquerda)</i>
- </center>
- </p>
- <p>
- Antes de ler o texto explicando como resolver este problema, pense um pouco sobre ele. Primeiro, tente por alguns minutos
- esquematizar um algoritmo para resolver o problema de modo iterativo (<i>não recursivo</i>), depois tente resolvê-lo de modo recursivo.
- Se conseguir resolver o desafio, poderá pereceber o quanto a recorrência simplifica a resolução desse problema.
- </p>
- <p>
- Entretanto, se você está com dificuldades para resolver o problema,
- <a href="#" onclick="trocaPagina('introducao_recursividade_binarios.html" title="ver a solucao para a geracao de numeros binarios">siga este apontador</a>
- para ver uma sugestão de como estruturar o pensamento para resolver o problema de forma recursiva.
- </p>
- <p>
- Agora que você sabe como gerar todos os binários com até <i>k</i> dígitos, pense em generalizar a problema, ou seja,
- gerar todos os números, em qualquer base, com até <i>k</i> dígitos.
- Espero que perceba que essa generalização é bem simples para quem resolveu o caso com base 2 (binário).
- </p>
- <p>
- As duas seções seguintes são conceitualmente mais sofisticadas, portanto mais difíceis de ser compreendidas por
- 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.
- Desse modo, estude-as apenas se estiver muito confortável com o conceito de recorrência.
- </p>
- <a name="hanoi">
- <p class="secao">Problema das Torres de Hanói</p>
- </a>
- <p>
- Pode-se notar nos exemplos anteriores que um algoritmo recursivo (geralmente) é mais simples de ser codificado.
- Um exemplo que ilustra ainda melhor essa facilidade é implementar um algoritmo para simular (ou computar) os movimentos
- 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>.
- <p>
- <p>
- 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"
- (e.g., nunca um disco maior pode ficar sobre um de diâmetro menor).
- Assim, para mover os <i>n</i> pode-se supor que exista um algoritmo que consiga realizar a movimentação mínima
- 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
- para a haste auxiliar <i>B</i>.
- 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
- de moviemtos: apenas 1.
- 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
- <i>C</i>, resolvendo o problema.
- </p>
- <p>
- A ideia acima está representada nas figuras abaixo e dela percebe-se claramente um algoritmo recursivo para resolver o
- problema.
- <center>
- <img src="img/ihanoi1.png" title="n discos em A"/>
- <img src="img/ihanoi2.png" title="maior em A, n-1 em B"/>
- <img src="img/ihanoi3.png" title="n-1 em B, maior em C"/>
- <img src="img/ihanoi4.png" title="n discos em C"/>
- <br/>
- <i>Fig. 6. Ilustração da sequência de movimentação mínima para 3 discos.</i>
- </center>
- </p>
- </p>
- Assim, movimentar minimamente os discos de A para C pode ser esquematizado no seguinte algoritmo recursivo:
- <pre>moverHanoi(n, A, C, B) - mover n discos de A para C, usando a haste B
- se n==1, entao mover disco do topo da haste A para a haste C - final de recorrencia
- senao
- moverHanoi(n-1, A, B, C) - mover otimamente n-1 discos de A para C (libera o ultimo)
- mover disco do topo da haste A para a haste C
- moverHanoi(n-1, B, C, A) - mover otimamente n-1 discos de B para C</pre>
- </p>
- <a name="fibonacci">
- <p class="secao">Nem todo algoritmo recursivo é eficiente</p>
- </a>
- <p>
- Entretanto, a recursividade pode não ser eficiente! O melhor exemplo de ineficiência é tentar implementar um algoritmo recursivo
- 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>, ...
- 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
- <i>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></i>, para todo <i>n>2</i>.
- </p>
- <p>
- Uma implementação iterativa eficiente para gerar o <i>n</i>-ésimo termo da sequência de <i>Fibonacci</i> pode ser:
- <tt>F1=1; F2=1; for i de 3 até N : F = F1+F2; F1=F2; F2=F;</tt>
- </p>
- <p>
- Novamente a implementação recursiva tem um código mais "enxuto", porém exponencialmente ineficiente!
- Isso está ilustrado no código abaixo que implementa ambos e compara o tempo de execução tanto em <b>C</b> quanto em
- <b>Python</b>.
- <center>
- <table class="tbCodeLinCol">
- <tr class="tbCodeLinColH"><th colspan="2">A soma dos naturais até <i>n</i></th></tr>
- <tr><th>C </th> <th>Python</th></tr>
- <tr><td><table class="tbCode"><pre><incl1>#include</incl1> <stdio.h>
- <incl1>#include</incl1> <time.h> <cyan>// clock_t, clock()</cyan>
- <cyan>// Fibonacci iterado</cyan>
- <verm>int</verm> fib (n) { <cyan>// os finalizadores ';' sao opcionais em Python</cyan>
- <verm>int</verm> i, F1=1, F2=1, F;
- if (n<3) return 1;
- for (i=3; i<=n; i++) {
- F = F1+F2;
- F1 = F2;
- F2 = F;
- }
- return F;
- }
- <cyan>// Fibonacci recursivo</cyan>
- <verm>int</verm> fibRec (n) { <cyan>// os finalizadores ';' sao opcionais em Python</cyan>
- if (n==1 || n==2) return 1; <cyan>// final de recorrencia</cyan>
- return fibRec(n-1) + fibRec(n-2); <cyan>// senao devolve</cyan>
- }
- <verm>int</verm> main (<verm>void</verm>) {
- <verm>int</verm> n, fibA; clock_t tempo_inicial, tempo_final;
- <verd>scanf</verd>("%d", &n);
- tempo_inicial = clock(); <cyan>// "dispara o cronometro"...</cyan>
- fibA = fib(n);
- tempo_final = clock();
- <verd>printf</verd>("Iterativo: %3d - %3d em %f segundos\n",
- n, fibA, (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
- tempo_inicial = clock(); <cyan>// "dispara o cronometro"...</cyan>
- fibA = fibRec(n);
- tempo_final = clock();
- <verd>printf</verd>("Recursivo: %3d - %3d em %f segundos\n",
- n, fibA, (double)(tempo_final - tempo_inicial) / CLOCKS_PER_SEC);
- return 1;
- }</pre></td></tr>
- </table></td>
- <td><table class="tbCode"><pre><tt style="color:#15007f;">import</tt> time; # para tempo 'time.time()'
- <cyan># Fibonacci iterado</cyan>
- <verm>def</verm> fib (n) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
- F1=1; F2=1;
- if (n<3) : return 1;
- for i in range(3, n+1) :
- F = F1+F2;
- F1 = F2;
- F2 = F;
- return F;
- <cyan># Fibonacci recursivo</cyan>
- <verm>def</verm> fibRec (n) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
- if (n==1 or n==2) : return 1; <cyan># final de recorrencia</cyan>
- return fibRec(n-1) + fibRec(n-2); <cyan># senao devolve</cyan>
- <verm>def</verm> main () :
- n = int(input());
- tempo_inicial = time.time(); <cyan># "dispara o cronometro"...</cyan>
- fibA = fib(n);
- tempo_final = time.time();
- <tt style="color:#0000df;">print</tt>("Iterativo: %3i - %3i em %f segundos" %
- (n, fibA, (tempo_final - tempo_inicial)));
- tempo_inicial = time.time(); <cyan># "dispara o cronometro"...</cyan>
- fibA = fibRec(n);
- tempo_final = time.time();
- <tt style="color:#0000df;">print</tt>("Recursivo: %3i - %3i em %f segundos" %
- (n, fibA, (tempo_final - tempo_inicial)));
- main();</pre></td></tr>
- </table></td></tr>
- </table></center>
- </p>
- <p>
- Se desejar tentar resolver o <i title="jogo proposto por Edouard Lucas em 1883">problema das Torres de Hanói</i>
- <a href="http://www.matematica.br/ihanoi" target="_blank"
- title="seguir para nossa implementação para a Torres de Hanói em JavaScript">seguir este apontador</a>.
- </p>
- <p class="porque">
- <a name="notaA">
- <!-- 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. -->
- <b>A</b>. Por que o código da tabela 1
- (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>)
- não precisa de <tt>else</tt>?
- <br/>
- Note que traduzindo os comandos da função <tt>somaRec</tt> para o <i>Portugol</i>, ele seria:
- <br/>
- <tt>
- se (n==0) devolva 0; <cyan>//# final de recorrencia</cyan><br/>
- devolva n + somaRec(n-1);
- </tt>
- <br/>
- Assim, se a condição <tt>n==0</tt> resultar <i>verdadeiro</i>, então o comando <tt>devolva 0</tt>
- é executado, voltando para quem invocou <tt>somaRec(0)</tt> (que pode ser <tt>somaRec(1)</tt> ou a
- função <tt>main</tt>, se tinha sido digitado <i>0</i> para <tt>n</tt>).
- Desse modo, a única possibilidade do comando <tt>devolva n + somaRec(n-1)</tt> ser executado é
- <tt>n==0</tt> resultar <i>falso</i>
- e portanto a reservada <tt>else</tt> é desnecessária.
- </a>
- </p>
- <p class="autoria">
- <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/>
- <a href="http://www.ime.usp.br/~leo" target="_blank" title="seguir para a página do LInE">http://line.ime.usp.br</a>
- </p>
- <p class="rodape">
- <b>Alterações</b>:<br/>
- 2020/08/20: acertos no formato<br/>
- 2020/08/15: novo formato, pequenas revisões<br/>
- 2020/08/13: novo formato, pequenas revisões<br/>
- 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/>
- 2019/06/03: extensáo da seção "Exemplo de função ou definição recursiva";<br/>
- 2018/06/18: nova seção "como gerar binários";<br/>
- 2018/06/03: acrescentado versoes 'fatRecDepuracao(...)';<br/>
- 2018/06/03: versao inicial
- </p>
- </div>
|