10进制的数字转换为8进制,c++中的递归

赶上孩子暑假，给了他一本c++的入门书籍，熟悉一下基本的语法体系。因为有scratch的基础，对于基本语法的认识与接受还是挺快的，可以说有点超乎预期。因为学习用书只讲到了函数部分，手头的另几本书有点艰涩，就从NOI全国青少年信息学奥林匹克竞赛官网上找了一套视频。让他尝试从递归开始学习。

如果说程序设计是一项抽象的工作，那么递归可以说是抽象中的再抽象了，短短几句语句就实现了一个密集的运算。自己初次接受这个概念的时候也是用了非常长的时间，陪着看视频的时候顺便复习了一下，顺便做一下笔记。

课后练习

虽然孩子表示听懂了，然而还是卡在了课后练习的第一题，呵呵。眼睛虽然说明白了，还是被大脑无情的反驳了:不，你还不会。题目的要求是将一个任意的10进制整数转换为8进制数，实际程序如下：

#include<iostream>

using namespace std;

int toOctal(int n){
    if(n == 0) return 0;
    toOctal( n / 8 );
    cout << n % 8 ;
}

int main(){
    toOctal(100);
}

我们来看一下转换进制函数的构成，为了方便理解，下面的程序里我去掉了int，仅用于展示结构：

toOctal(int n){
  if(n == 0) return 0;
  toOctal( n / 8 );
  cout << n % 8 ;
}

其实递归有点儿类似循环程序的多重嵌套，但是因为一个函数仅需要定义一次，所以在递归这一句就被抽象成了一句话，如果我们使用一个确切的数字，然后将被抽象的部分填充回去，那么程序的逻辑上就更易于理解了：

toOctal( n / 8 );

现在假设参数n为100，因为100除以8等于12.5，又因为参数n的类型被指定为int，所以实际运行时，这个n会被设为12，12显然不等于0，所以程序不会返回0，而继续运行“toOctal( 1 );”：

toOctal(100){
  if(n == 0) return 0;
    toOctal(12){
      if(n == 0) return 0;
      toOctal( 1 );
      cout << 12 % 8 ;
    }
  cout << 100 % 8 ;
}

我们继续展开“toOctal( 1 );”，得亏示例数字设的小，到了这一部分1除以8，整数部分就变成零了，所以虽然系统还是会运行一次“toOctal(0);”，但因为判断语句的存在，不会再有新的函数被运行，程序终于可以返回正常的流程。

toOctal(100){
  if(n == 0) return 0;

    toOctal(12){
      if(n == 0) return 0;
        
        toOctal(1){
          if(n == 0) return 0;
          toOctal( 0 );  <---  n=0,到达边界
          cout << 1 % 8 ;
        }

      cout << 12 % 8 ;
    }

  cout << 100 % 8 ;
}

因为程序是顺序执行的，在填充完整之后，我们可以看到，cout语句的排列顺序如下：

cout << 1 % 8 ;
cout << 12 % 8 ;
cout << 100 % 8 ;

所以最终输出的结果是"144",所以这里cout语句的位置也非常的重要，如果写成下面的形式：

#include<iostream>

using namespace std;

int toOctal(int n){
    if(n == 0) return 0;
    cout << n % 8 ;
    toOctal( n / 8 );
}

int main(){
    toOctal(100);
}

那么程序的输出就会变成“441”，原因也可以利用填充程序的方式来解答：

toOctal(100){
  if(n == 0) return 0;
  cout << 100 % 8 ;
    toOctal(12){
      if(n == 0) return 0;
        cout << 12 % 8 ;
        toOctal(1){
          if(n == 0) return 0;
          cout << 1 % 8 ;
          toOctal( 0 );  <---  n=0,到达边界
        }
    }
}