目录
- C递归函数:
- 十进制转二进制
- 十进制转换十六进制
- 字符串反转
- 斐波那契数列
- 自然数求和
- 总结
C递归函数:
经过前面的介绍递归函数(一):介绍,我们对递归函数有了初步的认识,知道了先序递归和后序递归。接下来我们看几个递归函数的常见应用。
十进制转二进制
我们取一个十进制数13,其二进制为1101。
尝试性代码:
#include <stdio.h>
void bin(int n)
{
int i = n % 2; //十进制转换二进制就是不断对2取余数
printf("%d\n",i);
if(n>0) { //递归函数必须有个条件,否则将会一直循环
bin(n / 2); //递归调用
}
}
int main()
{
int i=13;
bin(i);
return 0;
}
运行结果如下
发现问题:
- 13的二进制为1101,显示的是10110,顺序和正确的相反
- 前面多了一个0
对前面代码进行改造
#include <stdio.h>
void bin(int n)
{
int i = n % 2; //十进制转换二进制就是不断对2取余数
if(n>0)//递归函数必须有个条件,否则将会一直循环
{
bin(n / 2); //递归调用
printf("%d",i);//把printf放在if里面,并且换成后序递归,去掉\n
}
}
int main()
{
int i=13;
bin(i);
return 0;
}
运行结果:
成功!
我们通过后序递归函数,完成十进制转换二进制
十进制转换十六进制
根据十进制转二进制,我们进行以下尝试:
#include <stdio.h>
void hex(int n)
{
int i = n % 16; //把对2取余换成对16取余
if(n>0)//递归函数必须有个条件,否则将会一直循环
{
hex(n / 16); //递归调用
printf("%d",i);
}
}
int main()
{
int i=15;
hex(i);
return 0;
}
运行结果:
15这个数是没问题的,但是在十六进制里面应该是字母F
简单无脑的解决办法:
#include <stdio.h>
char hex1(int n) //因为字母ABC等不是数字,所以返回字符串char
{
switch(n)
{
case 0:
return '0';
case 1:
return '1';
case 2:
return '2';
case 3:
return '3';
case 4:
return '4';
case 5:
return '5';
case 6:
return '6';
case 7:
return '7';
case 8:
return '8';
case 9:
return '9';
case 10:
return 'A';
case 11:
return 'B';
case 12:
return 'C';
case 13:
return 'D';
case 14:
return 'E';
case 15:
return 'F';
default:
return '0';
}
}
void hex(int n)
{
int i = n % 16;
if(n>0)
{
hex(n / 16);
printf("%c",hex1(i));//返回值变为char,所以改为%c
}
}
int main()
{
int i=2348;//值改大一点
hex(i);
return 0;
}
运行结果:
看下计算器:
成功~~
字符串反转
我们来看一个字符串反转的例子:字符串’123456789’变为’987654321’
#include <stdio.h>
#include <string.h>
//反转字符串
char *reverse(char *str) {
int len = strlen(str); //先计算字符串长度
if (len > 1) { //对递归设立条件
char ctemp = str[0]; //把第一个字符暂存到ctemp
str[0] = str[len - 1]; //把第一个字符换成最后一个字符
str[len - 1] = '\0'; //最后一个字符在下次递归时不再处理
reverse(str + 1); //递归调用
str[len - 1] = ctemp;
}
return str;
}
int main() {
char str[20] = "123456789";
printf("%s\n", reverse(str));
return 0;
}
运行结果:
我们来仔细分析下这个处理过程:
每次调用函数,都会把字符串的第 0 个字符保存到 ctemp 变量,并把最后一个字符填充到第 0 个字符的位置,同时用’\0’来填充最后一个字符的位置。
读者要注意调用 reverse() 的实参为str+1,这会导致形参 str 的指向发生改变,每次递归调用时 str 都会向后移动一个字符的位置。
通过以上的两点可以得出一个结论:每次递归调用都会处理一个新的子串,这个新的子串是在原来字符串的基础上**“掐头去尾”**形成的。
斐波那契数列
斐波那契数列是这样的:0,1,1,2,3,5,8,13…
这个数列第0项是0,第1项是1。
从第二项开始,每一项都等于前面两项之和。
我们尝试用递归来生成这样一个数列,比如,这个数列的第10个数是多少?
#include <stdio.h>
int fib(int n)
{
if(n == 0){ //因为第0项前面没有两项
return 0;
}
if(n == 1){ //因为第1项前面只有0一项,不能组成两项和
return 1;
}
else
{
return fib(n-1)+fib(n-2); //递归调用
}
}
int main() {
printf("%d\n",fib(6));
return 0;
}
运行结果:
第6项是8,完全正确!
自然数求和
这个例子比较简单:
#include <stdio.h>
int sum(int n)
{
if(n>0)
{
return sum(n-1)+n;//调用递归
}
}
int main() {
printf("%d\n",sum(5));
return 0;
}
运行结果:5+4+3+2+1=15
总结
- 利用递归函数可以解决很多前后有明确关系的问题
- 利用前序和后序改变输出顺序
- 执行递归函数将反复调用其自身,每调用一次就进入新的一层,当最内层的函数执行完毕后,再一层一层地由里到外退出。
更多推荐
C递归函数(二):进制转换,字符串反转,斐波那契
发布评论