ESTRUTURAS DE DADOS - ISPRA

INSTITUTO SUPERIOR PRIVADO DE ANGOLA
ESTRTUTURAS DE DADOS

INFORMÁTICA -3º ANO
PROFESSOR: Samuel Kakumba N’gunga

RECURSÃO

A recursão é uma das práticas mais vulgares na programação e um mecanismo poderoso na resolução de problemas.

DEFINIÇÃO
A recursão consiste na resolução de um problema utilizando parte do problema em causa como solução.
Uma solução recorrente subdivide-se em duas partes:
1. Caso Base -é a mais elementar solução para aqual se tem uma solução imediata.
2. Caso Indutivo ou Regra -O caso indutivo ou regra é a generalização da solução.

Na programação, deparamo-nos com o fenómeno de recursão quando um procedimento ou função faz chamada a si mesmo.

EXEMPLOS
_______________________________________________________________________________________________________________
1. Considere o caso para o cálculo do factorial de um número N. ( n!).
SOLUÇÃO
Passo 1. Identificar o caso base: Para n = 0 = = > n!=0
Passo 2. Caso Indutivo: Para n>0 ==> n!= n x (n-1)!

Eis a implementação da função factorial em Pascal.

Function factorial (n: Integer): Integer;
begin
if n =0 then
factorial := 1
else
factorial :=n * factorial (n -1)
End;
É interessante ver o fluxo de execução desta função. Para tal faça um clique neste link. Fluxo de execunção- Ilustração

________________________________________________________________________________________________________________

2. Escreva um procedimento para escrever a sequência dos primeiros n números inteiros 0, 1, 2, 3, ... n.
SOLUÇÃO
Passo 1. Identificar o caso base: Para n < 0 ==> Terminar
Passo 2. Caso Indutivo: Para n>=0 ==> write(n) e recursivamente escrever(n-1)

procedure sequencia(n: Integer): Integer;
begin
if n >=0 then
     begin
             sequencia(n-1);
             write(n);
       end
End;

____________________________________________________________________________________________________________________
3. Escreva uma função para determinar a soma dos primeiros n termos de uma sequencia de numeros naturais. ( Sn=1 + 2 + 3 + ... + n)
SOLUÇÃO
Passo 1. Indentificar o caso Base: Para n =1 ==>S1=1;
Passo 2. Caso Indutivo : Para n >1 ==> Sn = n + S(n -1) Indutivo

function soma(n: integer):integer;
begin
      if n = 1 then
         soma :=1
     else
          soma := n + soma (n-1)
end;

_____________________________________________________________________________________________________________________

EXERCÍCIOS

1. determinar o Output do seguinte procedimento.
procedure ida_volta(n: integer);
begin
    if n > 0 then
       begin
             write(n);
             ida_volta(n-1);
             write(n);
       end
end;

2. A potência de um número n ao expoente K ( n^{K _),}pode ser determinada da seguinte forma:
caso 1: n⁰= 1; para K=0

caso 2: n^K= n * n^{(K -1)}; para K>0;
Com base nos casos 1 e 2 escreva a função recursiva, potencia (base:real; expoente: integer): real; em Pascal.

3. Dado o procedimento
   procedure b(n: integer);
   begin
       if n > 0 then
             begin
                  b( n div 2);
                  write(n mod 2);
             end
   end;

a) Determinar o Output deste procedimento para n = 9, n=11, n=23.

b) Com base nos resultados da alínea a), atribua um nome mais significativo a este procedimento.
_____________________________________________________________________________________________________________________==

=Fim=

Hosted by www.Geocities.ws