Qual e a diferenca entre iterativa e recursiva funcoes?

Obrigado Claudio!

Resposta

Funções recursivas: é uma função que parcialmente definido por si só e consiste em alguns simples caso com uma resposta conhecida. Exemplo: número de Fibonacci seqüência, função fatorial, classificação rápida e muito mais.

Algumas das funções/algoritmos podem ser representadas de forma iterativa e alguns não podem.

Funções iterativas: loop baseiam imperativa repetição de um processo (em contraste com a recursão que tem mais de abordagem declarativa).

Agora vamos pensar sobre quando é uma boa idéia usar recursão e porquê. Em muitos casos, haverá uma escolha: muitos métodos podem ser gravados, com ou sem o uso de recursão.

P: a versão recursiva geralmente é mais rápido?

R: não - é geralmente mais lento (devido a sobrecarga de manter a pilha)

Q: será que a versão recursiva geralmente usam menos memória?

R: não - geralmente usa mais memória (para a pilha).

P: então por que usar recursão?

R: às vezes é muito mais simples de escrever a versão recursiva (mas vamos precisar esperar até que nós discutimos árvores para ver bons exemplos...)

Aqui estão alguns exemplos onde a recursão torna as coisas um pouco mais claras, embora no segundo caso, o problema de eficiência o torna uma escolha ruim.

Fatorial

Fatorial pode ser definido como segue:

fatorial de 0 é 1

fatorial de N (para N > 0) é N N-1 ... 3 2 1

ou:

fatorial de 0 é 1

fatorial de N (para N > 0) é N fatorial (N-1)

(Note-se que fatorial está definida para números negativos).

A primeira definição leva a uma versão iterativa do fatorial:

int fatorial (int N) {

se (N = = 0) retornar 1;

int tmp = N;

para (int k = N-1; k > = 1; k-) tmp = tmp k;

retorno (tmp);

}

A segunda definição leva a uma versão recursiva:

int fatorial (int N) {

se (N = = 0) retornar 1;

mais retorno (Nfactorial(N-1));

}

A versão recursiva é

um pouco mais curto,

um pouco mais claro (mais perto da definição matemática),

um pouco mais lento

Porque a versão recursiva faz com que um registro de ativação para ser enviado para a pilha de execução para cada chamada, também é mais limitada do que a versão iterativa (não, com um erro de "estouro de pilha"), para valores grandes de N.

Espero que isso ajude

Cheers:)

Inscrever - receber um email se alguém adiciona novas respostas/comentários

Comentários

Matilde na 3 Ago 2023

A diferença entre funções iterativas e recursivas está na forma como elas são executadas. Funções iterativas usam loops, enquanto funções recursivas chamam a si mesmas para resolver um problema. Funções iterativas geralmente ocupam menos memória, pois não armazenam chamadas sucessivas na pilha de execução, enquanto funções recursivas podem ocupar mais memória devido à pilha de execução crescente. Além disso, funções iterativas tendem a ser mais eficientes em termos de desempenho, mas as funções recursivas podem ser mais fáceis de entender e desenvolver em certos casos. Portanto, a escolha entre usar uma função iterativa ou recursiva dependerá do problema específico que você está tentando resolver e das necessidades de desempenho do seu programa. Espero que isso esclareça a diferença entre os dois tipos de funções! Se tiver mais alguma dúvida, estou à disposição para ajudar.

Responder

O seu comentário

Acho que a resposta não está correta ou que você gostaria de acrescentar mais
alguma informação? Envie o seu comentário abaixo..