Question

A sequência [0, 1, 1, 2, 3, 5, 8, 13, 21, ...] é conhecida como sequência ou série de Fibonacci e pode ser obtida através da seguinte função, implementada em Linguagem C: int fibonacci(int num) { if(num==1) return 0; else if if(num==2) || num==3) return 1; else return fibonacci(num-1) + fibonacci(num-2); } Sobre esta função, analise as seguintes sentenças: I - Esta é uma função recursiva. II - Está é uma função iterativa. III - Quando num > 3, cada chamada causa 2 novas chamadas da função fibonacci, isto é, o número total de chamadas cresce exponencialmente. IV - Quando num = 0, não ocorre uma nova chamada da função fibonacci. Agora, assinale a alternativa que apresenta a resposta CORRETA.

Answer 1

Olá,

I) VERDADE - Para uma função ser considerada recursiva, precisa haver uma chamada de função se auto chamando, igual acontece na ultima linha deste código.

II) FALSA - Por mais que esta função tenha uma parte interativa, para ser considerada de fato interativa a função deve ser executada através de iterações e não deve conter recursividade.

III) VERDADEIRA - Números acima de 3 não entram no if com critério de parada, logo estes farão a função se auto chamar. Neste caso algorítimo tem complexidade de $O(2^{n})$, caracterizando um crescimento exponencial como afirma a questão.

IV)VERDADE - Não ocorre uma nova chamada pois não há esta condições nos critérios de parada.

Resposta: Letra D)

Espero ter ajudado.

Answer 2

Resposta:

As afirmativas I, III e IV estão corretas.

Explicação: