Recursividade

Recursividade

Recursividade é quando na codificação de uma função ocorre a chamada de própria função. Fazendo assim que nesse ponto da execução da função a mesma volte a ser executada, porém pela segunda vez. Ao final da execução da segunda vez volta-se a continuar a executar a função da primeira vez.

As funções recursivas são em sua maioria soluções mais elegantes e simples, se comparadas a funções tradicionais ou iterativas (laços), já que executam tarefas repetitivas sem utilizar nenhuma estrutura de repetição, como for ou while .

Porém essa elegância e simplicidade têm um preço que requer muita atenção em sua implementação. A cada chamada a própria função é criada uma pilha de execução dessa função recursiva.

Para cada nova chamada é criado um novo contexto para a execução da função. Então para todas as variáveis locais da função são criadas novas alocações.

Cada vez que uma função é chamada de forma recursiva, são alojados e armazenados uma cópia dos seus parâmetros, de modo a não perder os valores dos parâmetros das chamadas anteriores.

Em cada instância da função, só são diretamente acessíveis os parâmetros criados para esta instância, não sendo possível acessar os parâmetros das outras instâncias.

Existem duas formas de recursividade:

1. recursão direta: a função A chama a própria função A;

2. recursão indireta: a função A chama uma função B que, por sua vez, chama A.
Para que uma implementação de recursividade não fique o infinito, tem que haver uma condição de parada em que a função não invoque novamente a própria função.

Execução

Internamente, quando qualquer chamada de função é feita dentro de um programa, é criado um Registro de Ativação na Pilha de Execução do programa.

O registro de ativação armazena os parâmetros e variáveis locais da função bem como o “ponto de retorno” no programa ou subprograma que chamou essa função.

Ao final da execução dessa função, o registro é desempilhado e a execução volta ao subprograma que chamou a função.

Recursividade vale a pena para Algoritmos complexos, cuja a implementação iterativa é complexa e normalmente requer o uso explícito de uma pilha.

Uma função pode chamar a si própria por um número limitado de vezes. Esse limite é dado pelo tamanho da pilha. Se o valor correspondente ao tamanho máximo da pilha for atingido, haverá um estouro da pilha ou “Stack Overflow”.

Deve-se utilizar a recursividade quando esta forma for a mais simples e intuitiva de implementar uma solução para a resolução de um determinado problema. Se não for (simples e intuitiva), será então melhor empregar outros métodos não recursivos, também chamados de “métodos iterativos”.

Funções Recursivas contém duas partes fundamentais:

1. Ponto de Parada ou Condição de Parada : que é o ponto onde a função será encerrada, e é geralmente um limite superior ou inferior da regra geral.

2. Regra Geral : é o método que reduz a resolução do problema através da invocação recursiva de casos menores, que por sua vez são resolvidos pela resolução de casos ainda menores pela própria função, assim sucessivamente até atingir o “ponto de parada” que finaliza o método.

Exemplo:

 

Deixe uma resposta

Specify Google Client ID and Secret in Super Socializer > Social Login section in admin panel for Google Login to work

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *