一、函数定义和调用

二、函数的递归调用

Hanoi 问题

从经典的汉诺塔Hanoi 问题入手

思路如下：

void hanoi(int n, char A, char B, char C)
{
    if (n == 1)
        move(A, C);
    else
    {
        hanoi(n - 1, A, C, B); //将上面的n-1个借助C从A移动到B
        move(A, C); //将最下面一个从A移到C
        hanoi(n - 1, B, A, C); //将n-1个从B借助A移动到C
    }
}

具体代码：

//将src针的最上面一个盘子移动到dest针上
void move(char src, char dest) { 
    cout << src << " --> " << dest << endl; } 

//将n个盘子从src针移动到dest针，以medium针作为中转
void hanoi(int n, char src, char medium, char dest)
{
    if (n == 1)
        move(src, dest);
    else
    {
        hanoi(n - 1, src, dest, medium);
        move(src, dest);
        hanoi(n - 1, medium, src, dest);
    }
}

int main()
{
    int m;
    cout << "Enter the number of diskes: ";
    cin >> m;
    cout << "the steps to moving " << m << " diskes:" << endl;
    hanoi(m, 'A', 'B', 'C');
    return 0;
}

当函数发生递归调用时，同一个局部变量在不同递归深度上可以同时存在不同的取值，这在底层是如何做到的？

答：对同一个函数的多次不同调用中，编译器会为函数的形参和局部变量分配不同的空间，他们互不影响。

递归练习

① 递归逆序打印字符串

// function to reverse a string
void stringReverse( string stringToReverse, int startSubscript )
{
   // return when null character is encountered
   if ( startSubscript == stringToReverse.length() )
      return;

   // recursively call stringReverse with new substring
   stringReverse( stringToReverse, startSubscript + 1 );
   cout << stringToReverse[ startSubscript ]; // output character
} // end function stringReverse

② 递归查询最小元素

// function to recursively find minimum array element
const int MAXRANGE = 1000;
int recursiveMinimum( const int array[], int low, int high )
{
   static int smallest = MAXRANGE;

   // if first element of array is smallest so far
   // set smallest equal to that element
   if ( array[ low ] < smallest )
      smallest = array[ low ];

   // if only one element in array, return smallest
   // else recursively call recursiveMinimum with new subarray
   return low == high ? 
      smallest : recursiveMinimum( array, low + 1, high );
}

三、函数的参数传递

在函数被调用时才给形参分配存储单元
实参可以是常量、变量或表达式
实参类型必须和形参类型相符
值传递是传递参数值，形参的改变不会引起实参的改变，即单向传递
引用传递可以实现双向传递
常引用作参数可以保障实参数据的安全

值传递

传递参数值，单向传递

引用传递（需要修改形参值的时候使用）

我们常用的交换函数就需要用到引用传递，实现双向传递，修改传进来的形参值

void swap(int &a, int &b){
 int temp = a;
 a = b;
 b = temp;

学习引用传递需详细掌握以下引用的知识

① 变量的引用

int &r = n;
某个变量的引用，等价于这个变量（即同一个人，不管谁发生改变，另一个也会随之改变）
int n = 7;
int &r = n; //定义引用时一定要将其初始化引用某个*变量*
r = 4;
cout<<r; //4
cout<<n; //4
n = 5;
cout<<r; //5

int a = 4;
int b = 5;
int &r1 = a;
int &r2 = r1; //等价于 int &r2 = a; r2也引用a
r2 = 10;
cout<<a; //10

一旦一个引用被初始化后，就不能改为指向其他对象

int a = 4;
int b = 5;
int &r1 = a;
//*一个引用是从一而终的*，该语句并不表示r1引用了b，而是b的值赋给了r1
r1 = b; 
cout<<a; //5

② 引用作为函数的返回值

int n = 4;
int &setValue(){ //返回了n的引用
    return n;
}
int main(){
    setValue() = 40; //函数返回的是n的引用，所以可以作为左值被赋值
    cout<<n; //给n的引用赋值40 等价于 给n赋值40
}

③ 常引用

const int &r = n;

不能通过常引用去修改其引用的内容

int n = 100;
const int &r = n;
r = 50; //wrong
n = 49; //right n的引用r的值也随之改变

三、内联函数

声明时使用关键字 inline
编译时在调用处用函数进行替换，节省了参数传递、控制转移等开销
注意：内联函数体内不能有循环语句和 switch 语句

内联函数的调用过程：

inline int Max(int a, int b){
    if(a>b)
        return a;
    return b;
}

假如主函数中有如下语句

K = Max(n1,n2);

等价于

if(n1 > n2)
    tmp = n1;
else 
    tmp = n2;
K = tmp;

即直接把函数体嵌入到代码中，而没有函数调用的出入栈的过程。

编译器并不承诺将inline修饰的函数作为内联，而在现代编译器中，没有inline修饰的函数也可能被编译为内联

四、带默认形参值的函数（缺省函数）

在相同的作用域内，不允许在同一个函数的多个声明中对同一个参数的默认值重复定义，即使前后定义的值相同也不行。

五、函数重载（形参个数/类型不同）

函数重载提高了程序的可扩充性。

(C语言中不允许同名函数，即没有重载的概念)

注：编译器不以形参名和返回值来区分重载。 若只有返回值类型不同，则不叫重载，叫重复定义

double func(int a, string var){ };
int func（int x, string b){ };

六、典型例题

数制转换

double power(double x, int n); //x的n次方
int main(){
    int value = 0;
    cout<<"please enter 8 bit binary number:";
    for(int i = 7; i>=0; i--){ //从高位往低位读入二进制数
        char ch;
        cin>>ch; //以字符形式读取
        if(ch == '1')
        	//强转
            value += static_cast<int>(power(2,i)); //value += (int)(power(2,i));
    }
    cout<<"decimal value is "<<value<<endl;
    return 0;
}
double power(double x, int n){
    double sum = 1.0;
    while(n--)
        sum = sum*x;
    return sum;
}

或者用数学方式处理

//以int形式读入的数学方式处理
   while ( binary != 0 )
   {
      decimal += binary % 10 * bit;
      binary /= 10;
      bit *= 2;
   }

编写程序求 π 的值

double arctanx(double x)
{
    double sqr = x * x; //x每次都乘以x2
    double e = x; //保存x的次方，分子
    double sum = 0; //保存最终结果
    int i = 1; //分母
    int flag = 1;
    while (e / i > 1e-15)
    {
        double f = flag * e / i;
        sum += f;
        e = e * sqr;
        i += 2;
        flag = -flag;
    }
    return sum;
}
int main()
{
	 //注意：因为整数相除结果取整，如果参数写1/5，1/239，结果就都是0
    double a = 16.0 * arctanx(1 / 5.0);
    double b = 4.0 * arctanx(1 / 239.0);
    cout << "PI = " << a - b << endl;
    return 0;
}

掷骰子

每个骰子有六面，点数分别为1、2、3、4、5、6。游戏者在程序开始时输入一个无符号整数，作为产生随机数的种子。
每轮投两次骰子，第一轮如果和数为7或11则为胜，游戏结束；和数为2、3或12 则为负，游戏结束；和数为其它值则将此值作为自己的点数，继续第二轮、第三轮...直到某轮的和数等于点数则取胜，若在此前出现和数为7则为负。

此处需要用到 rand 函数,rand产生的是伪随机数，即每次运行产生的是同一串随机数序列

//投骰子、计算和数、输出和数
int rollDice()
{
    int die1 = 1 + rand() % 6;
    int die2 = 1 + rand() % 6;
    int sum = die1 + die2;
    cout << "player rolled " << die1 << " + " << die2 << " = " << sum << endl;
    return sum;
}

enum GameStatus
{
    WIN,
    LOSE,
    PLAYING
};

int main()
{
    int sum, myPoint;
    GameStatus status;
    unsigned seed;
    cout << "Please enter an unsigned integer: ";
    cin >> seed;      //输入随机数种子
    srand(seed);      //将种子传递给rand()
    sum = rollDice(); //第一轮投骰子、计算和数
    switch (sum)
    {
    case 7: //如果和数为7或11则为胜,状态为WIN
    case 11:
        status = WIN;
        break;
    case 2: //和数为2、3或12则为负,状态为LOSE
    case 3:
    case 12:
        status = LOSE;
        break;
    default: //其它情况，尚无结果，状态为 PLAYING，记下点数
        status = PLAYING;
        myPoint = sum;
        cout << "point is " << myPoint << endl;
        break;
    }
    while (status == PLAYING)
    { //只要状态为PLAYING，继续
        sum = rollDice();
        if (sum == myPoint) //某轮的和数等于点数则取胜
            status = WIN;
        else if (sum == 7) //出现和数为7则为负
            status = LOSE;
    }
    //当状态不为PLAYING时循环结束，输出游戏结果
    if (status == WIN)
        cout << "player wins" << endl;
    else
        cout << "player loses" << endl;
    return 0;
}

递归计算从n个人中选k个人不同组合数。

int comm(int n, int k)
{
    if (k > n)
        return 0;
    else if (n == k || k == 0)
        return 1;
    else
        return comm(n - 1, k) + comm(n - 1, k - 1);
}

递归实现 getPower 计算 x的y次方

此处需要考虑两种情况，x是整数和 x是小数，利用重载编写两个做同样运算的函数 getPower

函数