36-递归与迭代

36-1 用递归和迭代解决问题

1、求n的阶乘

公式：

n!=1×2×3×...×(n-1)×n。用递归方式定义：0!=1，n!=(n-1)!×n。

代码1：

我们先回忆一下之前用循环怎么实现的吧

非递归，也可称迭代：

int main()
{int n = 0;scanf("%d", &n);int i = 1;int ret = 1;for (i = 1; i <= n; i++){ret = i * ret;}printf("%d\n", ret);return 0;
}

运行结果：

代码2：

递归

int fac(num)
{if (num > 1){return num * fac(num - 1);}else{return 1;}
}
int main()
{int n = 0;scanf("%d", &n);int ret = fac(n);printf("%d\n", ret);return 0;
}

运行结果：

有些时候，并不适合用递归

2、求第n个斐波那契数

斐波那契数列：在数学上，斐波那契数列可以通过递推的方式定义，从第三项开始，每一项都等于前两项之和。具体的递推公式为F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2)，其中n≥2且n属于自然数集。

代码1：递归方法

int F(n)
{int ret = 0;if (n >= 2){return F(n - 1) + F(n - 2);}else if (0 == n){return 0;}else{return 1;}
}
int main()
{int n = 0;scanf("%d", &n);int ret = F(n);printf("%d\n", ret);return 0;
}

运行结果：

但是，这里会有大量重复的计算！严重浪费时间

我们可以进行一个测试：

int count = 0;  //计数器
int F(n)
{int ret = 0;if (n == 3){count++;  //计数，一共算了多少次第三个斐波那契数}if (n >= 2){return F(n - 1) + F(n - 2);}else if (0 == n){return 0;}else{return 1;}
}
int main()
{int n = 0;scanf("%d", &n);int ret = F(n);printf("%d\n", ret);printf("count=%d\n", count);return 0;
}

运行结果：

竟然算了将近4万次！！！

效率太低了，用递归太不合适啦！我们试试迭代吧~~~

代码2：迭代

①for循环

int Fib(n)
{if (n >= 2){int sum = 0;int i = 0;int n1 = 1;  //第一个数int n2 = 1;  //第二个数for (i = 0; i < n-2; i++)  //直接从第3个算起{sum = n1 + n2;n1 = n2;n2 = sum;}return sum;}else if(0==n){return 0;}else{return 1;}
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);
}

②while循环（该代码默认n>=1）

int Fib(n)
{int n1 = 1;int n2 = 1;int n3 = 1;while (n >= 3){n3 = n1 + n2;n1 = n2;n2 = n3;n--;}return n3;
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret);
}

再使用这两个代码进行测试，你会发现代码运行速度明显比递归的速度快

注意：如果用特别大的数测试，可能会得到负值，这是因为溢出了，关于溢出的问题这里不进行展开