FUNCIONAMENTO DO ALGORITMO RECURSIVO

FUNCIONAMENTO DE UM ALGORITMO RECURSIVO.

Definição.

O princípio de funcionamento de um algoritmo recursivo é diminuir sucessivamente o problema em problemas menores ou mais simples, até que a simplicidade do problema reduzido permita resolvê-lo de forma direta, sem recorrer a si mesmo. Quando isso ocorre, temos uma condição de parada, a qual deve estar presente em pelo menos um local dentro algoritmo. Sem esta condição o algoritmo não para de chamar a si mesmo, até estourar a capacidade da pilha, o que geralmente causa efeitos colaterais e até mesmo o término indesejável do programa.

Um algoritmo recursivo deve fazer pelo menos uma chamada a si mesmo, de forma direta (podemos ver o algoritmo sendo chamado dentro dele mesmo) ou indireta (o algoritmo chama um outro algoritmo, que por sua vez invoca uma chamada ao primeiro.

Para todo algoritmo recursivo existe um outro correspondente iterativo (não recursivo), que executa a mesma tarefa. Implementar um algoritmo recursivo, partindo de uma definição recursiva do problema, em uma linguagem de programação de alto nível como Pascal e C é simples e quase imediato, pois o seu código é praticamente transcrito para a sintaxe da linguagem. Por essa razão, em geral, os algoritmos recursivos possuem código mais claro (legível) e mais compacto do que os correspondentes iterativos. Além disso, muitas vezes, é evidente a natureza recursiva do problema a ser resolvido, como é o caso de problemas envolvendo árvores — estruturas de dados naturalmente recursivas.

Vantagens

Os algoritmos recursivos normalmente são mais compactos, mais legíveis e mais fáceis de serem compreendidos. Algoritmos para resolver problemas de natureza recursiva são fáceis de serem implementados em linguagens de programação de alto nível.

Desvantagens

Por usarem intensivamente a pilha, o que requer alocações e desalocações de memória, os algoritmos recursivos tendem a ser mais lentos que os equivalentes iterativos, porém pode valer a pena sacrificar a eficiência em benefício da clareza.

Aplicações

Nem sempre a natureza recursiva do problema garante que um algoritmo recursivo seja a melhor opção para resolvê-lo. O algoritmo recursivo para obter a sequência de Fibonacci é um ótimo exemplo disso.

Algoritmos recursivos são aplicados em diversas situações como em:

i) problemas envolvendo manipulações de árvores;

ii) analisadores léxicos recursivos de compiladores; e

iii) problemas que envolvem tentativa e erro ("Backtracking").

Exemplo de programa recursivo

//****************** MARCOS GERONIMO ************************

// Programa que calcula o valor Fatorial de um número fornecido

//Inclusão de bibliotecas

#include <stdio.h>

int fat (n) //Função recursiva

{

//Função que