Recursão é uma técnica de programação na qual chamamos uma função ou procedimento de dentro dela mesma. Ou seja, a definição de recursão poderia ser:

  Recursão -> vide Recursão
	

Mas essa é uma definição meio falha, pois ela nunca pára. Então, para que a recursão seja perfeita, temos que dar uma condição de parada para a função. Assim, uma definição melhor é:

  Recursão ->
    se você não entendeu o que é
      vide Recursão
	

Vamos ver um exemplo prático: como calcular n!

Sabemos que n! = n × (n-1)! e que 0! = 1. Então:

1.  FUNCTION fatorial(n : integer) : integer;
    BEGIN
2.    IF n=0 THEN fatorial := 1
3.    ELSE fatorial := n * fatorial(n-1)
    END;
	

Estranho, não? O que acontece aqui? Cada vez que chamamos uma função ou procedimento recursivamente, essa chamada, juntamente com todos seus parâmetros e variáveis locais do procedimento ou função, é colocada em uma pilha. Assim, quando a última chamada é feita, ou seja, quando essa última chamada retorna, o computador vai desempilhando.

Se quisermos acessar alguma variável da função ou procedimento, estaremos acessando a variável da última chamada feita, ou seja, da que está no topo da pilha.

Vamos ver o funcionamento da pilha no caso da função acima, para 3! Na linha 1 chamei a função pela primeira vez:

Como 3 ≠ 0, então a linha 3 é executada, e chamo novamente a função

Como 2 ≠ 0, então a linha 3 é executada, e chamo novamente a função

Como 1 ≠ 0, então a linha 3 é executada, e chamo novamente a função

agora 0 = 0, então a linha 2 é executada, e a função retorna pela primeira vez, retornando o valor 1. Essa chamada é desempilhada:

Como a chamada a fatorial(0) foi feita na linha 3 da chamada a fatorial(1), o programa continua a rodar de lá, fazendo 1 × 1. Ou seja, multiplicando o n pelo valor de retorno de fatorial(n-1). Esse valor é, então retornado, e a chamada é desemplidada:

Como a chamada a fatorial(1) foi feita na linha 3 da chamada a fatorial(2), o programa continua a rodar de lá, fazendo 2 × 1. Esse valor é, então retornado, e a chamada é desemplidada:

Como a chamada a fatorial(2) foi feita na linha 3 da chamada a fatorial(3), o programa continua a rodar de lá, fazendo 3 × 2. Esse valor é, então retornado, e a chamada é desemplidada. No caso, esse é o valor de retorno da função, pois não há mais chamadas recursivas a serem desempilhadas. E eis que a resposta será 6, ou seja 3!.

Mas como nem tudo é maravilha, apesar de facilitar nossa vida, recursão tem um preço: empilhar tudo isso gasta memória.

Vejamos agora como fazer x^y (x elevado a y).

Note que x^y = x × x^(y-1), e x^0 = 1. Então:

1.  FUNCTION pot(x,y : integer) : integer;
    BEGIN
2.    IF y=0 THEN pot := 1
3.    ELSE pot := x * pot(x,y-1)
    END;
	

Mas há outro modo de fazer isso, note que:

  x^1024 = (x^512)^2
  x^512  = (x^256)^2
  x^256  = (x^128)^2
  ...
  x^4    = (x^2)^2
  x^2    = x × x
	

Então temos que

  x^y = 1 se y = 0
        x × x^(y-1) se y for ímpar
	(x^(y/2))^2 se y for par
	

Assim, se y for par, faremos menos chamadas recursivas. A função, então, é:

1.  FUNCTION pot(x,y : integer) : integer;
    BEGIN
2.    IF y=0 THEN pot := 1
      ELSE
3.      IF Odd(y) THEN pot := x * pot(x,y-1)
4.      ELSE por := Sqr(pot(x, y DIV 2))
    END;
	

Opa! quem é esse Odd?

  Odd(x : Longint) : Boolean;
	

retorna True se x for ímpar e False se não.

Mas será que esse algoritmo é realmente melhor? Analizemos o primeiro para 3^4:

Na primeira chamada temos:

como 4 ≠ 0 e é par, a linha 3 é executada, chamando pot novamente:

como 3 ≠ 0 e é par, a linha 3 é executada, chamando pot novamente:

assim vamos indo para 1:

e, por fim

Agora, 0 = 0, então, pela linha 2, pot retorna 1

na linha 3, de onde pot(3,0) foi chamada, pot retorna x × 1 = 3

na linha 3, de onde pot(3,1) foi chamada, pot retorna x × 3 = 9

na linha 3, de onde pot(3,2) foi chamada, pot retorna x × 9 = 27

finalmente, na linha 3, de onde pot(3,3) foi chamada, pot retorna x × 27 = 81. O resultado final. Note que chegamos a ter 5 elementos na pilha.

Agora vamos analizar o segundo algoritmo: chamamos a função

como 4 é ≠ 0 e par, então a linha 4 é executada:

como 2 é ≠ 0 e par, então a linha 4 é executada:

como 1 é ≠ 0 e ímpar, então a linha 3 é executada:

agora, a linha 2 é executada, retornando 1 e desempilhando essa chamada:

como a chamada no topo parou na linha 3, e pot(3,0) retornou 1, termino a linha 3, retornando 3 × 1 = 3.

como a chamada no topo parou na linha 4, e pot(3,1) retornou 3, termino a linha 4, retornando 3^2 = 9.

por fim, como a chamada no topo parou na linha 4, e pot(3,2) retornou 9, termino a linha 4, retornando 9^2 = 81. Eis nossa resposta. Qual o número máximo de elementos na pilha? 4, 1 a menos que no algoritmo 1. E isso com y=4 somente. Se fizermos um y grande essa diferença sobe. Ou seja, esse algoritmo é realmente melhor.

Agora vejamos um último exemplo. Vamos rever um algoritmo de ordenação, só que dessa vez, usando recursão.

Lembra da ordenação por seleção? Seu algoritmo era:

  procuro o menor elemento do vetor
  coloco esse elemento na primeira posição
  ordeno o resto do vetor
	

Esse "ordeno o resto do vetor" é recursivo. Então vamos lá, o procedimento de ordenação fica:

  {ordena o vetor v, com índices começando em início e
   terminando em fim}
  PROCEDURE ordena(VAR v : vetor; inicio, fim : integer);
  VAR menor : integer; {posição do menor elemento}
  BEGIN
    IF inicio < fim THEN
    BEGIN {senão já está ordenado, tem um só elemento}
      menor := PosMenor(v,inicio,fim);

      Troca(v[menor],v[inicio]);

      {ordeno o resto}
      Ordena(v,inicio + 1,fim)
    END
  END;
	

Bem mais simples que a não recursiva, não é?

Agora precisamos de uma função chamada PosMenor que me retorne o índice do menor elemento de v começando a busca no índice "inicio" e terminando em "fim", e um procedimento que troque dois valores no vetor:

  FUNCTION PosMenor(v : vetor; i,f:integer) : integer;
  VAR men  : tipo;
      cont : integer;
  BEGIN
    men := v[i];
    PosMenor := i;
    FOR cont:=i TO f DO
      IF men > v[cont] THEN
      BEGIN
        men := v[cont];
	PosMenor := cont
      END
  END;

  PROCEDURE Troca(var a,b : tipo);
  VAR c : tipo;
  BEGIN
    c := a;
    a := b;
    b := c
  END;
	

Então o programa fica:

  PROGRAM Selecao;

  CONST MAX = 10;
  TYPE tipo  = real;
       vetor = ARRAY[1..MAX] OF tipo;

  VAR v : vetor;

  FUNCTION PosMenor(v : vetor; i,f:integer) : integer;
  VAR men  : tipo;
      cont : integer;
  BEGIN
    men := v[i];
    PosMenor := i;
    FOR cont:=i TO f DO
      IF men > v[cont] THEN
      BEGIN
        men := v[cont];
	PosMenor := cont
      END
  END;

  PROCEDURE Troca(var a,b : tipo);
  VAR c : tipo;
  BEGIN
    c := a;
    a := b;
    b := c
  END;

  PROCEDURE ordena(VAR v : vetor; inicio, fim : integer);
  VAR menor : integer; {posição do menor elemento}
  BEGIN
    IF inicio < fim THEN
    BEGIN {senão já está ordenado, tem um só elemento}
      menor := PosMenor(v,inicio,fim);

      Troca(v[menor],v[inicio]);

      {ordeno o resto}
      Ordena(v,inicio + 1,fim)
    END
  END;

  BEGIN
    {carrego o vetor vet}
    Ordena(vet);
    {imprimo vet}
  END.
	

o código para carregar e imprimir vet fica como exercício.

‹— Parte XXVI — Página da disciplina — Parte XXVIII —›