




                               CAPTULO 11       
            
                              RECURSIVIDADE  
            
            
            11.1. A DECLARAO FORWARD           
            
                 Todos  os   exemplos  de   declaraes  de  funes  ou
            procedimentos que  vimos at  agora, definiam  a  funo  ou
            procedimento logo  aps o  seu cabealho.  possvel se usar
            uma  funo   ou  procedimento   antes  da   sua   definio
            propriamente dita. Para isso ser possvel:
            
            (1)  Antes  de  ser  usada  pela  primeira  vez,  escreva  o
            cabealho da funo (ou do procedimento);
            
            (2) Logo aps o cabealho, avise ao compilador do Pascal que
            vai deixar  para depois  a definio  da funo,  escrevendo
            logo  aps   o  cabealho   a  palavra   reservada   FORWARD
            (= adiante, na frente);
            
            (3) Se quiser, defina outros objetos do programa ou use logo
            a funo ou procedimento declarado como FORWARD;
            
            (4)  Antes  do  programa  principal,  declare  a  funo  ou
            procedimento que  estava  sendo  adiada.  Para  fazer  isso,
            escreva  novamente   o  cabealho   e  defina  a  funo  ou
            procedimento da  maneira habitual.  Ao escrever  o cabealho
            nesta segunda  vez, os  parmetros e  tipos  so  opcionais:
            pode-se escrever  s a  palavra chave  FUNCTION ou PROCEDURE
            seguida apenas  do nome  da funo ou do procedimento, mesmo
            que  j   tenham  sido  declarados  parmetros  na  primeira
            declarao do cabealho.
            
            Exemplo: Abaixo,  a definio  da funo  f    adiada  para
            depois da  definio da  funo g, que usa a funo f na sua
            definio.
            
            FUNCTION f(x: real): real; FORWARD;
            
            ...     ...
            
            (* Definio de outros objetos (variveis, tipos,
               funes ...) do programa *)
            
            ...     ...
            
            FUNCTION g(x, y: real): real;
            
            BEGIN
              if (x > 0) and (y > 0) then
                g := f(x + y)        (* g usa a funo f *)
              else                         (* na sua definicao *)
                g := f(-x) + f(-y)

                                       - 171 -





            END;
            
            FUNCTION f(x: real): real;
            (* -------------------
                        |
                        +----->  Poderia ser simplesmente FUNCTION f; *)
            
            BEGIN
              f := Sin(1/(1 + Sqr(1 - Cos(x))))
            END;
            
            11.2. FUNES E PROCEDIMENTOS RECURSIVOS   
            
                 Uma funo  ou procedimento  podem usar  a si mesmos na
            sua definio.  Esta ferramenta  de  programao    chamada
            recursividade.            recursividade 
            
            Exemplo: O  exemplo mais  comum   o da  funo fatorial.  O
            fatorial de N pode ser definido como sendo 1, se N for menor
            do que  2, e  igual a N vezes o fatorial de N - 1 nos demais
            casos:
            
                      FUNCTION Fat(N: byte): longint;
            
                      (* Calcula recursivamente o fatorial de N *)
            
                      BEGIN
                        if (N < 2) then
                          Fat := 1
                        else
                          Fat := N*Fat(N - 1)
                      END;
            
            Exemplo: Outro exemplo de funo definida recursivamente  a
            funo f a seguir. Nesta funo, f(20)  calculado em termos
            de f(10) que  igual a f(0) = -3.
            
                      FUNCTION f(x: longint): longint;
            
                      BEGIN
                        case x of
                          0..5 : f := -3;
                          6..9 : f := 3;
                        else
                          if (x > 9) then
                            f := f(x - 10)
                          else
                            f := f(x + 10)
                        end
                      END;
            
            Exemplo: Usando-se a declarao FORWARD podemos definir duas
            funes, cada uma usando a outra na sua definio:
            

                                       - 172 -





                      FUNCTION h(x: real): real; FORWARD;
            
                      FUNCTION g(x: real): real;
            
                      BEGIN
                        if x < 0 then
                          g := x
                        else
                          g := h(x + 1)   (* g usa h na sua definio *)
                      END;
            
                      FUNCTION h;
            
                      BEGIN
                        if x > 0 then
                          h := Sin(x)
                        else
                          h := g(x - 1)   (* h usa g na sua definio *)
                      END;
            
            Exemplo: Neste  exemplo, elaboramos  uma funo determinante
            que usa o desenvolvimento de Laplace pela 1a linha da matriz
            M = (aij)nxn :
            
            det(M) = a11*det(M11) - a12*det(M12) +... + (-1)1+n*det(M1n)
            
            onde M1k   a  matriz quadrada  de ordem  n - 1 que se obtm
            retirando-se a primeira linha e k-sima coluna de M.
                 Escolhemos o  desenvolvimento de  Laplace apenas porque
            ele   um caso  tpico de  recursividade: o  determinante de
            ordem n  se escreve  como um  somatrio de  determinantes de
            ordens n  - 1.  Uma funo  incomparavelmente mais  rpida e
            mais  eficiente   poderia  ter  sido  construda  usando  um
            escalonamento  da   matriz,  observando-se   a  paridade  da
            quantidade de  linhas trocadas  e o produto dos elementos da
            diagonal principal da matriz escalonada.
                 Usamos o tipo MATRIZ definido no captulo 8.
            
            
            FUNCTION Det(mat: matriz): real;
            
            (* Calcula o determinante da matriz MAT de ordem n x n,
               2 <= n <= 10 *)
            
            VAR
              i, j, k: byte;
              aux: matriz;
              soma: real;
            
            BEGIN
              if (mat.m <> mat.n) or (mat.m <= 1) then Halt;
            
              if (mat.m = 2) then (* Caso em que a ordem de MAT for 2 *)
              begin

                                       - 173 -





                Det := mat.a[1,1]*mat.a[2,2] - mat.a[1,2]*mat.a[2,1];
                Exit
              end;
            
              aux.m := mat.m - 1; aux.n := mat.n - 1;
              soma := 0;
            
              for k := 1 to mat.m do
              begin
            
             (* Para cada valor de  k, AUX  a matriz formada pela
                retirada da primeira linha e k-sima coluna de MAT *)
                for i := 1 to aux.m do
                  for j := 1 to aux.n do
                    if (j < k) then
                      aux.a[i, j] := mat.a[i + 1, j]
                    else
                      aux.a[i, j] := mat.a[i + 1, j + 1];
            
                if Odd(k) then
                  soma := soma + mat.a[1, k]*Det(aux)
                else
                  soma := soma - mat.a[1, k]*Det(aux)
              end; (* fim do FOR k... *)
            
              Det := soma;
            END;
            
                 A recursividade normalmente gasta mais memria e  mais
            lenta  do   que  um   algoritmo  equivalente   que  no  use
            recursividade. No  entanto, apreciamos  a beleza terica dos
            algoritmos recursivos,  que nem  sempre so  simples  de  se
            descrever de forma no-recursiva.
            
            Exemplo:  Podemos   ter  tambm  procedimentos  "forward"  e
            mutuamente recursivos,  como   o caso de "Flip" e "Flop" do
            programa a  seguir (OBS.: "flip-flop"  o tipo dos circuitos
            eltricos que formam a memria de um computador).
            
            PROGRAM Flip_Flop;
            
            PROCEDURE Flip(n: integer); FORWARD;
            
            (* ------------------------------------------------------ *)
            
            PROCEDURE Flop(n: integer);
            
            BEGIN
              Writeln('Flop');
              if n > 0 then Flip(n - 1); (* FLOP chama FLIP *)
            END;
            
            (* ------------------------------------------------------ *)
            

                                       - 174 -





            PROCEDURE Flip;
            
            BEGIN
              Writeln('Flip');
              if n > 0 then Flop(n - 1); (* FLIP chama FLOP *)
            END;
            
            (* ------------------------------------------------------ *)
            
            VAR
              x: integer;
            
            BEGIN
              Write('Forneca um numero inteiro positivo: '); Readln(x);
              Flip(x);
            END.
            
            Exemplo: No  ltimo exemplo  deste captulo,  apresentamos o
            algoritmo de classificao mais eficiente: o "quick sort" ou
            "classificao rpida".  Nele a  recursividade   usada para
            classificar os  elementos de um vetor. Usamos o procedimento
            TROCA definido  no captulo 6. Escrevemos nosso procedimento
            para colocar  nmeros reais em ordem crescente. Modificaes
            imediatas podem ser feitas para ordenar em ordem decrescente
            ou classificar vetores de outros tipos.
                 A grosso  modo o  "quick sort" seleciona um elemento do
            meio do  vetor e  passa para  a direita  desse  elemento  os
            elementos que  forem maiores  do que  ele  e  passa  para  a
            esquerda os que forem menores; depois divide o vetor em duas
            partes disjuntas  e  classifica  cada  parte  separadamente.
            Tentaremos descrever  a seguir  o  funcionamento  do  "quick
            sort" e exemplificaremos cada passo com o vetor
                    v = (87, 51, 12, 34, 52, 83, 33, 13, 59, 27)
            
                 (1)   Atribumos    s   variveis    inteiras   i,   j
            respectivamente os  valores de  INF e  SUP  fornecidos  como
            parmetros, e  atribumos a  MEIO o  valor do termo de ordem
            (i+j) div 2 de v. No caso do v acima, MEIO := v[5] = 52.
                 (2) Determinamos o menor ndice de v que est associado
            a um  elemento de  v maior  do que MEIO e redefinimos i como
            sendo o valor desse ndice. Determinamos o maior ndice de v
            que est  associado a  um elemento  de v menor do que MEIO e
            atribumos o  valor desse  ndice  a  j.  No  nosso  exemplo
            particular do  v anterior,  temos i  := 1  e j := 10, porque
            v[1] > MEIO e v[10] < MEIO.
                 (3) Trocamos  v[i] por  v[j], incrementamos  i  de  uma
            unidade e  decrementamos j de uma unidade. Ficamos assim com
            v[1] = 27, v[10] = 87, i = 2, j = 9.
                 (4) Cada  vez que o passo (3)  executado o i aumenta e
            o j diminui de valor. Repetir os passos (2) e (3) at i > j.
                 No nosso  caso particular, (2) e (3) vo ser executados
            at i  = 7  e j  = 6  e nesse momento tero sido trocados os
            elementos 27 e 87, 52 e 13, 83 e 33 e v ser o seguinte:
                    v = (27, 51, 12, 34, 13, 33, 83, 52, 59, 87)

                                       - 175 -





                 (5) Voltamos ao passo (1) com o v do passo (4), INF = 1
            e SUP = j, ou seja, aplicamos novamente o "quick sort" aos 6
            primeiros elementos de v do passo (4).
                 Obtemos v = (12, 13, 27, 33, 34, 51, 83, 52, 59, 87).
                 (6) Voltamos ao passo (1) com o v do passo (5), INF = i
            e SUP  = 10, ou seja, aplicamos novamente o "quick sort" aos
            4 ltimos  elementos de  v do  passo (5).  Com isso o v fica
            classificado em ordem crescente.
            
            
            CONST
              quant = 1000;  (* Quantidade maxima de elementos *)
                             (* a serem ordenados.             *)
            
            TYPE
              vetor = array[1..quant] of real;
            
            PROCEDURE QuickSort(var v: vetor; inf, sup: word);
            
            (* "Ordenacao rapida" em ordem crescente dos  elementos
                do vetor v com  indices i tais que  inf <= i <= sup  *)
            
            VAR
              i, j: word;
              meio: real;
            
            BEGIN
              i := inf; j := sup;
              meio := v[(inf + sup) div 2];
            
              repeat
                while (v[i] < meio) and (i < sup) do Inc(i);
                while (meio < v[j]) and (j > inf) do Dec(j);
            
            (*  Para   classificar  em   ordem  decrescente,   troque  o
                (v[i] < meio)  e  (meio < v[j])  acima por (v[i] > meio)
                e (meio > v[j]).   *)
            
                if (i <= j) then
                begin
                  Troca(v[i], v[j]);
                  Inc(i);
                  Dec(j)
                end;
            
              until (i > j);
            
              (* O "quick sort" chama a si mesmo para classificar as
                 partes   (v[inf], v[inf + 1], ..., v[j]) ou a parte
                 (v[i], v[2], ..., v[sup]) *)
            
              if (inf < j) then QuickSort(v, inf, j);
              if (i < sup) then QuickSort(v, i, sup);
            END;

                                       - 176 -





            
                 Em todo  processo recursivo,  deve ficar  bem  definido
            quando a  recursividade  deve  acabar,  ou  seja,  quando  o
            procedimento (ou funo) deve parar de chamar a si mesmo. No
            caso do  QuickSort, observe que ele chama a si mesmo somente
            nas suas duas ltimas linhas. Cada vez que o QuickSort chama
            a si  mesmo, o  intervalo INF..SUP   diminudo.  Verifique,
            como  exerccio,  que  quando  v  for  formado  de  1  ou  2
            elementos, ento  o QuickSort ordena v e no chama mais a si
            mesmo  para   isso.  Isso  mostra  que  a  recursividade  do
            QuickSort tem hora para acabar.
            
            
            11.3. EXERCCIOS  
            
            
            1) Construa  uma funo  potncia POT(x, n) = xn de expoente
            inteiro positivo  n e  base x  real, definida recursivamente
            por:
            
                 POT(x, 0) = 1, e POT(x, n) = x*POT(x, n - 1), se n > 0
            
            
            2)  A   seqncia  de  Fibonacci  tem  seus  dois  primeiros
            elementos iguais  a 1  e os  restantes so  a soma  dos dois
            elementos imediatamente anteriores:
            
                      1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
            
                 Defina recursivamente  uma funo FIB(n) que seja igual
            ao n-simo elemento da seqncia de Fibonacci.
            
            
            3) O lado L(n) de um polgono regular de n lados, n potncia
            de 2, inscrito em um crculo de raio 1  dado por:
                               __
                         /   \/2  , se n = 4
                 L(n) =  |      _____________________
                         |     /     ______________
                         \   \/2 - \/4 - (L(n/2))^2    , se n > 4
            
                 Defina  uma  funo  PER(n)  =  permetro  do  polgono
            regular de  n lados, n potncia de 2, inscrito em um crculo
            de raio  1 e  calcule PER(2048),  que  uma aproximao para
            2*Pi.
            
            
            4) Gere  aleatoriamente um  vetor de 1000 elementos inteiros
            n, com 0 <= n <= 20000, e use os procedimentos QUICKSORT e o
            algoritmo de  classificao do  captulo 9  para colocar  em
            ordem crescente  os elementos  do vetor.  Use o  GETTIME  da
            unidade  DOS   para  comparar  os  tempos  gastos  por  cada
            procedimento.
            

                                       - 177 -
