假如我们把函数都改成递归...-Toy模板网

这篇具有很好参考价值的文章主要介绍了假如我们把函数都改成递归...。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

学算法阶段时不时会遇到一些递归的应用场景，例如DFS，二叉树等相关的题目，递归常常能大展身手。不过有意思的一件事情是，若我们把一些本该迭代的算法改成递归实现，会是什么样的情形。

这是一个很简单的矩阵加法的例子。

void matrixAdd(const std::vector<std::vector<int>>& a,
               const std::vector<std::vector<int>>& b,
               std::vector<std::vector<int>>& c)
{
    int n1 = a.size(), m1 = a[0].size();
    int n2 = b.size(), m2 = b[0].size();
    assert(n1 == n2 && m1 == m2);

    for (int i = 0; i < n1; ++i)
    {
        for (int j = 0; j < m1; ++j)
        {
            c[i][j] = a[i][j] + b[i][j];
        }
    }
}

同样有递归版本，很多时候这两者都是可以相互转换的。

void __matrixAdd(const std::vector<std::vector<int>>& a, const std::vector<std::vector<int>>& b,
                 std::vector<std::vector<int>>& c, int row, int col)
{
    if (row == static_cast<int>(a.size()))
        return;
    if (col == static_cast<int>(a[0].size()))
    {
        __matrixAdd(a, b, c, row + 1, 0);
        return;
    }

    c[row][col] = a[row][col] + b[row][col];
    __matrixAdd(a, b, c, row, col + 1);
}

void matrixAdd(const std::vector<std::vector<int>>& a,
               const std::vector<std::vector<int>>& b,
               std::vector<std::vector<int>>& c)
{
    int n1 = a.size(), m1 = a[0].size();
    int n2 = b.size(), m2 = b[0].size();
    assert(n1 == n2 && m1 == m2);
    __matrixAdd(a, b, c, 0, 0);
}

当row越界的时候，直接return不用再往下操作了；而当col越界的时候，可以往下一行重新进行相加操作，这里也要return，不然后续的操作会导致越界。可以直观看到代码并没有用到for循环，看起来比较简练。接下来是冒泡排序。

void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();

    // 进行 n-1 轮的冒泡排序
    for (int i = 0; i < n - 1; i++) {
        // 在每一轮中，比较相邻的两个元素，将较大的元素向后移动
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
            }
        }
    }
}

void bubbleSortRecursive(std::vector<int>& arr, int n) {
    // 基本情况：如果只剩下一个元素，已经有序
    if (n == 1) {
        return;
    }

    // 一次遍历，将最大的元素移动到末尾
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            std::swap(arr[i], arr[i + 1]);
        }
    }

    // 递归调用，对除了最后一个元素的子数组进行排序
    bubbleSortRecursive(arr, n - 1);
}

相比原来的迭代版本少了一个for循环，代码量相差不大。再来看看斐波那契数列，通常它的递归实现是只保留最后一项的，我们也可以写一个保留中间计算过程的版本。

int fib(std::vector<int>& arr, int n) {
    if (n <= 1) {
        arr[n] = n;
        return arr[n];
    }

    arr[n] = fib(arr, n - 1) + fib(arr, n - 2);
    return arr[n];
}

字符串翻转也是很容易实现的。

void reverseString(std::string& str, int left, int right) {
    if (left >= right) {
        return;
    }

    // 交换左右字符
    std::swap(str[left], str[right]);

    // 递归翻转剩余部分
    reverseString(str, left + 1, right - 1);
}

先到这里，有什么好的想法也可以提一提~文章来源地址https://www.toymoban.com/news/detail-760175.html

到了这里，关于假如我们把函数都改成递归...的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！