<!--
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>