C递归函数（二）：进制转换，字符串反转，斐波那契

admin管理员组

文章数量:1794759

C递归函数（二）：进制转换，字符串反转，斐波那契

目录

• 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

总结

• 利用递归函数可以解决很多前后有明确关系的问题
• 利用前序和后序改变输出顺序
• 执行递归函数将反复调用其自身，每调用一次就进入新的一层，当最内层的函数执行完毕后，再一层一层地由里到外退出。

本文标签： 递归字符串函数