intr_prog/introducao_recursividade_exemplos.html

<!--
 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> &nbsp; | &nbsp;
  <a href="#depuracao" title="Um exemplo mostrando o comportamento da funcao recursiva">Depurando fatorial </a> &nbsp; | &nbsp;
  <a href="#busca" title="Outro exemplo de recursividade em C e em Python: busca binaria">Busca Binária</a> &nbsp; | &nbsp;
  <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&gt;0 }" width="250"/>
  <!--
  <table>
   <tr><td><i>f:IN->IN, </td><td> sendo</td></tr>
   <tr><td></td>             <td>&nbsp;&nbsp;/ 1, se n=0</td></tr>
   <tr><td> f(n) = </td>     <td>{</td></tr>
   <tr><td></td>             <td>&nbsp;&nbsp;\ n x <b>f(n-1)</b>, se n &gt; 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> &lt;stdio.h&gt;
  <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> &lt;stdio.h&gt;
  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 =&gt; 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>&nbsp;&nbsp;&nbsp;&nbsp;<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.   &nbsp;&nbsp; <i>se (ini > fim), então </i> devolva que não existe mais intervalo onde procurar<br/>
  3.   &nbsp;&nbsp; <i>meio = (ini + fim) / 2;</i> <cyan>// usando a divisão inteira</tt><br/>
  4.   &nbsp;&nbsp; <i>se (vet[meio] == x), então</i> devolva que encontramos na posição <i>meio</i><br/>
  5.   &nbsp;&nbsp; <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.   &nbsp;&nbsp; <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] &lt; 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] &lt; 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 &gt; meio) {
    <verd>printf</verd>("%*.s", 2*(N-k), brancos);
    <verd>printf</verd>("Nao ha mais onde buscar: %d &gt; %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] &lt; 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] &lt; 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>
  &nbsp; (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>