Por dentro da recursão

Cefet-MG
Arquitetura e Estrutura de Dados
Laboratório
Trabalho Pratico III
Por dentro da Recursão

Aluno: Oscar de Souza Dias

Parte 1: Intendendo a Recursão:
Vamos aprender como funciona a recursão usando a função de Ackermann, implementação em anexo.
Uma função recursiva é uma função definida em torno de si mesma, isto é, antes de terminar a execução ela volta a estanciar a si própria. Toda função recursiva tem que ter uma condição de terminação bem definida, para não entrar em loop infinito. No caso desta função sua terminação se da quando m = 0, na instancia de mais alto nível, pois vamos ver que está função tem vários níveis de instanciações.
A seguir temos a impressão das chamadas recursivas e o diagrama, para valores de m = 2, e n = 2:

A1(2,2) // primeira chamada da função m=2,n=2 m,n≃0A2(2,1) m,n≃0A3(2,0) n=0A4(1,1) Função de Ackermann: m,n≃0A5(1,0) A(0, n) = n+1 n=0A6(0,1) A(m, 0) = A(m-1, 1) m=0A7(0,2) A(m, n) = A(m-1, A(m, n-1)) m=0A8(1,3) m,n≃0A9(1,2)Diagrama: m,n≃0A10(1,1) m,n≃0A11(1,0) n=0A12(0,1) m=0A13(0,2) m=0A14(0,3) m=0A15(0,4) m=0A16(1,5) m,n≃0A17(1,4) m,n≃0A18(1,3) m,n≃0A19(1,2) m,n≃0A20(1,1) m,n≃0A21(1,0) n=0A22(0,1) m=0A23(0,2) m=0A24(0,3) m=0A25(0,4) m=0A26(0,5) m=0A27(0,6)

A tabulação:
Primeira tabulação, chamada e referente a uma instanciação onde m = 0;
Segunda tabulação, chamada e referente a uma instanciação onde n = 0;
Terceira tabulação, chamada e referente a uma instanciação onde m e n ≃ 0;
A partir das chamadas impressas e do diagrama podemos intender como funcionar a recursividade e a própria função de Ackermann. ~=
Se m e n ≃ 0, é feita outra chamada de função onde vai diminuindo os valores de n ate 0, onde a função volta um nível, e a cada nível que é voltado o valor de m diminui-se também ate 0. E quando m = 0, a função retorna um valor inteiro, que é o corrente valor de n onde é somado 1(um).
Assim podemos ver que a recursão sempre volta a chamar a