黑马程序员技术交流社区

标题: 关于函数递归的一些理解 [打印本页]

---

作者: Pythoner    时间: 2015-8-6 23:41
标题: 关于函数递归的一些理解
        首先，楼主是黑马ios双元基础班5期的学员，这两天学到C语言的函数，想到以前学习C语言遇到一个难题----递归，于是顺便查了查资料，加深一下对函数递归的理解和应用。
        先看一个例子：

• #include <stdio.h>
• void fun(int i)
• {
•     if(i > 0)
•     {
•         fun(i / 2);
•     }
•     printf("%d\n", i);
• }
• int main()
• {
•     fun(10);
•     return 0;
• }
  
  

这个例子的输出结果为
0
1
2
5
10

有些人认为应该输出0，因为当i小于或等于0时递归调用结束，然后执行printf函数打印i的值。

    这种想法是错误的，典型的没有理解递归的含义。printf("%d\n", i);语句是fun函数的一部分，肯定执行一次fun函数，就要打印一行，怎么可能只打印一次呢？所以要搞清楚怎么展开递归函数。展开过程如下：

• void fun(int i)
• {
•     if(i > 0)
•     {
•         //fun(i/2);
•         if(i/2 > 0)
•         {
•             if (i/4 > 0)
•             {
•                 ...
•             }
•             printf("%d\n", i/4);
•         }
•         printf("%d\n", i/2);
•     }
•     printf("%d\n", i);
• }
  
  

这样应该就很容易理解了。我们再来看一个应用：不使用任何变量编写strlen函数

    strlen函数的作用是传入一个字符串，返回这个字符串的长度。利用递归编写 int my_strlen(char *strDest);

    这个解决方法有很多种，比如嵌套汇编，不过此处只讨论递归。代码如下：

• int my_strlen(const char* strDest)
• {
•     assert(NULL != strDest);   //第一步：用assert宏做入口检验。
•     if('\0' == *strDest)       //第二部：确定参数传递过来的地址上的内存存储的是否为'\0'。如果是，表明这是一个空字符串，或者是字符串的结束标志。
•     {
•         return 0;
•     }
•     else
•     {
•         return (1 + my_strlen(++strDest)); //第三步：如果参数传递过来的地址上的内存不为'\0'，则说明这个地址上的内存上存储的是一个字符。既然这个地址上存储了一个字符，那就计数为1，然后将地址加1个char类型元素的大小，然后再调用函数本身，如此循环，当地址加到字符串的结束标志'\0'时，递归停止。
•     }
• }
  
  

同样，还有更加简洁的代码：

• • int my_strlen(const char* strDest)
  • {
  •    
  •     return *strDest ? 1 + my_strlen(strDest + 1) : 0;
  •    
  • }
    
    
  这里很巧妙的利用了问号表达式，不过没有做参数入口校验，同时用*strDest来代替('\0' == *strDest)也不是很好，所以这种写法虽然简洁，但是不符合编码规范，可以改写成：
  • int my_strlen(const char* strDest)
  • {
  •     assert(NULL != strDest);
  •     return ('\0' != *strDest) ? 1 + my_strlen(strDest + 1) : 0;
  •    
  • }
    
    
  每调用一遍my_strlen函数，其实只判断了一个字节上的内容，但是如果传入的字符串很长的话，就需要连续多次函数调用，而函数调用的开销比循环来说要大得多，所以，递归的效率很低，递归的深度太大甚至可能出现错误，比如栈溢出。所以，平时写代码，不到万不得已，尽量不要用递归。用的时候注意递归的层次不要太深，防止出现栈溢出的错误，同时递归的停止条件一定要正确，否则，可能会变成死递归。
  
  

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2