Professor
678 palavras
3 páginas
UNIVALIUniversidade do Vale do Itajaí
CTTMar São José - Curso de Ciência da Computação/Engenharia de Computação
RECURSIVIDADE
A recursividade pode ser compreendida quando na prática surge a necessidade de se
•
definir alguma coisa em função dela mesma.
Em muitos problemas, uma solução recursiva é muito mais simples, natural ou intuitiva do
•
que uma solução repetitiva ou iterativa.
Uma subrotina é recursiva se definida em termos de si mesma.
•
Considere a seguinte definição de fatorial
n! =
1
, se n = 0
n (n – 1)! , se n > 0
Com esta definição, o fatorial é definido em seus próprios termos.
FUNÇÃO fatorial (INTEIRO n) : INTEIRO
fatorial ( 3 )
INÍCIO
SE n = 0 ENTÃO
3
*
fatorial ( 2 )
fatorial ← 1
SENÃO
2
*
fatorial ( 1 )
fatorial ← n * fatorial ( n – 1 )
FIM SE
1
FIM
*
fatorial ( 0 )
1
ESTRUTURA BÁSICA DE UMA FUNÇÃO/MÉTODO RECURSIVO:
SE condição de parada ENTAO
Fim
SENAO
Chamada recursiva (n -1)
FIMSE
CONSIDERAÇÕES:
• Usar recursividade quando o problema é definido recursivamente ou seus dados.
•
Garantir um fim (garantir que a função a ser chamada é menos abrangente que a atual).
•
Funções recursivas são mais lentas que funções iterativas.
•
Erros na implementação ou limitações de máquina podem levar a estouro de pilha.
UNIVALI
Universidade do Vale do Itajaí
CTTMar São José - Curso de Ciência da Computação/Engenharia de Computação
RECURSIVIDADE
Uma SUBROTINA pode ser:
• diretamente recursiva: P ativa P;
•
indiretamente recursiva: P ativa Q ativa R....ativa P
A natureza recursiva do problema não garante que um algoritmo recursivo seja a melhor solução. Todo algoritmo recursivo pode ser transformado num algoritmo não recursivo que, apesar de ser, normalmente, mais complexo e menos claro, muitas vezes é mais eficiente em relação a espaço e tempo.
PASSOS PARA DESENVOLVIMENTO DE ALGORITMOS RECURSIVOS
Passo1: