RootStack

10_函数基础

14分钟阅读

函数基础

建议先阅读：09_数组基础

原理

函数调用栈帧

每次函数调用在调用栈上压入一个栈帧（stack frame），包含：

  • 返回地址（调用方下一条指令的地址）
  • 保存的基指针（调用方的 ebp/rbp）
  • 局部变量
  • 参数（部分可能通过寄存器传递）

函数返回时弹出栈帧，程序计数器跳回返回地址继续执行。这就是为什么递归过深会导致栈溢出——每个递归调用都分配新栈帧，超出操作系统限制（通常 8MB）。

值传递 vs 引用传递

void byValue(int x) { x++; }  // 栈帧上复制一份 x，修改不影响实参
void byRef(int& x) { x++; }   // x 是实参的别名，修改直接作用于实参

引用在底层实现为指针——编译器自动解引用，语法层无需 *。对大型对象（如 string），const 引用避免昂贵的内存拷贝。

名称修饰 (Name Mangling)

C++ 的函数重载依赖名称修饰——编译器将函数名、参数类型信息编码为唯一的链接符号。例如 add(int, double) 在不同编译器下可能编为 _Z3addid（GCC）或 ?add@@YAHHN@Z（MSVC）。这就是为什么 C++ 函数不能被 C 代码直接调用（需要 extern "C" 禁止修饰）。

内联与调用开销

函数调用有固定开销：压栈参数、跳转、分配栈帧、返回。inline 将函数体在调用处展开，消除调用开销。但内联增加代码体积（code bloat），影响指令缓存。编译器会根据启发式规则自主决定是否内联——inline 关键字只是建议。

语法

声明与定义

int add(int a, int b);      // 声明（原型）
int add(int a, int b) {     // 定义
    return a + b;
}

声明可多次，定义只能一次（单一定义规则 ODR）。函数必须先声明后调用。

值传递与引用传递

void swap(int& a, int& b) { // 引用传递，修改生效
    int temp = a;
    a = b;
    b = temp;
}
 
void print(const std::string& s) { // const 引用：不拷贝，不修改
    std::cout << s << '\n';
}

基本类型 (int, char, double) 值传递即可；大对象使用 const 引用。

函数重载

同名函数，参数列表不同（类型/数量/顺序）：

int add(int a, int b);
double add(double a, double b);
int add(int a, int b, int c);

仅返回类型不同不构成重载——编译器无法仅凭调用上下文区分。

默认参数

void print(std::string msg, int times = 1, std::string end = "\n") {
    for (int i = 0; i < times; i++)
        std::cout << msg << end;
}
// 调用: print("Hi"); print("Hi", 3); print("Hi", 2, " ");

默认参数必须从右向左连续设置，不能跳跃。

递归

int factorial(int n) {
    if (n <= 1) return 1; // 基准条件 (终止)
    return n * factorial(n - 1);
}

每个递归必须有无条件到达的基准条件。尾递归（最后一步是自身调用）可被编译器优化为循环。

头文件组织

// utils.h
#ifndef UTILS_H
#define UTILS_H
int add(int a, int b);
#endif
 
// utils.cpp
#include "utils.h"
int add(int a, int b) { return a + b; }
 
// main.cpp
#include "utils.h"

详解：函数重载决议

编译器按以下步骤选择重载函数：

  1. 名称查找：在作用域内找到所有同名函数
  2. 实参推导：将实参类型与每个重载的形参类型匹配
  3. 最佳匹配：选择”最匹配”的重载

匹配优先级：

  • 精确匹配（无需转换）
  • 提升匹配（char → int）
  • 标准转换匹配（int → double）
  • 用户自定义转换匹配（构造函数/转换运算符）
  • 无匹配 → 编译错误
void f(int);
void f(double);
void f(int, int);
 
f(42);        // 精确匹配: f(int)
f(3.14);      // 精确匹配: f(double)
f('a');       // 提升匹配: f(int) (char → int)
f(1, 2);      // 精确匹配: f(int, int)
// f(1, 2.0); // 歧义错误: f(int,int) 和 f(double) 均可匹配

重载 vs 函数模板

// 重载: 为每种类型写一份
int max(int a, int b) { return a > b ? a : b; }
double max(double a, double b) { return a > b ? a : b; }
 
// 模板: 自动生成 (C++98)
template<typename T>
T max_val(T a, T b) { return a > b ? a : b; }
// max_val(1, 2) -> T=int, max_val(1.5, 2.5) -> T=double

extern “C”

// C++ 函数被 C 调用
extern "C" void c_style_func(int x) {
    // 无名称修饰，可被 C 链接器找到
}
 
// C 函数被 C++ 调用
extern "C" {
    #include <math.h> // C 头文件
}

详解：默认参数深入

声明与定义中的默认参数

// 声明中提供默认值
void func(int a, int b = 10, int c = 20);
 
// 定义中不能重复提供
void func(int a, int b, int c) {
    std::cout << a << b << c;
}
 
// 错误: 重复默认值
// void func(int a, int b = 10, int c = 20) { ... }

默认参数与重载的陷阱

void f(int a, int b = 10) { ... }
void f(int a) { ... }
 
f(5); // 歧义! 两个 f 都可以匹配

建议：默认参数和函数重载不要混用，容易产生歧义。

详解：constexpr 函数

C++11: 基本 constexpr

constexpr int factorial(int n) {
    return n <= 1 ? 1 : n * factorial(n - 1);
}
 
// 编译期计算
constexpr int f5 = factorial(5); // 120, 编译时求值
int x = 10;
int f10 = factorial(x); // 运行时求值（x 不是 constexpr）

C++14: 放宽限制

// C++14: constexpr 函数可以有循环、局部变量
constexpr int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}
 
constexpr int fib10 = fibonacci(10); // 55, 编译期

C++17: if constexpr

template<typename T>
constexpr auto convert(T val) {
    if constexpr (std::is_integral_v<T>) {
        return static_cast<double>(val);
    } else {
        return val;
    }
}
// 编译期根据类型选择分支，无运行时开销

constexpr 的价值

// 编译期验证: 错误在编译时暴露
constexpr int sqrt_int(int n) {
    if (n < 0) throw "negative"; // C++14: constexpr 函数可以 throw
    int root = 0;
    while ((root + 1) * (root + 1) <= n) root++;
    return root;
}
// constexpr int bad = sqrt_int(-1); // 编译错误!
 
// 用于模板参数
template<int N>
struct Array {
    int data[N];
};
Array<sqrt_int(100)> arr; // 编译期: N=10

详解：Lambda 表达式 (C++11)

基本语法

// [捕获列表](参数列表) -> 返回类型 { 函数体 }
auto greet = []() { std::cout << "Hello!\n"; };
greet(); // Hello!
 
// 带参数
auto add = [](int a, int b) { return a + b; };
add(3, 4); // 7
 
// 带返回类型
auto divide = [](double a, double b) -> double {
    if (b == 0) return 0;
    return a / b;
};

捕获方式

int x = 10, y = 20;
 
// 值捕获 (只读)
auto f1 = [x, y]() { return x + y; };
 
// 引用捕获 (可修改)
auto f2 = [&x, &y]() { x++; y++; };
 
// 隐式值捕获
auto f3 = [=]() { return x + y; }; // 捕获所有外部变量(值)
 
// 隐式引用捕获
auto f4 = [&]() { x++; y++; };     // 捕获所有外部变量(引用)
 
// 混合捕获
auto f5 = [=, &x]() { return x + y; }; // y值捕获, x引用捕获

Lambda vs 函数指针 vs std::function

// Lambda: 零开销，类型唯一
auto lambda = [](int x) { return x * 2; };
 
// 函数指针: 只能捕获全局函数
int global_add(int a, int b) { return a + b; }
int (*fptr)(int, int) = global_add; // OK
// fptr = lambda; // 错误: lambda 不能隐式转为函数指针(无捕获时可以)
 
// std::function: 通用包装，有运行时开销
std::function<int(int)> func = lambda; // OK
func = global_add; // OK
func = [](int x) { return x + 100; }; // OK
特性Lambda函数指针std::function
捕获外部变量可以不能可以
运行时开销无无有（堆分配）
类型唯一类型int(*)(int)std::function<int(int)>
作为模板参数推荐可以不推荐
可赋值性有限可互换完全通用

Lambda 实用示例

#include <algorithm>
#include <vector>
 
std::vector<int> v = {3, 1, 4, 1, 5, 9};
 
// 排序: 传入 lambda 比较器
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b; // 降序
});
 
// 查找: 第一个大于 3 的元素
auto it = std::find_if(v.begin(), v.end(), [](int x) {
    return x > 3;
});
 
// 计数: 统计偶数个数
int count = std::count_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});

详解：函数指针 vs std::function

函数指针

// 声明
int (*fptr)(int, int) = add;      // 指向全局函数
int (*fptr2)(int, int) = &add;    // & 可省略
 
// 调用
fptr(3, 4);    // 7
(*fptr)(3, 4); // 7, 两种写法等价
 
// 作为参数 (回调)
void execute(int (*func)(int, int), int a, int b) {
    std::cout << func(a, b);
}
execute(add, 3, 4); // 7

std::function

#include <functional>
 
std::function<int(int, int)> f = add;          // 普通函数
f = [](int a, int b) { return a + b; };       // Lambda
f = std::bind(add, std::placeholders::_1, std::placeholders::_2); // bind
 
f(3, 4); // 7
 
// 检查是否为空
if (f) { f(1, 2); } // 有值时调用

何时使用哪个

// 1. 高性能场景: 函数指针或模板
// 编译期确定，零开销
void sort(int* begin, int* end, bool (*comp)(int, int));
 
// 2. 需要存储状态: Lambda + std::function
int counter = 0;
std::function<int()> gen = [counter]() mutable { return ++counter; };
 
// 3. STL 算法: Lambda (推荐)
std::sort(v.begin(), v.end(), [](int a, int b) { return a < b; });
 
// 4. 回调接口: std::function (通用性)
using Callback = std::function<void(int)>;
void register_callback(Callback cb);

详解：内联函数

inline 的本质

// inline: 建议编译器在调用处展开
inline int square(int x) { return x * x; }
 
// 编译器可能展开为:
int y = square(5); // int y = 5 * 5;
// 或者保留函数调用 (编译器自主决定)

何时内联有效

// 小函数: 内联有收益
inline int max_val(int a, int b) { return a > b ? a : b; }
 
// 大函数: 内联增加代码体积，可能降低性能
inline void huge_function() {
    // 几十行代码...
    // 不建议内联
}

编译器决策

现代编译器（GCC/Clang）会自主决定是否内联，无视 inline 关键字。inline 的真正作用是允许函数在多个翻译单元中定义（消除链接器的 ODR 违规）。

实践

计算整数幂（快速幂）：

double power(double base, int exp) {
    if (exp == 0) return 1;
    double half = power(base, exp / 2);
    if (exp % 2 == 0)
        return half * half;
    else if (exp > 0)
        return half * half * base;
    else
        return half * half / base; // 负指数
}

尾递归优化

// 普通递归: O(n) 栈空间
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1); // 最后一步是乘法
}
 
// 尾递归: O(1) 栈空间 (编译器优化为循环)
int factorial_tail(int n, int acc = 1) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc); // 最后一步是自身调用
}

回调函数模式

#include <functional>
#include <vector>
 
// 通用遍历
void for_each(const std::vector<int>& v, std::function<void(int)> func) {
    for (int x : v) func(x);
}
 
// 使用
std::vector<int> nums = {1, 2, 3, 4, 5};
for_each(nums, [](int x) { std::cout << x * x << ' '; });
// 输出: 1 4 9 16 25

练习

题号题目链接知识点
50Pow(x, n)https://www.luogu.com.cn/problem/P1001快速幂、递归
70爬楼梯https://www.luogu.com.cn/problem/P1001递归、记忆化
172阶乘后的零https://www.luogu.com.cn/problem/P1001数学、函数封装
206反转链表https://www.luogu.com.cn/problem/P1001递归、迭代
2312的幂https://www.luogu.com.cn/problem/P1001位运算、递归
3424的幂https://www.luogu.com.cn/problem/P1001位运算、数学
367有效的完全平方数https://www.luogu.com.cn/problem/P1001二分查找、数学
392判断子序列https://www.luogu.com.cn/problem/P1001双指针、函数抽象
509斐波那契数https://www.luogu.com.cn/problem/P1001递归、迭代
704二分查找https://www.luogu.com.cn/problem/P1001二分、函数封装

关系图谱

反向链接