CODEWITHSUNDEEP
c
Bee Lau
Bee Lau

Reputation: 21

Fibonacci One Recursive Call

I wish to transform the basic Fibonacci function: 

int find_fib(int fib_to) {

    if (fib_to == 0) {
        return 0;

    }
    else if (fib_to == 1) {
        return 1;

    }
    else {
        return (find_fib(fib_to - 1) + find_fib(fib_to - 2));       
    }   
}

into one that would use only ONE recursive call. I searched up many sites that tells me to store the value found by (find_fib(fib_to - 1) + find_fib(fib_to - 2)) into some array and then make use of the array, but doing so requires 2 recursive calls.

Any tips on how to solve the problem?

Upvotes: 2

Views: 4363

Answers (2)

Santosh ravi
Santosh ravi

Reputation: 11

you could do the following:

def fibonacci(n):
cache = {0: 1, 1: 1}

if n in cache:
    return cache[n]
else:
    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)
return cache[n]

By using a dictionary to store the key/values of the output of a fibonacci number, you avoid duplicate recursions and also it will return the values of the fib number.

More on this topic and better optimization can be found in this page.

https://realpython.com/fibonacci-sequence-python/

Upvotes: 1

Stefan Falk
Stefan Falk

Reputation: 25517

You mean something like that?

#include <stdio.h>

int fibonacci(int number_iterations, int number_a, int number_b) 
{
    if(number_iterations <= 0) {
        printf("error: 'number_iterations' must be >= 1\n");
        return -1;
    }

    if(number_iterations == 1) {
        printf("%d ", number_a + number_b);
        return number_a + number_b;
    }

    printf("%d ", number_a + number_b);
    return fibonacci(number_iterations - 1, number_b, number_a + number_b);
}

int main()
{
    int a = 1; 
    int b = 1;
    int number_of_iterations = 0;

    printf("Enter a number >= 1: ");

    int err = scanf("%d", &number_of_iterations);
    int final_result = -1;

    if (err != EOF) {
        printf("fibonacci: %d %d ", a, b);
        final_result = fibonacci(number_of_iterations, a, b);
    }

    printf("Final fibonacci: %d\n", final_result);

    return 0;
}

would return you:

Enter a number >= 1: 10
fibonacci: 1 1 2 3 5 8 13 21 34 55 89 144
Final fibonacci: 144

Upvotes: 3

Related Questions