 |
| Bellacosa Mainframe apresenta cobol recursivo parte ii sec a |
☕ Um Café no Bellacosa Mainframe
COBOL Recursivo — Muito Além do Fatorial (Parte 2A)
Construindo Nosso Primeiro Programa Recursivo: Entendendo o Call Stack Passo a Passo
"Todo programador COBOL aprende a escrever um PERFORM. Poucos já pararam para observar o que realmente acontece quando um programa chama a si próprio. Nesta segunda parte, vamos acompanhar cada chamada como se estivéssemos olhando diretamente para a memória do IBM Z."
Introdução
Na primeira parte desta série entendemos que recursividade não é simplesmente "um programa chamando ele mesmo".
Ela representa a criação de novos contextos de execução, cada um possuindo seu próprio estado, seus parâmetros e, quando corretamente projetado, suas próprias variáveis locais.
Agora chegou o momento de acompanhar isso acontecendo.
Não vamos começar falando de árvores binárias.
Nem XML.
Nem JSON.
Vamos começar pelo exemplo mais famoso da computação.
O cálculo do fatorial.
Não porque seja o algoritmo mais útil.
Mas porque ele é pequeno o suficiente para enxergarmos exatamente como a pilha cresce e diminui.
Nosso objetivo não é aprender matemática.
Nosso objetivo é aprender como o Enterprise COBOL pensa.
Antes de escrever uma linha de código...
Imagine que alguém pergunte:
Quanto vale 5!?
Matematicamente sabemos:
5! = 5 × 4 × 3 × 2 × 1
Mas existe outra forma de enxergar.
5!
↓
5 × 4!
↓
5 × (4 × 3!)
↓
5 × (4 × (3 × 2!))
↓
5 × (4 × (3 × (2 × 1!)))
Perceba algo interessante.
O problema original é reduzido a um problema menor.
Depois outro.
Depois outro.
Até chegar em um caso extremamente simples.
1! = 1
Esse ponto recebe um nome muito importante.
Caso Base (Base Case).
Toda recursão possui um.
Sem ele...
O algoritmo nunca termina.
O primeiro programa recursivo
Vamos analisar uma implementação didática.
IDENTIFICATION DIVISION.
PROGRAM-ID. FATORIAL IS RECURSIVE.
DATA DIVISION.
LOCAL-STORAGE SECTION.
01 LS-NUMERO PIC 9(4).
01 LS-RESULTADO PIC 9(18).
LINKAGE SECTION.
01 LK-NUMERO PIC 9(4).
01 LK-RESULTADO PIC 9(18).
PROCEDURE DIVISION USING LK-NUMERO LK-RESULTADO.
IF LK-NUMERO <= 1
MOVE 1 TO LK-RESULTADO
ELSE
SUBTRACT 1 FROM LK-NUMERO GIVING LS-NUMERO
CALL "FATORIAL"
USING LS-NUMERO
LS-RESULTADO
COMPUTE LK-RESULTADO =
LK-NUMERO * LS-RESULTADO
END-IF
GOBACK.
Não se preocupe se parecer estranho.
Vamos desmontá-lo completamente.
O primeiro detalhe importante
Observe a primeira linha.
PROGRAM-ID. FATORIAL IS RECURSIVE.
Essa pequena palavra muda completamente o comportamento esperado do programa.
Ela informa ao compilador que poderão existir várias ativações simultâneas da mesma rotina.
Sem isso, o compilador poderá assumir um modelo inadequado para esse tipo de chamada.
Por que usamos LOCAL-STORAGE?
Veja novamente.
LOCAL-STORAGE SECTION.
01 LS-NUMERO.
01 LS-RESULTADO.
Muitos iniciantes perguntam:
"Posso colocar isso na Working-Storage?"
Tecnicamente...
Pode.
Mas provavelmente produzirá resultados incorretos.
Vamos entender por quê.
O que aconteceria usando Working-Storage?
Imagine:
WORKING-STORAGE
LS-NUMERO = 5
Primeira chamada.
Tudo bem.
Agora o programa chama ele mesmo.
WORKING-STORAGE
LS-NUMERO = 4
Ops.
O valor 5 desapareceu.
Nova chamada.
WORKING-STORAGE
LS-NUMERO = 3
Mais uma vez.
WORKING-STORAGE
LS-NUMERO = 2
Depois.
WORKING-STORAGE
LS-NUMERO = 1
Quando retornar...
Quem lembra do cinco?
Ninguém.
Ele foi sobrescrito.
É exatamente esse tipo de problema que Local-Storage resolve.
Agora usando Local-Storage
Cada chamada recebe sua própria cópia.
Visualmente.
FATORIAL(5)
LS-NUMERO = 5
Chama.
FATORIAL(4)
LS-NUMERO = 4
Chama.
FATORIAL(3)
LS-NUMERO = 3
Depois.
FATORIAL(2)
LS-NUMERO = 2
Depois.
FATORIAL(1)
LS-NUMERO = 1
Nenhuma variável interfere na outra.
Cada ativação possui seu próprio ambiente.
Vamos acompanhar a execução
Chamamos.
CALL FATORIAL(5)
O programa verifica.
5 <= 1 ?
Não.
Então calcula.
5 × FATORIAL(4)
Mas ele ainda não sabe quanto vale FATORIAL(4).
Então precisa descobrir.
Segunda chamada
Agora executa.
FATORIAL(4)
Pergunta.
4 <= 1 ?
Não.
Calcula.
4 × FATORIAL(3)
Ainda não sabe.
Então chama novamente.
Terceira chamada
FATORIAL(3)
Ainda não terminou.
Chama.
FATORIAL(2)
Quarta chamada
Agora.
FATORIAL(2)
Ainda não chegou.
Chama.
FATORIAL(1)
Quinta chamada
Finalmente.
FATORIAL(1)
Agora acontece algo mágico.
1 <= 1
SIM
O algoritmo encontrou o caso base.
Retorna.
1
A partir daqui...
A pilha começa a voltar.
A pilha crescendo
Durante a descida.
+----------------------+
|FATORIAL(1) |
+----------------------+
|FATORIAL(2) |
+----------------------+
|FATORIAL(3) |
+----------------------+
|FATORIAL(4) |
+----------------------+
|FATORIAL(5) |
+----------------------+
Observe.
Nenhum cálculo foi concluído.
Todos aguardam.
Agora começa a subida
FATORIAL(1)
retorna
1
Então.
FATORIAL(2)
faz.
2 × 1
=
2
Retorna.
Depois.
FATORIAL(3)
recebe.
2
Calcula.
3 × 2
=
6
Retorna.
Depois.
FATORIAL(4)
recebe.
6
Calcula.
4 × 6
=
24
Retorna.
Depois.
FATORIAL(5)
recebe.
24
Calcula.
5 × 24
=
120
Agora sim.
Fim.
O momento em que tudo faz sentido
Perceba.
A descida não resolve o problema.
Ela apenas divide.
A subida resolve.
Esse conceito aparece em praticamente todos os algoritmos recursivos.
O papel do CALL
Muitos imaginam que o CALL copie o programa inteiro.
Não.
Ele apenas cria um novo contexto.
É como se o Language Environment dissesse:
"Guarde tudo o que estava acontecendo."
"Execute esta nova instância."
"Quando terminar, volte exatamente daqui."
Esse "guardar tudo" inclui:
registradores;
endereço de retorno;
parâmetros;
estado da execução.
Comparando com PERFORM
Agora vamos resolver exatamente o mesmo problema usando um laço tradicional.
MOVE 1 TO WS-RESULTADO
PERFORM VARYING WS-I
FROM 1 BY 1
UNTIL WS-I > WS-NUMERO
MULTIPLY WS-I
BY WS-RESULTADO
END-PERFORM
Muito menor.
Muito mais simples.
Muito mais eficiente.
Então surge a pergunta.
Por que alguém usaria recursão?
Porque nem todos os problemas são lineares.
Imagine uma árvore.
CEO
/ | \
Financeiro RH TI
|
Recrutamento
Como percorrer isso usando apenas PERFORM?
É possível.
Mas rapidamente surgem:
pilhas auxiliares;
vetores;
índices;
controles complexos.
Já a solução recursiva acompanha naturalmente a estrutura da árvore.
Ela entra em um nó.
Depois em seus filhos.
Depois nos filhos dos filhos.
E assim sucessivamente.
A recursão modela o problema
Esse talvez seja o conceito mais importante deste artigo.
A melhor solução nem sempre é a mais rápida.
Muitas vezes ela é a que representa o problema de forma mais natural.
Uma árvore chama outra árvore.
Uma pasta contém outras pastas.
Um elemento XML contém outros elementos.
Um objeto JSON contém outros objetos.
Todos esses cenários possuem uma natureza recursiva.
O custo da elegância
Infelizmente...
Elegância tem preço.
Cada chamada implica em:
criação de um novo frame;
salvamento de registradores;
passagem de parâmetros;
reserva de memória local;
desvio para uma nova execução;
retorno ao ponto original.
Enquanto um PERFORM reutiliza o mesmo contexto durante todas as iterações, a recursão cria um novo contexto a cada nível.
Por isso, em rotinas batch que processam milhões de registros sequenciais, o PERFORM quase sempre será mais eficiente.
O que um Programador COBOL Padawan deve observar neste exemplo
Antes de pensar em escrever algoritmos recursivos sofisticados, é importante consolidar alguns princípios:
Toda recursão precisa obrigatoriamente de um caso base. Sem ele, a pilha cresce indefinidamente até provocar falha de execução.
Cada chamada deve aproximar o problema da condição de parada. Se o valor de entrada não evolui em direção ao caso base, o algoritmo nunca termina.
Variáveis que representam o estado da execução devem, preferencialmente, estar em LOCAL-STORAGE, evitando interferência entre diferentes ativações.
A recursão não substitui o
PERFORM. Ela é uma técnica para problemas cuja própria estrutura é hierárquica.Antes de implementar uma solução recursiva, pergunte: este problema realmente possui uma estrutura recursiva ou estou apenas complicando um processamento linear?
Essa última pergunta evita um dos erros mais comuns entre desenvolvedores iniciantes: usar recursão apenas porque ela parece elegante.
Um pequeno exercício para o leitor
Pegue papel e lápis.
Escreva a sequência:
FATORIAL(6)
Agora desenhe seis caixas empilhadas.
Dentro de cada caixa, anote:
valor recebido;
valor retornado;
quem chamou aquela rotina.
Ao final do exercício, você perceberá algo importante: o algoritmo não "anda para frente". Ele mergulha até o caso base e depois retorna desfazendo a pilha, uma camada de cada vez.
Esse simples desenho vale mais do que dezenas de linhas de código para compreender a essência da recursividade.
Encerrando o Café
Se você chegou até aqui, provavelmente percebeu que o exemplo do fatorial nunca foi o verdadeiro objetivo deste artigo.
O fatorial é apenas uma desculpa elegante para observar o funcionamento interno do Enterprise COBOL.
O aprendizado mais valioso não está no resultado 120, mas em entender como o compilador, o Language Environment e a pilha de execução trabalham juntos para permitir que várias instâncias do mesmo programa coexistam de forma segura.
É essa engenharia invisível que torna possível escrever compiladores, interpretadores, analisadores de XML, processadores de JSON e diversas outras soluções sofisticadas em COBOL moderno.
No próximo café, deixaremos os exemplos acadêmicos para trás. Vamos explorar algoritmos realmente interessantes — Fibonacci, percorrimento de árvores, busca em profundidade (DFS), QuickSort, MergeSort, XML, JSON e outros cenários em que a recursividade deixa de ser apenas uma curiosidade e passa a ser a ferramenta mais elegante para resolver problemas complexos no universo IBM Mainframe.
Sem comentários:
Enviar um comentário