递归:函数自己调用自己
递:递推 归:回归
思考方式: 把大问题转换为一个规模较小的原问题求解,直到子问题无法拆分
特点:使用少量的代码就可以完成复杂的任务
两个必要条件:1.递归要存在限制条件,当满足这个限制条件时,递归就会停止
2.每次递归调用时会越来越接近这个限制条件
举例1:求n的阶乘(0的阶乘为1;正整数n的阶乘为n!)
阶乘公式:n!=n*(n-1)!
#include <stdio.h>
int Fact(int n)
{
if (n == 0)
return 1;
else
return n * Fact(n - 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fact(n);
printf("%d\n", ret);
return 0;
}
其中 条件1:n >0;n = 0 停下
条件2:每一步过程都在不断逼近停下条件
举例2:顺序打印一个整数的每一位
输入:3241 输出:3 2 4 1
#include <stdio.h>
void Print(int n)
{
if (n > 9)
{
Print(n / 10);
printf("%d", n % 10);
}
else
{
printf("%d", n % 10);
}
}
int main()
{
int n = 0;
scanf("%d", &n);
Print(n);
return 0;
}
这张图表示程序流程:先是一步步递推,然后在回归printf,按顺序逐个打印数字
总的来说递归就是先把问题一步步简化,然后回到每一步过程上进行解答,最终将问题解决
迭代
然而递归函数每一次调用都需要在本次函数调用的内存栈区申请一块内存空间来保存函数调用期间的个中局部变量,这片空间成为运行时堆栈,或者函数栈帧。
如果递归函数不返回,函数对应的栈帧空间就会被一直占用,直到递归函数不再继续时,才会逐层释放栈帧空间。
所以递归函数层次不宜太深,太深会浪费太多栈帧空间,也可能会引起栈溢出(stack overflow)的问题。
此时就需要用其他方法来解决问题,比如迭代(通常就是循环的方式)
如 例1:
#include<stdio.h>
int Fact(int n)
{
int i = 0;
int ret = 1;
for (i = 1; i < n + 1; i++)
{
ret *= i;
}
return ret;
}
int main()
{
int n = 0;
scanf("%d", &n);
int ret = Fact(n);
printf("%d", ret);
return 0;
}
这样也可以完成任务,并且效率比迭代更高
当很多问题递归和迭代都可以解决时,递归的方式比非递归的更加清晰,但是迭代往往比递归效率更高。 然而当一个问题非常复杂,难以使用迭代的方式完成,递归便以实现的简洁性补偿它运行时的开销。