Programação recursiva

Na programação recursiva , um procedimento , função ou método em um programa de computador chama a si mesmo (ou seja, contém uma recursão ). A chamada mútua também representa uma recursão.

Uma condição de término nesta função é importante para a programação recursiva , porque, de outra forma, o programa recursivo teoricamente chamaria a si mesmo com frequência infinita.

A programação recursiva pode ser usada, entre outras coisas, em linguagens de programação procedurais e orientadas a objetos . Embora essas linguagens permitam expressamente a recursão em seu padrão de linguagem , as auto-chamadas e as chamadas recíprocas são a exceção aqui (devido aos paradigmas de programação usados ). Embora a recursão seja frequentemente usada na prática para melhorar o estilo de programação , a maioria delas são funções em essas linguagens são puramente iterativas .

Em alguns idiomas, como B. em algumas linguagens de programação funcionais ou macroprocessadores , o método de programação recursiva deve ser usado, visto que faltam construções de linguagem iterativa .

Exemplos

Faculdade

Um exemplo de uso de programação recursiva é calcular o fatorial de um número. O fatorial é o produto de todos os inteiros de 1 até esse número. Portanto, o fatorial de 4 é . ${\ displaystyle 1 \ times 2 \ times 3 \ times 4 = 24}$

A maioria dos matemáticos define o corpo docente desta forma (uma definição recursiva):

O fatorial do número 0 é, por definição, 1.
O fatorial de um inteiro maior que zero é o produto desse número pelo fatorial do próximo inteiro inferior.

A definição funciona assim:

Se você quiser calcular o fatorial de 4 , primeiro terá que calcular o fatorial de 3 e multiplicar o resultado por 4.

Se quiser calcular o fatorial de 3, primeiro você deve calcular o fatorial de 2 e multiplicar o resultado por 3.

Se você deseja calcular o fatorial de 2, primeiro deve calcular o fatorial de 1 e multiplicar o resultado por 2.

Se quiser calcular o fatorial de 1, primeiro você deve calcular o fatorial de 0 e multiplicar o resultado por 1.

De acordo com a definição, o fatorial de 0 é 1.

O fatorial de 1 é, portanto, 1 * 1 = 1

Portanto, o fatorial de 2 é 1 * 1 * 2 = 2

Portanto, o fatorial de 3 é 1 * 1 * 2 * 3 = 6

Portanto, o fatorial de 4 é 1 * 1 * 2 * 3 * 4 = 24

Em uma linguagem de programação como Pascal, que permite a programação recursiva, você pode entrar no corpo docente da seguinte maneira:

É definida uma função fatorial , que recebe um número x como valor de entrada. Esta função multiplica x pelo valor de retorno do fatorial (x - 1), exceto para x = 0 , então a função retorna o resultado 1. Esta é a condição de finalização:

Implementação recursiva da função fatorial

function factorial(x: Integer): Integer;
begin
    if x = 0 then
        factorial := 1
    else
        factorial := x * factorial(x - 1);
end;

Com o número inicial x = 4 , o computador contaria:

4 * (3 * (2 * (1 * factorial(0))))

o resultado é então o resultado correto, ou seja, 24.

Busca binária

A pesquisa binária em uma matriz pode ser implementada recursivamente . Se o elemento do meio for menor do que o elemento pesquisado, a metade posterior da matriz é pesquisada recursivamente. Se for maior do que o elemento que está sendo pesquisado, a metade frontal da matriz é pesquisada recursivamente. Se for igual ao elemento procurado, a procura termina.

A condição de término para a recursão é cumprida se o elemento do meio for o mesmo que o elemento pesquisado, ou seja, a pesquisa for bem-sucedida, ou se o índice final for menor do que o índice inicial, ou seja, a pesquisa não foi bem-sucedida.

A seguinte função ( método ) para pesquisa binária recursiva está na linguagem de programação C # :

int RekursiveBinaereSuche(int[] werte, int gesuchterWert, int startIndex, int endIndex)
{
    if (endIndex < startIndex)
    {
        // Wenn Element nicht gefunden, dann null zurückgeben
        return null;
    }
    int mittlererIndex = (startIndex + endIndex) / 2;
    if (werte[mittlererIndex] == gesuchterWert)
    {
        // Wenn Element gefunden, dann Index zurückgeben
        return mittlererIndex;
    }
    else
    {
        if (werte[mittlererIndex] < gesuchterWert)
        {
            // Rekursiver Aufruf der Funktion für die hintere Hälfte
            return RekursiveBinaereSuche(werte, gesuchterWert, mittlererIndex + 1, endIndex);
        }
        else
        {
            // Rekursiver Aufruf der Funktion für die vordere Hälfte
            return RekursiveBinaereSuche(werte, gesuchterWert, startIndex, mittlererIndex - 1);
        }
    }
}

Eficiência

Os programas recursivos não são bons no desempenho geral . Devido às chamadas de função repetidas (encarnações), o mesmo código de entrada de método é processado repetidamente e o contexto é salvo a cada encarnação , o que leva a um código de programa adicional e maior consumo de memória . No entanto, todos os algoritmos recursivos também podem ser implementados por meio de programação iterativa e vice-versa.

Faculdade

O corpo docente também poderia ter sido implementado assim :

function factorial(x: Integer): Integer;
    var i, number: Integer;
begin
    number := 1;

    for i := 1 to x do
        number := number * i;

    factorial := number;
end;

A regra aqui é que a implementação iterativa costuma ser mais eficiente para problemas simples . Z também deveria. Por exemplo, a função docente pode ser implementada iterativamente na prática por uma questão de eficiência. No caso de problemas complicados (por exemplo, tarefas com árvores ), por outro lado, muitas vezes vale a pena usar uma solução recursiva, uma vez que uma formulação iterativa para tais problemas pode rapidamente se tornar muito confusa - e ineficiente - porque no pior caso, o A própria pilha é causada pelo algoritmo iterativo. O que deve ser gerenciado é o que o processador faria diretamente.

Nem todas as linguagens de programação de alto nível permitem chamadas recursivas. Um exemplo disso é o Fortran . Outras linguagens de programação , por outro lado, são basicamente recursivas (como Prolog ). Essas linguagens de programação recursiva e também outras linguagens, como B. Esquema define a ordem mais eficiente de recursão .

implementação

A recursão é geralmente implementada por uma pilha que aceita os endereços de retorno, mas também todas as variáveis locais e possivelmente os resultados da função. Se, como no exemplo acima, o corpo docente cobrar 4, a cada chamada, as seguintes informações serão colocadas na pilha:

Espaço para resultados
Argumento x
Endereço de devolução

Primeiro, fac (4) seria chamado no programa principal e as seguintes informações seriam colocadas na pilha :

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	3	Endereço de retorno no programa principal

A função fatorial agora verifica se o argumento é 0. Como este não é o caso, 4 * fac (3) é calculado. Portanto, o primeiro fac deve ser chamado com o argumento 3:

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	6º	Endereço de devolução na função docente

O argumento não é igual a 0 novamente, então continuamos com 3 * fac (2) .

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
		6º	Endereço de devolução na função docente
		7º	Espaço para resultados
		8º	2 (argumento)
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	9	Endereço de devolução na função docente

O argumento não é igual a 0 novamente, ou seja, 2 * fac (1) .

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
		6º	Endereço de devolução na função docente
		7º	Espaço para resultados
		8º	2 (argumento)
		9	Endereço de devolução na função docente
		10	Espaço para resultados
		11	1 (argumento)
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	12º	Endereço de devolução na função docente

O argumento novamente não é igual a 0, ou seja, 1 * fac (0) .

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
		6º	Endereço de devolução na função docente
		7º	Espaço para resultados
		8º	2 (argumento)
		9	Endereço de devolução na função docente
		10	Espaço para resultados
		11	1 (argumento)
		12º	Endereço de devolução na função docente
		13º	Espaço para resultados
		14º	0 (argumento)
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	Dia 15	Endereço de devolução na função docente

Agora o argumento é 0, o resultado é 1. Pegamos o endereço de retorno e o argumento da pilha e escrevemos 1 no espaço fornecido. O salto de retorno leva de volta à função do corpo docente:

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
		6º	Endereço de devolução na função docente
		7º	Espaço para resultados
		8º	2 (argumento)
		9	Endereço de devolução na função docente
		10	Espaço para resultados
		11	1 (argumento)
		12º	Endereço de devolução na função docente
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	13º	1 (resultado)

Agora você pode multiplicar o resultado pelo argumento (1 * 1). O novo resultado é novamente 1. O endereço de retorno e o argumento são buscados na pilha e o novo resultado é escrito no espaço fornecido. Retorne à função docente:

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
		6º	Endereço de devolução na função docente
		7º	Espaço para resultados
		8º	2 (argumento)
		9	Endereço de devolução na função docente
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	10	1 (resultado)

Novamente, o resultado é multiplicado pelo argumento (1 * 2). De volta à função docente:

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
		4º	Espaço para resultados
		5	3 (argumento)
		6º	Endereço de devolução na função docente
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	7º	2 (resultado)

O resultado é multiplicado pelo argumento (2 * 3). De volta à função docente:

Início da pilha	${\ displaystyle \ rightarrow}$	1	Espaço para resultados
		2	4 (argumento)
		3	Endereço de retorno no programa principal
Ponteiro de pilha	${\ displaystyle \ rightarrow}$	4º	6 (resultado)

O resultado é multiplicado pelo argumento (6 * 4). Voltar para o programa principal

Stack start
stack pointer

{\ displaystyle \ rightarrow}

1

24 (resultado)

O programa principal só precisa buscar o resultado 24 da pilha .

Languages

Programação recursiva

Índice

Exemplos

Faculdade

Busca binária

Eficiência

Faculdade

implementação

Veja também