Cursando

Sumário:

1-Recursividade

1.1 Conceitos……………………………………………..…………pág 2

1.2 Condição de parada…………………………………..………...pág 2

1.3 Execução……………………………………….…………..……pág 2

1.4 Complexibilidade………………………………...…………..…pág 3

1.5 Análise do uso da recursividade na Fibonacci……………...…pág 4

1.6 Divisão de tarefas dentro da recursividade……………………pág 5

Recursividade
1.1 Conceitos
A recusividade é fundamental em Matemática e Ciência da Computação.
Um programa recursivo é um programa que chama a si mesmo, assim como uma função recursiva é definida em termos dela mesma. Como exemplo de programa temos os números naturais, e como exemplo de função recursiva, temos as funções fatoriais. Um conceito poderoso que é muitas vezes utilizado, pra definir recursividade, é de que são conjuntos infinitos com comandos finitos
A recursividade é uma estratégia que pode ser utilizada sempre que o cálculo de uma função para o valor n, pode ser descrita a partir do cálculo desta mesma função para o termo anterior (n-1).
Exemplo – Função fatorial: n! = n * (n-1) * (n-2) * (n-3) *....* 1
(n-1)! = (n-1) * (n-2) * (n-3) *....* 1 logo: n! = n * (n-1)!
Dentro do corpo de uma função, o fato de chamar novamente a própria função pode ser dividida em dois tipo, a recursão direta, onde a função A chama a própria função A, e recursão indireta, onde, a função A chama uma função B que, por sua vez, chamar A.

1.2 Condição de parada
Nenhum programa nem função pode ser exclusivamente definido por si mesmo, se não o programa viraria um loop infinito e a função teria definição circular. Então definimos uma condição de parada para a mesma, que permite que o procedimento pare de se executar. Por exemplo F(x) > 0 onde x é decrescente. O objetivo é sempre estudar a recursividade como ferramenta prática!

1.3 Execução
Para cada chamada de uma função, recursiva ou não, os parâmetros e as variáveis locais são empilhados na pilha de execução. Internamente, quando