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

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

void matrixAdd(const std::vector<std::vector>& a,               const std::vector<std::vector>& b,               std::vector<std::vector>& 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>& a, const std::vector<std::vector>& b,                 std::vector<std::vector>& c, int row, int col){    if (row == static_cast(a.size()))        return;    if (col == static_cast(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>& a,               const std::vector<std::vector>& b,               std::vector<std::vector>& 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& arr) {    int n = arr.size();    // 进行 n-1 轮的冒泡排序    for (int i = 0; i < n - 1; i++) {        // 在每一轮中,比较相邻的两个元素,将较大的元素向后移动        for (int j = 0; j  arr[j + 1]) {                std::swap(arr[j], arr[j + 1]);            }        }    }}
void bubbleSortRecursive(std::vector& arr, int n) {    // 基本情况:如果只剩下一个元素,已经有序    if (n == 1) {        return;    }    // 一次遍历,将最大的元素移动到末尾    for (int i = 0; i  arr[i + 1]) {            std::swap(arr[i], arr[i + 1]);        }    }    // 递归调用,对除了最后一个元素的子数组进行排序    bubbleSortRecursive(arr, n - 1);}

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

int fib(std::vector& 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);}

  先到这里,有什么好的想法也可以提一提~