C language code for finding the Fibonacci number

problem

Write code that returns the __nth Fibonacci number. __

--If the argument is less than 0, -1 is returned. --Implement recursively. --The function should take the following form - int fibo(int index);

Self-made code

int fibo(int index)
{
    if(index < 0) return -1;
    if(index == 0) return 0;
    if(index == 1) return 1;
    if(index > 46) return 0;
    return fibo(index - 1) + fibo(index -2);
}

Mr. A's code

int fibo(int index)
{
    if (index < 0)
        return (-1);
    if (index == 0)
        return (0);
    if (index == 1)
        return (1);
    if (index > 46)
        return (0);
    return fibo(index - 1) + fibo(index - 2);
}

test case

#include <stdio.h>

int main()
{
    int i = 1;
    int x = 0;
    for(x = -3; x < 50; x++){
        i = fibo(x);
        printf("%Fibonacci number of d:%d\n",x,i);
    }
    return (0);
}

Impressions

--At first, the code did not consider the maximum value of int type. You should always be aware of the maximum value of int. --I wanted to use memoized recursion, but I couldn't use it because the shape of the function was fixed. ――I was surprised because the speed was so different when I tried to implement it with memoization recursion.

--Things to consider in the test case --Behavior for negative numbers --Behavior when 0,1 --46 Behavior around

Bonus code to find the Fibonacci number using memoization recursion

int fibo(int index, int a[])
{
    if(index < 0) return -1;
    if(index == 0) return 0;
    if(index == 1) return 1;
    if(index > 46) return 0;
    if(a[index] != 0) return a[index];
    return a[index] = fibo(index - 1, a) + fibo(index -2, a);
}

Postscript

2020/04/14 I came back because I solved a similar problem for the first time in a month. I tried to write it, but it doesn't work. In the memoization recursion part, static was not added. Last time, I didn't understand it properly. By adding static, the value is retained in the static area and the calculation result is inherited. I didn't understand here. Review is important.

//Important here!
static int A[46 + 1] = {0, 1};
#include <stdio.h>

int fibo(int n)
{
    static int A[46 + 1] = {0, 1};

    if (n < 0)
        return -1;
    if (n > 46)
        return 0;
    if (n >= 2 && A[n] == 0)
        A[n] = fibo(n - 1) + fibo(n - 2);
    return A[n];
}

int main(void)
{
    int N;

    scanf("%d", &N);

    printf("%d\n", fibo(N));
    return 0;
}

Recommended Posts