C语言：(采用PTA浙大题目) 简单递归总结（含部分答案）
那么为了这期讲解递归的博客，博主特意去把pta比较简单的浙大题目部分的递归刷了一遍，要是觉得博主讲的不错的小伙伴可以关注博主哦！博主会持续更新的????
小伙伴们可以选择性学习哦！
注：代码在算法实例，主要讲解在最后的总结。
目录↓
1.递归思想
程序调用自身的编程技巧称为递归（recursion），简单来说就是编程技巧。我们在写一个函数时，对这个函数不断的调用其本身，就是一种递归。递归在求很多数列，乃至写不同的算法时十分方便（忽略其时间复杂度和空间复杂度），递归，递归，顾名思义：递和归。
引入图 （取自：卓象程序员）
到这里其实都是废话。
2.算法实例
这里的代码皆为函数块，小伙伴们可放心使用，与主函数任意搭配????
1.使用递归函数计算1到n之和
我们一般情况下会选择在主函数中使用for循环和while循环的方式去计算。但在函数引用中我们可以使用递归：
int sum( int n )
{
if(n<0)
return 0;
if(n==1)
return 1;
else
return n+sum(n-1);
}
2. 递归求阶乘和
这里我们为了方便使用两个函数。
double fact( int n )
{
if(n==1||n==0)
return 1;
else
return (double)n*fact(n-1);
}
double factsum( int n )
{
int i;
double sum=0;
for(i=1;i<=n;i++)
{
sum+=fact(i);
}
return sum;
}
3. 递归实现指数函数
这里不需要math库的函数。
double calc_pow( double x, int n )
{
if(n == 0)
return 1;
return x * calc_pow(x, n - 1);
}
4. 递归求简单交错幂级数的部分和
所谓简单交错幂级数和其实就是：
我们要做的就是实现它，我们这里需要用到math库。
#include<math.h>
double fn( double x, int n )
{
if(n==1)
return x;
else
return pow(-1,n-1)*pow(x,n)+fn(x,n-1);
}
5. 递归计算Ackermenn函数
所谓ack函数便是：
ok，代码：
int Ack( int m, int n )
{
if(m>0&&n>0)
return Ack(m-1,Ack(m,n-1));
else if(n==0&&m>0)
return Ack(m-1,1);
else if(m==0)
return n+1;
}
6.经典算法，斐波那契
int f( int n)
{
if(n==0)
return 0;
if(n==1||n==2)
return 1;
else
return f(n-1)+f(n-2);
}
7. 十进制转二进制
这里博主会附上一张图，以便小伙伴们能够理解。
void dectobin( int n ){
//使用递归刚好会符合二进制的算法。
if(n==0)
printf("0");
else if(n==1)
printf("1");
else
{
dectobin(n/2);
printf("%d",n%2);
}
}
8. 递归实现顺序输出整数
代码：
void printdigits( int n ){
if(n<10){ //出口
printf("%d\n",n);
}else{
printdigits(n/10);
printf("%d\n",n%10);
}
}
alright，代码就提供这么多了，可以供小伙伴们参考。以上的代码思想在python中都是可以用的，小伙伴们也可以转接到python上放心食用。
3.算法总结
-
递归的输出顺序是由我们所规定的。如果我们使用return的话，他的return方式其实是这样的，举例：使用递归函数计算1到n之和
它的本质是从递归的出口（也就是递归的最深处），一步一步return过来的。而不是从我们明面上第一个return开始return的。 -
递归的出口，我们必须要特别的注意，递归就如同循环一样，循环没有停止条件就会周而复始的循环下去，递归同样如此，不同的是，它不是一圈一圈的转而是会不停的往下递归，如果大家看了看上面的代码，会发现每一个递归的算法都有它的出口，我们一般用一个if和一个return来表示，因为这已经满足大多数递归的出口条件。
-
c语言的return是非常严格的，如果你的return出现了例如（…return a value…）之类的bug说明你的return后接入的式子或者变量有问题。小伙伴们千万不要觉得编译器错误????
-
对于返回值要求为void空的函数，我们便不能用return，这时候往往是要进行输出的，否则递归便没有意义，因此小伙伴们在这时候不要迷茫，总想着用return进行递归。我们要明白递归的本质是调用自身函数，而不是不断的return。
-
如果小伙伴们学习了时空复杂度，便能看出来递归并不是一定方便的，甚至在大部分情况下的，它的时空复杂度要比用普通的循环还有大。
-
博主建议小伙伴动用手里的编译器或解释器自己动手试一试。对递归的熟练程度将会帮助到我们很多。
over 这一期就到这里的