FUNÇÃO COMPUTADA POR UM PROGRAMA RECURSIVO EM UMA MAQUINA

FUNÇÃO COMPUTADA POR UM PROGRAMA RECURSIVO EM UMA MAQUINA

Nas linguagens de programação em geral o conceito de programa recursivo aparece relacionado ao de sub-rotinas recursivas, onde a recursão é uma forma indutiva de definir programas e as sub-rotinas permitem a estruturação hieraquica dos programas possibilitando niveis diferenciados de abstração.
Sendo que a Expressão de sub-rotinas é definida da seguinte maneira:
- A operação vazia, √, constitui uma expressão de sub-rotinas.
- Cada identificador de operação constitui uma expressão de sub-rotinas.
- Composição sequencial: Se D1 e D2 são expressões de sub-rotinas, então a composição sequencial denotada por: D1; D2 resulta em uma expressão de sub-rotinas cujo efeito é a execução de D1 e, após a execução de D2;
- Composição condicional: Se D1 e D2 são expressões de sub-rotinas e T é um identificador de teste, então a composição condicional denotada por: (se T então D1 senão D2) resulta em uma expressão de sub-rotinas cujo efeito é a execução de D1 se T é verdadeiro ou D2 se T é falso.

Para, Diverio e Menezes, 2011,o programa recursivo se define da seguinte forma:
"P é E0 onde R1 def E1, R2 def E2, ..., Rn def En onde (suponha k ∈ {1, 2, ..., n}):
E0 = Expressão Inicial, a qual é uma expressão de sub-rotinas;
Ek = Expressão que Define Rk, a expressão que define a sub-rotina identificada por Rk;
A operação vazia ✔constitui um programa recursivo que não faz coisa alguma. "

Para tanto a função computada por uma programa recursivo, de acordo com Diverio e Menezes, 2011, a computação se inicia na expressão inicial com a memória contendo o valor inicial resultante da aplicação da função de entrada sobre o dado fornecido, executa, passo a passo, testes e operações, na ordem determinada pelo programa, até que a expressão de sub-rotina resultante seja a expressão vazia, quando pára e o valor da função computada pelo programa é o valor resultante da aplicação da função de saída ao valor da memória