Recursion and non recursion are used to calculate the nth Fibonacci number respectively

First , You need to know what is Fibonacci sequence ？

Fibonacci sequence ：

Mathematically, it is defined by recursion ：F(0) = 0,F(1) = 1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2,n ∈ N * ）
0、1、1、2、3、5、8、13、21、34、……

Recursive writing

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

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

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = F(n);
	printf("%d\n", ret);
	return 0;
}

Have you found any problems with this code , That is when n When the value of is large , There will be many repeated calculations , When n=30 when ,F(0) Will be recalculated 514229 Time ; When n=40 when ,F(0) Will be recalculated 63245986 Time （ It takes six or seven seconds to calculate ）; When n=50 when , You will find that the calculation results can't come out for a long time ; Low code efficiency .

At this time, we can consider using the iterative method .

Iterative writing

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

int F(int n)
{
	int a = 0;
	int b = 1;
	int c = 0;
	if (n == 0)
	{
		return 0;
	}
	else if(n == 1)
	{
		return 1;
	}
	while (n > 1)
	{
		c = a+b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = F(n);
	printf("%d\n", ret);
	return 0;
}