MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

C++指针在递归函数中的应用

2022-08-241.8k 阅读

理解 C++ 指针

在深入探讨 C++ 指针在递归函数中的应用之前，我们先来全面理解一下 C++ 指针的概念。指针是 C++ 中一种强大的工具，它存储的是内存地址。通过指针，我们可以直接访问和操作内存中的数据，这为我们提供了极大的灵活性，但同时也带来了一定的风险，比如内存泄漏和悬空指针等问题。

指针基础

声明一个指针变量时，需要指定它所指向的数据类型。例如：

int *ptr; // 声明一个指向 int 类型的指针

这里，ptr 是一个指针变量，它可以存储 int 类型数据的内存地址。要获取一个变量的地址，可以使用取地址运算符 &。例如：

int num = 10;
int *ptr = #

在上述代码中，ptr 现在存储了 num 的内存地址。通过指针访问所指向的值，可以使用解引用运算符 *。例如：

std::cout << "通过指针访问的值: " << *ptr << std::endl;

这将输出 num 的值 10。

指针与内存管理

指针在内存管理中扮演着重要角色。动态内存分配使用 new 运算符，它会在堆上分配内存并返回指向该内存的指针。例如：

int *dynamicInt = new int;
*dynamicInt = 20;

这里，dynamicInt 是一个指向在堆上分配的 int 类型数据的指针。当我们不再需要这块动态分配的内存时，必须使用 delete 运算符来释放它，以避免内存泄漏。例如：

delete dynamicInt;

对于数组的动态分配，使用 new[] 和 delete[]。例如：

int *dynamicArray = new int[5];
for (int i = 0; i < 5; i++) {
    dynamicArray[i] = i * 2;
}
delete[] dynamicArray;

递归函数基础

递归函数是一种在函数定义中调用自身的函数。递归是解决许多问题的有效方法，特别是那些可以被分解为更小、相似子问题的问题。

递归函数的结构

一个典型的递归函数包含两个部分：基线条件（base case）和递归调用。基线条件是递归终止的条件，防止函数无限递归下去。递归调用则是函数调用自身，解决更小的子问题。

例如，计算阶乘的递归函数：

int factorial(int n) {
    if (n == 0 || n == 1) { // 基线条件
        return 1;
    } else {
        return n * factorial(n - 1); // 递归调用
    }
}

在这个例子中，当 n 为 0 或 1 时，函数返回 1，这就是基线条件。否则，函数通过递归调用 factorial(n - 1) 来计算 n 的阶乘。

递归函数的调用栈

理解递归函数的调用栈对于掌握递归原理至关重要。每次递归调用都会在调用栈中创建一个新的栈帧。例如，当调用 factorial(5) 时，调用栈的过程如下：

  1. factorial(5) 被调用，它计算 5 * factorial(4)。
  2. factorial(4) 被调用，它计算 4 * factorial(3)。
  3. factorial(3) 被调用，它计算 3 * factorial(2)。
  4. factorial(2) 被调用，它计算 2 * factorial(1)。
  5. factorial(1) 被调用，由于满足基线条件，返回 1。
  6. 然后，factorial(2) 计算 2 * 1 并返回 2。
  7. factorial(3) 计算 3 * 2 并返回 6。
  8. factorial(4) 计算 4 * 6 并返回 24。
  9. factorial(5) 计算 5 * 24 并返回 120。

随着递归调用的进行，调用栈会不断增长，如果没有正确的基线条件，调用栈可能会溢出，导致程序崩溃。

C++ 指针在递归函数中的简单应用

链表的递归遍历

链表是一种常见的数据结构，它由节点组成，每个节点包含数据和指向下一个节点的指针。使用指针和递归可以方便地遍历链表。

首先，定义链表节点结构：

struct ListNode {
    int data;
    ListNode *next;
    ListNode(int val) : data(val), next(nullptr) {}
};

然后，编写递归遍历链表的函数：

void traverseList(ListNode *head) {
    if (head == nullptr) { // 基线条件
        return;
    }
    std::cout << head->data << " ";
    traverseList(head->next); // 递归调用
}

在这个函数中，head 是指向链表头节点的指针。如果 head 为 nullptr，表示链表结束，这就是基线条件。否则，输出当前节点的数据，并递归调用 traverseList 处理下一个节点。

二叉树的递归遍历

二叉树也是一种常用的数据结构，每个节点最多有两个子节点。使用指针和递归可以实现二叉树的各种遍历方式，如前序遍历、中序遍历和后序遍历。

定义二叉树节点结构：

struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

前序遍历（根 - 左 - 右）的递归实现：

void preorderTraversal(TreeNode *root) {
    if (root == nullptr) { // 基线条件
        return;
    }
    std::cout << root->data << " ";
    preorderTraversal(root->left); // 递归遍历左子树
    preorderTraversal(root->right); // 递归遍历右子树
}

中序遍历（左 - 根 - 右）的递归实现：

void inorderTraversal(TreeNode *root) {
    if (root == nullptr) { // 基线条件
        return;
    }
    inorderTraversal(root->left); // 递归遍历左子树
    std::cout << root->data << " ";
    inorderTraversal(root->right); // 递归遍历右子树
}

后序遍历（左 - 右 - 根）的递归实现：

void postorderTraversal(TreeNode *root) {
    if (root == nullptr) { // 基线条件
        return;
    }
    postorderTraversal(root->left); // 递归遍历左子树
    postorderTraversal(root->right); // 递归遍历右子树
    std::cout << root->data << " ";
}

在这些函数中，root 是指向二叉树根节点的指针。根据不同的遍历顺序，先处理根节点、左子树或右子树，并通过递归调用处理子树的节点。

指针在递归函数中解决复杂问题

表达式树的求值

表达式树是一种用于表示数学表达式的数据结构。节点可以是操作数（如数字）或运算符（如 +, -, *, /）。通过指针和递归，可以实现表达式树的求值。

定义表达式树节点结构：

struct ExprNode {
    char op;
    double value;
    ExprNode *left;
    ExprNode *right;
    ExprNode(double num) : op(' '), value(num), left(nullptr), right(nullptr) {}
    ExprNode(char o, ExprNode *l, ExprNode *r) : op(o), value(0), left(l), right(r) {}
};

编写递归求值函数：

double evaluateExpression(ExprNode *root) {
    if (root->left == nullptr && root->right == nullptr) { // 基线条件，操作数节点
        return root->value;
    }
    double leftVal = evaluateExpression(root->left);
    double rightVal = evaluateExpression(root->right);
    switch (root->op) {
        case '+':
            return leftVal + rightVal;
        case '-':
            return leftVal - rightVal;
        case '*':
            return leftVal * rightVal;
        case '/':
            if (rightVal != 0) {
                return leftVal / rightVal;
            } else {
                std::cerr << "除数不能为零" << std::endl;
                return 0;
            }
        default:
            std::cerr << "不支持的运算符" << std::endl;
            return 0;
    }
}

在这个函数中，如果节点没有子节点，说明它是一个操作数节点，直接返回其值。否则，递归计算左子树和右子树的值，并根据节点的运算符进行相应的计算。

分治算法中的指针递归

分治算法是一种将问题分解为多个子问题，分别解决子问题，然后合并结果的算法策略。在一些分治算法中，指针递归可以有效地处理数据。

以归并排序为例，归并排序是一种基于分治思想的排序算法。它将一个数组分成两个子数组，分别对它们进行排序，然后将排好序的子数组合并成一个有序数组。

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = new int[n1];
    int *R = new int[n2];

    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    delete[] L;
    delete[] R;
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

在这个代码中，mergeSort 函数通过递归将数组不断分成更小的子数组，直到子数组只有一个元素（基线条件）。然后，通过 merge 函数将排好序的子数组合并起来。虽然这里没有直接使用指针作为函数参数来表示数据结构，但数组名本质上是一个指针，通过指针操作数组元素，在递归过程中实现了分治算法的排序功能。

指针递归中的常见问题与解决策略

内存泄漏

在递归函数中使用动态内存分配（如 new 运算符）时，如果没有正确释放内存，就会导致内存泄漏。例如，在链表的递归删除操作中，如果没有在递归调用后释放节点内存，就会造成内存泄漏。

void deleteList(ListNode *head) {
    if (head == nullptr) {
        return;
    }
    deleteList(head->next);
    delete head; // 正确释放节点内存
}

在这个函数中，先递归删除下一个节点，然后再释放当前节点的内存，从而避免了内存泄漏。

悬空指针

悬空指针是指指向已释放内存的指针。在递归函数中，如果在释放内存后没有将指针置为 nullptr，就可能产生悬空指针。例如：

ListNode *removeNode(ListNode *head, int value) {
    if (head == nullptr) {
        return nullptr;
    }
    if (head->data == value) {
        ListNode *temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    head->next = removeNode(head->next, value);
    return head;
}

在这个函数中，当找到要删除的节点时，先保存该节点指针 temp，然后更新 head 指针，再释放 temp 指向的内存。这样可以避免悬空指针问题。

栈溢出

递归函数调用会在调用栈中创建新的栈帧，如果递归深度过大，可能导致栈溢出。可以通过一些方法来避免栈溢出，例如尾递归优化。尾递归是指递归调用是函数的最后一个操作，这样编译器可以优化递归调用，避免栈的无限增长。

以计算阶乘为例，传统的递归实现不是尾递归：

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

而尾递归的实现如下：

int factorialHelper(int n, int acc = 1) {
    if (n == 0 || n == 1) {
        return acc;
    } else {
        return factorialHelper(n - 1, n * acc);
    }
}

int factorial(int n) {
    return factorialHelper(n);
}

在尾递归实现中，factorialHelper 函数的递归调用是最后一个操作，编译器可以对其进行优化，减少栈的使用。

总结与拓展

C++ 指针在递归函数中的应用非常广泛，无论是处理数据结构（如链表、二叉树），还是实现复杂算法（如表达式树求值、分治算法），指针递归都发挥着重要作用。然而，在使用指针递归时，需要注意内存管理、悬空指针和栈溢出等问题，通过正确的编码方式和优化策略来避免这些问题。

对于进一步的拓展，可以研究更复杂的数据结构和算法中的指针递归应用，如图的遍历算法（深度优先搜索和广度优先搜索）、高级数据结构（如红黑树、AVL 树）的操作等。同时，了解现代 C++ 中的智能指针（std::unique_ptr, std::shared_ptr, std::weak_ptr）在递归场景中的应用，能更好地管理内存，提高程序的安全性和可靠性。

希望通过本文的介绍，读者对 C++ 指针在递归函数中的应用有了更深入的理解，并能够在实际编程中灵活运用这一强大的技术。