函数递归与迭代

递归的简介

1.1 递归的思想：

把⼀个大型复杂问题层层转化为⼀个与原问题相似，但规模较小的子问题来求解；直到⼦问题不能再 被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。 递归中的递就是递推的意思，归就是回归的意思，接下来慢慢来体会。

1.2 递归的限制条件 递归在书写的时候，有2个必要条件： • 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。 • 每次递归调⽤之后越来越接近这个限制条件。

阶乘

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;
}

递归在阶乘当中的应用:当计算阶乘时,例如 5的阶乘可以转化为5✖4的阶乘; 4的阶乘看作是4✖3的阶乘; 以此类推,而这个过程是"递"的过程,当遇到1的时候,也就是阶乘的限制条件,开始’归’的过程,下图可以形象的展示出来:

在这里插入图片描述

有递也有归.

顺序打印⼀个整数的每⼀位

void Print(int n)
{
 if(n>9)
 {
 Print(n/10);
 }
 printf("%d ", n%10);
}

int main()
{
 int m = 0;
 scanf("%d", &m);
 Print(m);
 return 0;
}

• 获得数字每一位数的方式之前都有涉及过,也就是通过除法和取余实现.%和/ 而之前实现的是逆序打印,在这里将会实现顺序打印.
• Print作为顺序打印数字每一位的函数;当我们在打印例如1234这个四位数时, 可以看作是打印123的每一位,外加打印一个4; 打印123的每一位可以看作打印12的每一位外加一个3; 顺序打印打印交给Print来实现; 以此类推,将1234的每一位打印出来; 下图展示:

在这里插入图片描述

求第n个斐波那契数

什么是斐波那契数列

斐波那契数列是一个著名的数学序列，其中每个数字都是前两个数字的和，从1和1开始。这个序列的前几个数字是1, 1, 2, 3, 5, 8, 13, 21等。斐波那契数列的求和问题涉及到计算序列中前n个数字的总和。 第n项斐波那契数可以通过第n-1项和n-2项斐波那契数相加而得到,在这里也能看出函数递归的意思来;

int count = 0;
int Fib(int n)
{
 if(n == 3)
 count++;//统计第3个斐波那契数被计算的次数 
 if(n<=2)
 return 1;
 else
 return Fib(n-1)+Fib(n-2);
}
int main()
{
 int n = 0;
 scanf("%d", &n);
 int ret = Fib(n);
 printf("%d\n", ret); 
 printf("\ncount = %d\n", count);
 return 0;
}

当n>=3时,走函数;而1和2 便是递归的限制条件,返回为1的值. 在这里可以尝试当输入n为50时,程序运行速度是比较慢的,这是因为,每一个斐波那契数都要去调用两次斐波那契函数,而在递的过程中,每次都会占用一块栈区,当递归层次过深的话,就会导致效率下降等一系列问题.

递归的缺陷:

在C语⾔中每⼀次函数调⽤，都需要为本次函数调⽤在内存的栈区，申请⼀块内存空间来保存函数调 ⽤期间的各种局部变量的值，这块空间被称为运⾏时堆栈，或者函数栈帧。 函数不返回，函数对应的栈帧空间就⼀直占⽤，所以如果函数调⽤中存在递归调⽤的话，每⼀次递归 函数调⽤都会开辟属于⾃⼰的栈帧空间，直到函数递归不再继续，开始回归，才逐层释放栈帧空间。 所以如果采⽤函数递归的⽅式完成代码，递归层次太深，就会浪费太多的栈帧空间，也可能引起栈溢出（stack overflow）的问题。