发布于 

函数的递归

c语言函数递归的总结与运用。

在c语言的函数部分,递归是一块比较难掌握但是又很重要的一个部分。所以就来总结总结遇到的一些问题,以帮助更好的理解与运用递归。

在开始之前,还是先来看看递归的定义。什么是递归呢?简单来讲就是程序调用自身的编程技巧。递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的但规模较小的问题来求解,递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。递归的主要思考方式在于:大事化小,小事化了

下面通过一个个地例题,我们逐渐认识递归,并总结一些东西。

1.接受一个整型值(无符号),按照顺序打印它的每一位。例如:输入1234,输出1 2 3 4.

1
2
3
4
5
6
7
8
9
#include<stdio.h>
void print(unsigned int n)
{
if(n>9)
{
print(n/10);
}
printf("%d ",n%10);
}

通过一层层分析,我们可以了解到这个函数的运行情况。和比较简单的依次输出整数的每一位那一类题不一样,这个题你并不能确定输入的是几位数,但是这个函数就能很好的解决这个问题。就像剥洋葱一样,一层一层地弄开-解决,弄开-解决…同时,我们也不难看出,函数中的选择语句非常重要,正是因为有了那个选择语句,这个递归才有尽头。否则,就是“死循环”。所以,在进行递归时,有两个必要条件:

一, 存在限制条件,当满足这个限制条件的时候。递归便不再继续。

二,每次递归调用之后越来越接近这个限制条件。

例如,在上面一个递归中,限制条件就是n<=9,如果满足这个条件,递归就结束了,每次递归调用之后(n/10),n的值会靠近9这个限制条件。

2.求斐波那契数列第n项的值

斐波那契数列指的是从第三项起,每一项等于前两项之和。因为它的数学关系很明确,所以考虑利用函数的递归来完成。

1
2
3
4
5
6
7
8
9
int Fib(int n)
{
if(n==1)
return 0;
else if(n==2)
return 1;
else
return Fib(n-2)+Fib(n-1);
}

其实类似于这种的函数递归很容易想明白,因为它具有明显的数学关系:Fib(n)=Fib(n-2)+Fib(n-1),我们只需要利用这个公式进行递归即可。类似地,求这种第n项与前一项有关系的数列的某一项时,可以考虑递归,思维难度低且代码简洁。

3.计算交错序列1-2/3+3/5-4/7+5/9-6/11+…的前N项之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
float A(int n)//函数的递归
{
if (n == 1)
return 1;
else if (n % 2 == 0)
return -2 - A(n - 1);
else
return abs(A(n - 1)) + 2;
}
int main()
{
int n = 0;
scanf("%d", &n);
double sum = 0;
int i = 0;
for (i = 1; i <= n; i++)
{
sum = sum+ (i / A(i));
}
printf("%.3f", sum);
return 0;
}

这个题我们容易发现这个数列是有规律的。它的分子和分母分别成等差数列,但是每一项的正负是交替的。这个时候我们想,如果它的每一项都是正值,那也太舒服了,直接利用递归就可以求出每一项的值。but,所以我们它的正负号是交替的,偶数项是负的,奇数项是正的,所以我们只需要在偶数项加一个负号即可。如果只考虑到这,那肯定就错了。因为这是递归,在计算奇数项的值时肯定会利用偶数项的值计算,如果我们只是给偶数项加一个负号,那么奇数项的值就出错了。这个时候我们考虑价格绝对值,把奇数项递归时的值变成正值。其实,对于我来说这个地方还是挺难想的,一不小心进去就出不来了(想不明白了)。。。。细品,品。。。

4.求阶乘

以一个简单的问题收尾,因为这篇文章实在是拖太久了()。。。

1
2
3
4
5
6
7
int Mul(int n)
{
if(n==1)
return 1;
else
return n*Mul(n-1);
}

万变不离其宗,这个问题其实和斐波那契数列那个问题一样,都是两项之间有明确的数学关系。n!=n*【(n-1!)】,只要能找到这个关系,这类问题就可以很轻松的解决。

函数的递归其实还是比较费脑筋的,尤其是遇到一些问题你不知道怎么去构造递归,就很麻烦。持续总结一些问题,积累积累经验。常更新(划掉)


本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。

本站由 @Miracle 创建,使用 Stellar 作为主题。