学算法阶段时不时会遇到一些递归的应用场景,例如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);}
先到这里,有什么好的想法也可以提一提~