C 递归基础讲解----对运行时堆栈中变量分析，掌握递归的基本知识

递归

基础讲解----对运行时堆栈中变量分析，掌握递归的基本知识

C通过运行是对栈支持递归函数的实现。递归函数就是直接或间接调用自己的函数。
许多资料中使用一下两个例子来讲解递归的调用：
阶乘------但并未体现出递归的任何优势
菲波那契数列-----效率是非常低的

下面我们来看一个简单的例子：
将一个整数从二进制形式转换为可打印的字符形式，如，给出一个值为4267，那么我们需要
一次产生字符‘4’‘2’‘6’‘9’。
其实在printf中使用%d格式输出时就会执行类似的程序。

这里我们采用将这个值反复除以10并打印各余数，并且利用
‘0’+0 = ‘0’
‘0’+1 = ‘1’
‘0’+4 = ‘4’
.
.
.
直接使用这种方法存在一个严重的问题就是产生的字符与输入的字符顺序是向反得。
我们在这里使用递归的方法，来实现顺序打印的效果，在这要注意思考代码的实现
毕竟递归不想我们正常的程序一样，为了更好的理解递归大家在思考方式上要有一个
转变。好了下面让我们来看看具体程序的实现。

 /*
 *接受一个整形值（无符号），并将他转换为字符并打印（前导零被删除）
 */
 #include
 
 void
 binary_to_ascii(unsigned int value)
 {
  unsigned int quotient;
  quotient = value / 10 ;
  if(quotient != 0)
   binary_to_ascii(quotient);
  putchar(value % 10 + '0');
 }
 
 在使用递归时我们必须设定一个循环终止条件
 并且在每次循环中必须越来越接近这种限制条件

下面我们来看看改程序具体的实现
1、将参数除以10.
2、如果quotient的值非零调用函数自身打印quotient当前的各位数字
3、接着，最后打印步骤1中除法运算的余数

相信到现在你还是不太明白，没关系让我们来深入的看一下整个递归过程是如何实现的！
首先，让我们来看一下函数中所声明的变量是如何存储的，我们在前面曾讲过递归调用是基于
运行时堆栈之上的，当函数被调用时他的变量的空间是创建与运行时堆栈上的。也就是说
以前调用的变量仍保留在堆栈上，但他们被新函数的变量所掩盖，因此是不能被访问的。
在堆栈中当前可以访问的变量位于栈顶，其他变量是暂时不能够访问的。
好了有了这些基础知识我们可以来一步一步的看一下执行过程中变量的分布情况

这里我们来举一个简单的数：我们以269来看一下实行过程

 1、当函数刚开始执行时变量在堆栈中的分布情况
        
        -------------------------------------
       *   value:269      quotient:       *
       *************************************
         else function's variables
         
  执行第一步除法之后：
       -------------------------------------
       *   value:269      quotient:26      *
       *************************************
            else function's variables
       -------------------------------------
       
2、由于quotient不为零，所以会对该函数执行递归调用，在该函数第二次被调用
  时的堆栈分布情况：
 
         -------------------------------------
         *   value：26      quotient：
         *************************************
         *   value:269      quotient:26      *
         *************************************
            else function's variables
         -------------------------------------
   （注意****线下面的变量时不可访问的，直到当前这次递归调用返回，紧邻的下面的变量才可用）
   执行除法之后：
        -------------------------------------
         *   value：26      quotient：2
         *************************************
         *   value:269      quotient:26      *
         *************************************
            else function's variables
         -------------------------------------
       
            -------------------------------------
            *   value：2      quotient：
            *************************************
           *   value：26      quotient：2
           *************************************
           *   value:269      quotient:26      *
          *************************************
            else function's variables
         -------------------------------------
       
         -------------------------------------
            *   value：2      quotient：0
            *************************************
           *   value：26      quotient：2
          *************************************
          *   value:269      quotient:26      *
          *************************************
            else function's variables
       -------------------------------------
       
3、 到这时quotient的变量值为0，递归函数便不再调用自身，开始打印输出，然后函数返回
  并开始销毁堆栈上的变量值，使下一层变量生效
  每次调用putchar得到变量value的最后一个数字，方法是对value进行模10取余的运算，其结果
  是一个0到9之间的整数。利用他与字符常量‘0’相加 便可以得到这个数字对应的ASII字符
  然后将他们打印出来！
       -------------------------------------
       *   value：2      quotient：0                 //输出：‘2’
        *************************************
         *   value：26      quotient：2
        *************************************
       *   value:269      quotient:26      *
       *************************************
            else function's variables
       -------------------------------------
       
4、接着函数返回，他的变量从堆栈中销毁。接着递归函数的前一次调用从新继续执行，他所使用的
   是自己的变量他们现在位于堆栈的顶部（可用，26对10取余的到6）：
         -------------------------------------
         *   value：26      quotient：2             //输出：6
         *************************************
          *   value:269      quotient:26      *
         *************************************
            else function's variables
         -------------------------------------
       
5、一次类推本次函数返回时，激活下一层的变量

      -------------------------------------
       *   value:269      quotient:26      *//输出9
       *************************************
            else function's variables
       -------------------------------------
       
 到目前为止可以看到已经输出了‘269’！所有递归调用结束，返回到else function调用的地方
 
 经过我们对运行时堆栈中变量分配机制的讲解，希望大家对对递归调用能够有一个初步的认识！
 下次我们还会继续讲解有关递归调用的知识！
 
 大家也许会问递归和迭代有什么不同呢？
 好了，为了让大家对递归和迭代有一个清楚的认识下次我们就讲解有关递归和迭代的有关知识！
 感谢大家的支持！
 谢谢！
 另外：大家如有什么不明白的可以和我联系：