Funcão recursiva linear Fibonacci

[TiagoGR]

Eu preciso criar uma função em C que, através da recursividade, calcule um determinado número da sequência de Fibonacci. No entanto, essa função precisa ser linear, ou seja, a função só pode chamar a si mesma uma vez dentro do código.

O código que eu fiz, e o único que eu consegui criar que usasse a recursividade para calcular o Fibonacci, não é linear. (Como exemplo de código linear, coloquei uma função que calcula um fatorial de forma linear).

Se alguém tiver alguma ideia de como calcular o Fibonacci linearmente, eu agradeceria muito. Estou batendo cabeça com esta questão faz tempo e não consegui nada =/

int fibonacci (int n)
{
         if (n == 1 || n == 0)
                return n;
         else
                return fibonacci(n-1) + fibonacci(n-2);
}

int fatorial (int n)
{
         if (n==1 || n==0)
                return 1;
         else
                return n*fatorial(n-1);
}

[Visitante]

Pode usar um for para calcular as somas. Como um numero da sequencia de fibonacci é a soma dos dois anteriores e tudo começa com 1 e 1:

int i=1, j=1, cont;
for(cont=1;cont<=n-2;l++)
    {
        p=i+j;       /* soma dos numeros anteriores */
        i=j;
        j=p;
    }

E p retorna o valor da sequencia fibonacci.

[nelsonspbr]

Acho que o que o Tiago quis dizer com "calcular Fibonacci linearmente" significa usar recursividade (e não um método iterativo) porém chamando a função apenas uma vez, e não duas (como o que foi feito no código que ele passou).

[Hugo fob]

Preciso criar um código fibonacci é numeros primos com recursividade em c, mas dentro do swich case. Como faço isso.

[Ansi C]

Foi apresentado modificadores de variáveis? Eles dão características especiais para modifica o comportamento de um tipo de variável. Lembre-se das variáveis estáticas modificadas pela palavra chave static, ela força persistir em todas as chamadas da função a mesma variável.

 

Use ao menos duas static para concluir a complexidade  O(n).

[arfneto]

Em 11/10/2010 às 21:00, TiagoGR disse:

No entanto, essa função precisa ser linear, ou seja, a função só pode chamar a si mesma uma vez dentro do código

 

Não conhecia essa definição de "recursão linear".

 

Em 30/08/2020 às 22:43, Hugo fob disse:

Preciso criar um código fibonacci é numeros primos com recursividade em c, mas dentro do swich case. Como faço isso.

 

E o que seria isso? Em particular "um código fibonacci é numeros primos com recursividade em c, mas dentro do swich case"? Não consegui entender. 

 

Esse era um tópico de DEZ anos atrás. Porque ressuscitou isso ao invés de postar um tópico novo e algum código e uma descrição mais precisa do que quer fazer? 

 

Curiosamente até hoje só se vê essa solução do autor mesmo:
 

int fibonacci (int n)
{
         if (n == 1 || n == 0)
                return n;
         else
                return fibonacci(n-1) + fibonacci(n-2);
}

Veja a solução em https://www.programmingsimplified.com/c-program-generate-fibonacci-series

int f(int n)
{
  if (n == 0 || n == 1)
    return n;
  else
    return (f(n-1) + f(n-2));
}

Em 2020, agosto, 31.  

 

A mesma que está em https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ hoje. 

E em https://www.tutorialspoint.com/data_structures_algorithms/fibonacci_recursive_program_in_c.htm

E algumas em https://stackoverflow.com/ como essa https://stackoverflow.com/questions/42557573/recursive-fibonacci-in-c-plain-simple mas com problemas.

 

Estranho até porque parece que não é uma solução muito boa. A cada recursão chamar duas vezes a própria função cresce muito rápido em complexidade. 

 

Não vi nenhuma usando uma simples recursão, e não sei como chegaram a uma solução usando duas chamadas. Mas achei interessante.

 

4 horas atrás, Mauro Britivaldo disse:

Foi apresentado modificadores de variáveis? Eles dão características especiais para modifica o comportamento de um tipo de variável. Lembre-se das variáveis estáticas modificadas pela palavra chave static, ela força persistir em todas as chamadas da função a mesma variável.

 

Use ao menos duas static para concluir a complexidade  O(n)

 

É como @Mauro Britivaldo disse. Como o código recursivo é reentrante há duas maneiras tradicionais de passar contexto:

• passando um argumento, tipo uma bola de neve
• usando variáveis estáticas e algum tipo de inicialização e reinicialização pra poder chamar de novo durante uma mesma execução do programa

Nesse caso aqui usar variáveis estáticas é mais simples. Mas acho que precisa de 4 delas. E transformar o loop da programação tradicional em recursão. E ter um cuidado extra com o overflow. O maior que cabe em um int acho que é o 93:

			fib(93) = 7540113804746346429

Acima disso já precisa arrumar outra representação...