<!--
Introdução à Programação - 2017 - Prof. Leoônidas de Oliveira Brandão
Introdução aos algoritmos recorrentes/recursivos: alguns exemplos
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> <!-- para referencias 'a documentos internos -->
<div class="pagina">
<!--
fatorial -
depuracao -
busca -
depuracaobb -
-->
<center><p>[
<a href="#fatorial" title="Fatorial recursivo">Fatorial</a> |
<a href="#depuracao" title="Um exemplo mostrando o comportamento da funcao recursiva">Depurando fatorial </a> |
<a href="#busca" title="Outro exemplo de recursividade em C e em Python: busca binaria">Busca Binária</a> |
<a href="#depuracaobb" title="Simulando e depurando a busca binária">Depurando a Busca Binária</a>
]</p>
</center>
<p class="secao">Introdução aos algoritmos recorrentes/recursivos: alguns exemplos</p>
<p>
Nesta seção examinaremos alguns exemplos de <b>algoritmos recorrentes</b> (ou <b>recursivos</b>).
A apresentação do conceito pode ser encontrada
<a href="#" onclick="trocaPagina('introducao_recursividade.html')" title="examinar a introducao `a recursao">nesta página</a>.
</p>
<a name="fatorial">
<p class="secao">Fatorial implementado de modo recursivo</p>
</a>
<p>
A função matemática <i>fatorial</i> descreve o númeto de permutações distintas de um conjunto finito.
Sua definição é intrinsecamente recursiva:
<!-- <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><i>f:IN->IN, </td><td> sendo</td></tr>
<tr><td></td> <td> / 1, se n=0</td></tr>
<tr><td> f(n) = </td> <td>{</td></tr>
<tr><td></td> <td> \ n x <b>f(n-1)</b>, se n > 0.</td></tr></table>-->
</center>
</p>
<p>
Em termos práticos a função fatorial pode ser implementada como indicado abaixo, utilizando
<i>recorrência de cauda</i>, ou seja, a chamada recursiva corresponde às últimas instruções da função.
<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>
}
<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>
<verm>def</verm> main () :
n = int(input());
<verd>print</verd>("O fatorial de %d e': %d" % (n, fatRec(n)));
main();
</pre></td></tr>
</table></td></tr>
</table></center>
</p>
<p>
A execução de uma função recursiva é realizada empilhando-se o contexto de execução,
de modo que no momento que a chamada recursiva termina, retorna-se ao contexto empilhado e,
ao finalizado a chamada "inicial", o contexto é removido da pilha (<i>desempilhado</i>).
Em detalhes, vejamos uma simulação da função <i>fatRec</i> acima apresentada para <i>n=3</i>.
<table><tr><td>
<pre style="font-size:0.8em;">Ord. n Imprimir (esquema de execução)
1 3 fatRec(3)
2 2 fatRec(3) = 3*fatRec(2) -> fatRec(2)
3 1 ^ ^ 2*fatRec(1) -> fatRec(1)
4 0 | | ^ 1*fatRec(0) --> fatRec(0)
| | | ^
| | | |
5 0 | | | +-- 1 .. final desse contexto n=0
6 1 | | +--------- 1 = 1*1 .... final do contexto 'fatRec(1)'
7 2 | +--------- 2 = 2*1 .................. final do contexto 'fatRec(2)'
8 3 +------ 6 = 3*2 ................................... final do contexto 'fatRec(3)'</pre>
</td>
<td><img src="img/img_fatorial_fat3.png" title="representacao pilha execucao fatRec(3)" width="100%"></tr></table>
Na primeira coluna, sob rótulo <i>Ord.</i>, está o tempo de execução, sendo os números a ordem de execução dos
comandos. Na segunda coluna está o valor do <i>n</i> no contexto da chamada sendo simulada.
</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="depuracao">
<p class="secao">Um exemplo mostrando o comportamento da função recursiva</p>
</a>
<p>
Podemos alterar o código da função recursiva <i>fatRec</i> acima para percebermos mais claramente
os contextos de execução e os <b>níveis de recorrência</b>.
Por <i>nível de recorrência</i> deve-se entender o número de vezes que a recorrência é invocada, por exemplo,
para <i>n=0</i>, teremos nível de recorrência <i>0</i>, para <i>n=1</i>, nível <i>1</i> e assim por diante.
</p>
<p>
Abaixo os códigos em <i>C</i> e em <i>Python</i>, imprimindo a chegada ao contexto <i>n</i>, deslocando-se
horizontalmente a impressão de acordo com o nível da recorrência ("indentação").
Por essa razão, precisaremos passar um parâmetro adicional, que sempre terá o valor inicial do <i>n</i>.
</p>
<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>
char brancos[] = " ";
<verm>int</verm> fatRec (int N, <verm>int</verm> k) {
<verm>int</verm> aux;
<verd>printf</verd>("%*.s", 2*(N-k), brancos); <cyan>// truque: nivel rec. maior => deslocar mais</cyan>
<verd>printf</verd>("Entrei em fat(%d)\n", k);
if (k==0) aux = 1; <cyan>// final de recorrencia</cyan>
else aux = k * fatRec(N, k-1); <cyan>// senao devolve k x "o fatorial de k-1"</cyan><!-- (inducao) -->
<verd>printf</verd>("%*.s", 2*(N-k), brancos);
<verd>printf</verd>("Saindo de fat(%d): devolve %d\n", k, aux);
return aux;
}
<verm>int</verm> main (<verm>void</verm>) {
<verm>int</verm> n, fat;
<verd>scanf</verd>("%d", &n);
<verd>printf</verd>("Antes de iniciar chamada a fat(%d)\n", n);
fat = fatRec(n, n);
<verd>printf</verd>("Apos chamada a fat(%d)\n", n);
return 1;
}</pre></td></tr>
</table></td>
<td><table class="tbCode"><pre><tt style="color:#15007f;">from __future__ import print_function;</tt> <cyan># para Python 2</cyan>
<cyan># Fatorial recursivo</cyan>
<verm>def</verm> fatRec (N, k) : <cyan># os finalizadores ';' sao opcionais em Python</cyan>
<verd>print</verd>((N-k) * " ", end=""); <cyan># truque: nivel rec. maior => deslocar mais</cyan>
<verd>print</verd>("Entrei em fat(%d)" % k);
if (k==0) : aux = 1; <cyan># final de recorrencia</cyan>
else : aux = k * fatRec(n, k-1); <cyan># senao devolve k x "o fatorial de k-1"</cyan><!-- (inducao) -->
<verd>print</verd>((N-k) * " ", end=""); <cyan># truque: nivel rec. maior => deslocar mais</cyan>
<verd>print</verd>("Saindo de fat(%d): devolve %d" % (k, aux));
return aux;
<verm>def</verm> main () :
n = int(input());
<verd>print</verd>("Antes de iniciar chamada a fat(%d)" % n);
fatRec(n, n);
<verd>print</verd>("Apos chamada a fat(%d)" % n);
main();
</pre></td></tr>
</table></td></tr>
</table></center>
</p>
<p>
Assim, se rodarmos qualquer uma das versões para <i>n=3</i>, teremos a seguinte impressão:
<table><tr><td>
<pre style="font-size:0.9em;color:#0000aa;">Antes de iniciar chamada a fat(3)
Entrei em fat(3)
Entrei em fat(2)
Entrei em fat(1)
Entrei em fat(0)
Saindo de fat(0): devolve 1
Saindo de fat(1): devolve 1
Saindo de fat(2): devolve 2
Saindo de fat(3): devolve 6
Apos chamada a fat(3)</pre></font></td>
<td> <img src="img/img_fatorial_fat3.png" title="representacao pilha execucao fatRec(3)" width="330px"></tr></table>
</p>
<a name="busca">
<p class="secao">Outro exemplo de recursividade em <i>C</i> e em <i>Python</i>: busca binária</p>
</a>
<p>
Se analisarmos a frequência de uso dos variados tipos de algoritmo, provavelmente o campeão de uso
é a <i>busca</i> de elemento em vetor/lista/conjunto.
Para que essa busca seja eficiente, geralmente mantemos os dados ordem (e.g., crescente), assim
podemos empregar um algoritmo de busca muito rápido, a <i>busca binária</i>.
</p>
<p>
A <b>busca binária</b> é feita sobre listas ordenadas, adotando o seguinte esquema:<br/>
1. <i>busca(vet, x, ini, fim)</i> <cyan>// busca o elemento <i>x</i> em <i>vet</i> entre as posições <i>ini</i> e <i>fim</i>;</tt><br/>
2. <i>se (ini > fim), então </i> devolva que não existe mais intervalo onde procurar<br/>
3. <i>meio = (ini + fim) / 2;</i> <cyan>// usando a divisão inteira</tt><br/>
4. <i>se (vet[meio] == x), então</i> devolva que encontramos na posição <i>meio</i><br/>
5. <i>se (vet[meio] < x), então</i> <i>x</i> não pode estar na primeira metade, busque entre <i>meio+1</i> e <i>fim</i><br/>
6. <i>se (vet[meio] > x), então</i> <i>x</i> não pode estar na segunda metade, busque entre <i>ini</i> e <i>meio-1</i></p>
<p>
Note que na descrição acima, o algoritmo é naturalmente recursivo, então faremos essa implementação em
<i>C</i> e em <i>Python</i>.
</p>
<p>
<center>
<table class="tbCodeLinCol">
<tr class="tbCodeLinColH"><th colspan="2">Busca binária implementada recursivamente</th></tr>
<tr><th>C </th> <th>Python</th></tr>
<tr valign="top"><td><table class="tbCode">
<tr><td><pre><verm>int</verm> busca (<verm>int</verm> vet[], <verm>int</verm> x, <verm>int</verm> ini, <verm>int</verm> fim) { <cyan>// busca x entre vet[ini] e vet[fim]</cyan>
<verm>int</verm> meio;
if (ini>meio) return -1; <cyan>// nao tem mais onde procurar!</cyan>
meio = (ini+fim) / 2; <cyan>// pegar indice do elemento do meio</cyan>
if (vet[meio]==x)
return meio; <cyan>// encontrei na posicao meio</cyan>
else
if (vet[meio] < x) <cyan>// vet[ini]...vet[meio] NAO contem x</cyan>
<cyan>// entao busque (recursivamente) entre vet[meio+1] e vet[fim]</cyan>
return busca(vet, x, meio+1, fim);
else <cyan>// vet[meio]...vet[fim] NAO contem x</cyan>
<cyan>// entao busque (recursivamente) entre vet[ini] e vet[meio-1]</cyan>
return busca(vet, x, ini, meio-1);
} <cyan>// nunca executaria esta linha - por que?</tt></pre></td></tr>
</table></td>
<td><table class="tbCode"><pre><verm>def</verm> busca (vet, x, ini, fim) : <cyan># busca x entre vet[ini] e vet[fim]</cyan>
if (ini>meio) : return -1; <cyan># nao tem mais onde procurar!</cyan>
meio = (ini+fim) / 2; <cyan># pegar indice do elemento do meio</cyan>
if (vet[meio]==x) :
return meio; <cyan># encontrei na posicao meio</cyan>
elif (vet[meio] < x) : <cyan># vet[ini]...vet[meio] NAO contem x</cyan>
<cyan># entao busque (recursivamente) entre vet[meio+1] e vet[fim]</cyan>
return busca(vet, x, meio+1, fim);
else : <cyan># vet[meio]...vet[fim] NAO contem x</cyan>
<cyan># entao busque (recursivamente) entre vet[ini] e vet[meio-1]</cyan>
return busca(vet, x, ini, meio-1);
<cyan># nunca executaria esta linha - por que?</tt></pre></td></tr>
</table></td></tr>
</table></center>
</p>
<a name="depuracaobb">
<p class="secao">Simulando e depurando a busca binária</p>
</a>
<p>
Da mesma forma que inserimos várias linhas de impressão para ajudar a entender as recorrência na
função fatorial, inclusive usando um truque para visualizar o nível da recorrência,
faremos o mesmo com o algoritmo de busca binária.
</p>
<p>
<center>
<table class="tbCodeLinCol">
<tr class="tbCodeLinColH"><th colspan="2">Busca binária recursiva com mensagens para visualizar nível de recorrência</th></tr>
<tr><th>C </th> <th>Python</th></tr>
<tr valign="top"><td><table class="tbCode">
<tr><td><pre><cyan>// busca x entre vet[ini] e vet[fim]</cyan>
<verm>int</verm> busca (<verm>int</verm> vet[], <verm>int</verm> x, <verm>int</verm> ini, <verm>int</verm> fim, <verm>int</verm> N, <verm>int</verm> k) {
<verm>int</verm> meio = (ini+fim) / 2; <cyan>// pegar indice do elemento do meio</cyan>
<verd>printf</verd>("%*.s", 2*(N-k), brancos); <cyan>// para fazer indentacao</cyan>
<verd>printf</verd>("Entrei em busca(%d,%d): meio = %d\n", ini, fim, meio);
if (ini > meio) {
<verd>printf</verd>("%*.s", 2*(N-k), brancos);
<verd>printf</verd>("Nao ha mais onde buscar: %d > %d)\n", ini,fim);
return -1; <cyan>// nao tem mais onde procurar!</cyan>
}
if (vet[meio]==x) {
<verd>printf</verd>("%*.s", 2*(N-k), brancos);
<verd>printf</verd>("Achei %d na posicao %d!\n", x, meio);
return meio; <cyan>// encontrei na posicao meio</cyan>
}
else
if (vet[meio] < x) { <cyan>// vet[ini]...vet[meio] NAO contem x</cyan>
<verd>printf</verd>("%*.s", 2*(N-k), brancos);
<verd>printf</verd>("Busque na segunda metade: %d e %d\n", meio + 1, fim);
<cyan>// entao busque (recursivamente) entre vet[meio+1] e vet[fim]</cyan>
return busca(vet, x, meio+1, fim, N, k-1);
}
<verd>printf</verd>("%*.s", 2*(N-k), brancos);
<verd>printf</verd>("Busque na primeira metade: %d e %d\n", ini, meio - 1);
<cyan>// entao busque (recursivamente) entre vet[ini] e vet[meio-1]</cyan>
return busca(vet, x, ini, meio-1, N, k-1);
}
<verm>int</verm> main (<verm>void</verm>) {
<verm>int</verm> vet[] = { -1, 0, 3, 3, 5, 6, 7, 8, 9 };
<verm>int</verm> n = 9, resp;
<cyan>//int x = 7; // buscar 7</cyan>
<verm>int</verm> x = 2; <cyan>// buscar 2</cyan>
<verd>printf</verd>("Antes de iniciar chamada a busca(%d)\n", x);
resp = busca(vet, x, 0, n, n, n);
<verd>printf</verd>("Apos chamada a busca(%d)\n", x);
if (resp>-1) <verd>printf</verd>("Encontrei em %d: de fato %d = %d\n", resp, x, vet[resp]);
else <verd>printf</verd>("NAO encontrei %d\n", x);
return 0;
}</pre></td></tr>
</table></td>
<td><table class="tbCode"><pre><cyan># busca x entre vet[ini] e vet[fim]</cyan>
<verm>def</verm> busca (vet, x, ini, fim, N, k) :
<tt style="color:#fa4429;">global</tt> conta;
conta += 1;
if (conta>10) : return -1;
meio = (ini+fim) / 2; <cyan># pegar indice do elemento do meio</cyan>
<verd>print</verd>((N-k) * " ", end=""); <cyan># truque: nivel rec. maior => deslocar mais</cyan>
<verd>print</verd>("Entrei em busca(%d,%d): meio = %d" % (ini,fim, meio));
if (ini>meio) :
<verd>print</verd>((N-k) * " ", end=""); <cyan># truque: nivel rec. maior => deslocar mais</cyan>
<verd>print</verd>("Nao ha mais onde buscar: %d > %d)" % (ini,fim));
return -1; <cyan># nao tem mais onde procurar!</cyan>
if (vet[meio]==x) :
<verd>print</verd>((N-k) * " ", end="");
<verd>print</verd>("Achei %d na posicao %d!" % (x,meio));
return meio;
elif (vet[meio] < x) : <cyan># vet[ini]...vet[meio] NAO contem x</cyan>
<verd>print</verd>((N-k) * " ", end="");
<verd>print</verd>("Busque na segunda metade: %d e %d" % (meio + 1, fim));
<cyan># entao busque (recursivamente) entre vet[meio+1] e vet[fim]</cyan>
return busca(vet, x, meio+1, fim, N, k-1);
else : <cyan># vet[meio]...vet[fim] NAO contem x</cyan>
<verd>print</verd>((N-k) * " ", end="");
<verd>print</verd>("Busque na primeira metade: %d e %d" % (ini, meio - 1));
<cyan># entao busque (recursivamente) entre vet[ini] e vet[meio-1]</cyan>
return busca(vet, x, ini, meio-1, N, k-1);
<verm>def</verm> main () :
vet = [ -1, 0, 3, 3, 5, 6, 7, 8, 9 ];
n = len(vet);
#x = 7; <cyan># buscar 7</cyan>
x = 2; <cyan># buscar 2</cyan>
<verd>print</verd>("Antes de iniciar chamada a busca(%d)" % x);
resp = busca(vet, x, 0, n, n, n);
<verd>print</verd>("Apos chamada a busca(%d)" % x);
if (resp>-1) : <verd>print</verd>("Encontrei em %d: de fato %d = %d" % (resp, x, vet[resp]));
else : <verd>print</verd>("NAO encontrei %d" % x);
main();</pre></td></tr>
</table></td></tr>
</table></center>
</p>
<p>
Procure criar uma função recursiva, eventualmente com mais de uma chamada como é o caso da
função de busca binária acima, com as mensagens e usando o truque para fazer indentação.
Então procure simular manualmente sua função, depois rode sua implementação e veja se
o resultado foi o esperado.
Cuidado com recorrência infinita (que equivale a laça infinito), por exemplo, utilize
uma variável global <tt>conta=0</tt> e dentro de sua função, use como primeira linha
algo como
<tt>conta += 1; if (conta>20) return -1;</tt>
(no <i>Python</i> lembre-se de declarar como global com a linha: <tt>global conta</tt>).
</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/15: novo formato, pequenas revisões<br/>
2020/08/13: novo formato, pequenas revisões<br/>
2020/06/18: nova imagem "img/img_fatorial_def.png" e "img/img_fatorial_fat3.png";<br/>
2019/06/03: extensáo da seção "Exemplo de função ou definição recursiva";<br/>
2018/06/15: primeira versão.
</p>
</div>