第19讲：函数进阶

《计算机程序设计》

苏醒

计算机学院计算机研究所编译系统研究室

课前准备

• 在WSL Ubuntu中建立一个专门的目录用于课上练习，如~/course

$ mkdir ~/course

• 打开VSCode并连接到WSL，打开此目录并新建文件，如~/course/main.cpp
• 编辑main.cpp，随堂编程练习的代码请直接在此文件中编辑

main.cpp

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  // ============= begin =============

  // =============  end  =============
  return 0;
}

温故

• 阅读下列程序，判断程序输出

文件读写

#include <fstream>
#include <iostream>
using namespace std;
int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  ofstream fout("data.txt");
  for (int i = 0; i < 5; i++)
    fout << arr[i] << ' ';
  fout.close();
  ifstream fin("data.txt");
  int value;
  while (not fin.eof()) {
    fin >> value;
    cout << value << ' ';
  }
  return 0;
}

学习目标

• 学习内容
  • 递归函数
  • 默认参数
  • 函数重载

学习目标

• 掌握C++默认参数的使用方法
• 掌握重载函数的定义方法
• 理解递归函数的基本原理与执行过程
• 运用递归函数解决递归问题

一、递归函数

回顾：斐波那契数列

• 斐波那契数列的定义如下
  • 数列前两项的值为1
  • 后续每一项的值等于该项之前两项的和

\[ F(n) = \begin{cases} 1 & n < 2 \\ F(n-1) + F(n-2) & n \ge 2 \end{cases} \]

斐波那契数列

def fibnacci(n):
  if n < 2:
    return 1
  x = fibnacci(n-1)
  y = fibnacci(n-2)  
  return x + y

1.1 递归函数的概念

• 在执行过程中调用自身的函数称为递归函数

直接调用本函数

int fibnacci(int n) {
  if (n < 2) return 1;
  return fibnacci(n-1) + fibnacci(n-2); // 调用自身
}

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 28px
---
flowchart LR
  fibnacci --> fibnacci

间接调用本函数（互递归）

int foo(int n) {
  if (n < 2) return 1;
  return bar(n-1);     // foo调用bar
}
int bar(int n) {
  if (n < 2) return 1;
  return foo(n-1) + 1; // bar调用foo
}

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 28px
---
flowchart LR
  foo --> bar
  bar --> foo

1.1 递归函数的概念

• 递归函数用于解决具有自相似性的问题

考考你

阶乘公式可否具有自相似性？可否通过递归方式定义？

1.1 递归函数的概念

• 试从下列问题出发，总结递归方法求解自相似问题的一般方法

\[ sum(n) = \begin{cases} 0 & n = 0 \\ n + sum(n-1) & n > 0 \end{cases} \]

\[ n! = \begin{cases} 1 & n = 0 \\ n \times (n-1)! & n > 0 \end{cases} \]

\[ F(n) = \begin{cases} 1 & n < 2 \\ F(n-1) + F(n-2) & n \ge 2 \end{cases} \]

1.2 递归的基本原理

• 递归的基本原理
  • 将当前问题分解为更简单（规模更小）的同结构问题
  • 当问题简单（规模小）到一定程度时可以直接求解，无需再分解

明察秋毫

• 递归二要素
  • 递推公式：将问题分解为更简单同构问题的方法
  • 边界问题：无需进一步分解即可直接求解的问题

\[ F(n) = \begin{cases} 1 & n < 2 & \Leftarrow \text{边界问题}\\ F(n-1) + F(n-2) & n \ge 2 & \Leftarrow \text{递推公式} \end{cases} \]

1.2 递归的基本原理

• 从递归的基本原理出发，递归函数可通过组合递归二要素实现

递归函数的构造模板

return_type function_name(parameter_list) {
  if (base_case) { // 边界问题
    // 直接求解
    return ...;
  }
  // 1. 分解问题并逐个求解
  // 2. 利用递推公式将子问题的解组合得到当前问题的解
  return ...;
}

考考你

编写一个递归函数，计算n!的值

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

$ g++ -o code/factorial code/factorial.cpp
$ ./code/factorial 3

1 &n=0x7ffd776221bc, &subfactorial=0x7ffd776221c4
2 &n=0x7ffd776221ec, &subfactorial=0x7ffd776221f4
3 &n=0x7ffd7762221c, &subfactorial=0x7ffd77622224
6

考考你

上述程序的输出结果说明了什么现象？

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

factorial.cpp

#include <cstdlib>
#include <iostream>
using namespace std;
int factorial(int n) {
  if (n == 0) {
    return 1;
  }
  int subfactorial = factorial(n - 1);
  cout << n << " &n=" << &n << ", &subfactorial=" << &subfactorial << endl;
  return n * subfactorial;
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int f = factorial(n);
  cout << f << '\n';
  return 0;
}

函数调用栈

$ ./code/factorial 2

1.3 递归函数调用过程

• 递归函数的调用过程
  • 每个函数调用都会在栈顶压入自己的内存空间用于存储函数参数、局部变量
  • 当函数执行完毕返回调用点时，会退栈释放这块内存空间

考考你

如果递归调用的深度过深，会发生什么？

明察秋毫

函数调用的实现机制可以保证统一函数的不同调用栈空间隔离，但递归本身会引入较多的函数调用开销

1.4 递归函数应用

考考你

假设一对成熟的兔子每月能生一对小兔（一雌一雄），小兔一个月后长为成熟兔子，假定兔子不死亡，那么由一对刚出生的小兔开始，3年后有多少对兔子？

兔子繁殖问题

int rabbit(int months) {
  // 边界问题

  // 递归求解

}

兔子繁殖问题

int rabbit(int months) {
  // 边界问题
  if (months <= 2) return 1;
  // 递归求解
  return rabbit(n-1) + rabbit(n-2);
}

科学考古

1202年，意大利数学家斐波那契提出了“兔子繁殖问题”，这就是斐波那契数列的由来

1.4 递归函数应用

考考你

假设小明每一步可以登上一级、两级或者三级台阶，问小明有多少种不同方式登上n个台阶？

step.cpp

#include <iostream>
#include <cstdlib>
using namespace std;
int step(int n) {
  // 边界问题



  // 递归求解

}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  cout << step(n) << endl;
}

step.cpp

#include <iostream>
#include <cstdlib>
using namespace std;
int step(int n) {
  // 边界问题
  if (n == 1) return 1;
  if (n == 2) return 2;
  if (n == 3) return 4;
  // 递归求解
  return step(n-1) + step(n-2) + step(n-3);
}
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  cout << step(n) << endl;
}

$ g++ -o code/step code/step.cpp
$ ./code/step 5

13

1.4 递归函数应用

考考你

能不能使用递归的思路实现排序算法？思路：选择一个元素将之放置到正确的位置上，然后对剩余的元素进行排序

selectsort.cpp

#include <cstdlib>
#include <iostream>
#include <chrono>
using namespace std;
void select_sort(int a[], int i, int n);
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int *a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = rand() % RAND_MAX;
  auto start = chrono::system_clock::now();
  select_sort(a, 0, n);
  auto end = chrono::system_clock::now();
  chrono::duration<double> elapsed_seconds = end - start;
  cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
  delete[] a;
  return 0;
}

selectsort.cpp

void select_sort(int a[], int i, int n) {
  if (i == n - 1)
    return;
  int min_index = i;
  for (int j = i + 1; j < n; j++)
    if (a[j] < a[min_index])
      min_index = j;
  swap(a[i], a[min_index]);
  select_sort(a, i + 1, n);
}

1.4 递归函数应用

考考你

能不能使用递归的思路实现排序算法？思路：选择一个元素将之放置到正确的位置上，然后对剩余的元素进行排序

quicksort.cpp

#include <cstdlib>
#include <iostream>
#include <chrono>
using namespace std;
void quicksort(int a[], int i, int j);
int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  int *a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = rand() % RAND_MAX;
  auto start = chrono::system_clock::now();
  quicksort(a, 0, n);
  auto end = chrono::system_clock::now();
  chrono::duration<double> elapsed_seconds = end - start;
  cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
  delete[] a;
  return 0;
}

quicksort.cpp

void quicksort(int a[], int i, int j) {
  if (i + 1 == j) {
    if (a[i] > a[j]) swap(a[i], a[j]);
    return;
  }
  int middle = a[(i + j) / 2];
  int left = i, right = j;
  while (left <= right) {
    while (a[left] < middle) left++;
    while (a[right] > middle) right--;
    if (left <= right) {
      swap(a[left], a[right]);
      left++;
      right--;
    }
  }
  if (i < right) quicksort(a, i, right);
  if (left < j) quicksort(a, left, j);
}

1.4 递归函数应用

考考你

选择排序与快速排序，你觉得哪个更快？

$ g++ -o code/selectsort code/selectsort.cpp
$ g++ -o code/quicksort code/quicksort.cpp
$ ./code/selectsort 1000; ./code/selectsort 10000; ./code/selectsort 100000
$ ./code/quicksort 1000; ./code/quicksort 10000; ./code/quicksort 100000

elapsed time: 0.000477592s
elapsed time: 0.0468432s
elapsed time: 4.5469s
elapsed time: 8.1016e-05s
elapsed time: 0.000843884s
elapsed time: 0.0112795s

1.4 递归函数应用

在印度，有一个古老的传说：布拉马圣殿有三根金刚石柱子，第一根柱子上套放了64个金盘，每个金盘都比其下面的金盘略小。教士们预言：当按预定的规则，把第一根柱子上的金盘全部移到第三根柱子上时世界末日就会来临

汉诺塔

二、默认参数与函数重载

2.1 默认参数

• C++函数参数支持设置默认值，称为默认参数

默认参数

#include <iostream>
using namespace std;
int func(int a, int b = 10, int c = 20) {
  return a + b + c;
}
int main() {
  cout << func(1) << endl; // 1 + 10 + 20
  cout << func(1, 2) << endl; // 1 + 2 + 20
  cout << func(1, 2, 3) << endl; // 1 + 2 + 3
  return 0;
}

明察秋毫

• 默认参数必须从右向左设置
  • 如果一个参数有默认值，则其右侧的参数也必须有默认值

2.1 默认参数

• 若在同一个编译单元中出现了多次函数声明，则仅在第一次声明中设置默认参数

defaultarg.cpp

#include <iostream>
using namespace std;
int func(int a, int b = 10, int c = 20);
int main() {
  cout << func(1) << endl; // 1 + 10 + 20
  cout << func(1, 2) << endl; // 1 + 2 + 20
  cout << func(1, 2, 3) << endl; // 1 + 2 + 3
  return 0;
}
int func(int a, int b = 10, int c = 20) {
  return a + b + c;
}

$ g++ -o code/defaultarg code/defaultarg.cpp

code/defaultarg.cpp:10:5: error: default argument given for parameter 2 of ‘int func(int, int, int)’ [-fpermissive]
   10 | int func(int a, int b = 10, int c = 20) {
      |     ^~~~
code/defaultarg.cpp:3:5: note: previous specification in ‘int func(int, int, int)’ here
    3 | int func(int a, int b = 10, int c = 20);
      |     ^~~~
code/defaultarg.cpp:10:5: error: default argument given for parameter 3 of ‘int func(int, int, int)’ [-fpermissive]
   10 | int func(int a, int b = 10, int c = 20) {
      |     ^~~~
code/defaultarg.cpp:3:5: note: previous specification in ‘int func(int, int, int)’ here
    3 | int func(int a, int b = 10, int c = 20);
      |     ^~~~

2.2 函数重载

考考你

以下是C标准库中的浮点绝对值函数（在math.h头文件中声明），看一看有没有令人不满意的地方？

C标准库中的浮点绝对值函数

float fabsf(float x);
double fabs(double x);
long double fabsl(long double x);

不足之处

三个函数功能一致，仅因为作用在不同精度浮点类型上，就需要不同的函数名予以区分

2.2 函数重载

• C++支持函数重载机制解决C语言的这一不足之处
• 只需包含头文件<cmath>，即可对任意精度的浮点数调用fabs()函数

C++标准库中的浮点绝对值函数

float fabs(float x);
double fabs(double x);
long double fabs(long double x);

明察秋毫

还有一个更加通用的函数abs()，可以计算任意整数与浮点类型的绝对值

C++标准库中的绝对值函数

int abs(int x);
long int abs(long int x);
long long int abs(long long int x);
float abs(float x);
double abs(double x);
long double abs(long double x);

2.2 函数重载

• C++函数重载：允许定义多个同名函数，函数通过不同的形式参数列表予以区分
  • 参数个数不同
  • 参数类型不同
  • 参数顺序不同

函数重载

Node *insert(Node *list, int index, int value);
Node *insert(Node *list, int index, double value);

int compare(int a, double b);
int compare(double a, int b);

2.2 函数重载

考考你

下面的函数重载是否正确？

函数重载

int getListNodeValue(Node *, int index);
double getListNodeValue(Node *, int index);

函数重载

int getListNodeValue(Node *, int index);
double getListNodeValue(Node *, int index);

int main() {
  Node *p = new Node;
  cout << getListNodeValue(p, 1) << endl; // 应该调用哪个版本？
}

明察秋毫

函数重载不允许仅通过返回值区分同名函数！

2.3 函数重载的二义性问题

考考你

下面程序是否存在问题？

funcquiz.cpp

#include <iostream>
using namespace std;
int func(int a, int b = 1) { return a + b; }
int func(int a) { return a; }
int func(int a, int b, int c = 1) { return a + b + c; }
int main() {
  cout << func(1) << endl;
  cout << func(1, 2) << endl;
  cout << func(1, 2, 3) << endl;
  return 0;
}

$ g++ -o code/funcquiz code/funcquiz.cpp

code/funcquiz.cpp: In function ‘int main()’:
code/funcquiz.cpp:7:15: error: call of overloaded ‘func(int)’ is ambiguous
    7 |   cout << func(1) << endl;
      |           ~~~~^~~
code/funcquiz.cpp:3:5: note: candidate: ‘int func(int, int)’
    3 | int func(int a, int b = 1) { return a + b; }
      |     ^~~~
code/funcquiz.cpp:4:5: note: candidate: ‘int func(int)’
    4 | int func(int a) { return a; }
      |     ^~~~
code/funcquiz.cpp:8:15: error: call of overloaded ‘func(int, int)’ is ambiguous
    8 |   cout << func(1, 2) << endl;
      |           ~~~~^~~~~~
code/funcquiz.cpp:3:5: note: candidate: ‘int func(int, int)’
    3 | int func(int a, int b = 1) { return a + b; }
      |     ^~~~
code/funcquiz.cpp:5:5: note: candidate: ‘int func(int, int, int)’
    5 | int func(int a, int b, int c = 1) { return a + b + c; }
      |     ^~~~

避坑

• 注意函数重载二义性问题：（1）函数重载与默认参数共同使用，（2）通过返回值区分同名函数

总结

本节内容

---
config:
  look: handDrawn
  themeVariables:
    fontSize: 24px
---
mindmap
函数进阶
  默认参数
  函数重载
    二义性问题
  递归函数
    递归的概念
    递归基本原理（二要素）
    递归函数调用过程
    递归函数应用
      数列求解
      上台阶问题
      排序问题
      汉诺塔问题

学习目标

• 掌握C++默认参数的使用方法
• 掌握重载函数的定义方法
• 理解递归函数的基本原理与执行过程
• 运用递归函数解决递归问题

课后作业

• 实训（截止时间2025.05.11）
  • C&C++函数实训

计算机程序设计