C++ 递归

1、C++ 递归

 递归是使函数本身调用的技术。 该技术提供了一种将复杂问题分解为易于解决的简单问题的方法。

递归可能有点难以理解。弄清楚它是如何工作的最好方法是进行试验。

2、递归示例

将两个数字加在一起很容易，但是将一系列数字相加则比较复杂。在下面的示例中，递归通过将其分解为添加两个数字的简单任务而用于将多个数字加在一起：

例如，

#include <iostream>
using namespace std;
int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
}
int main() {
  cout << sum(4) << endl;
  return 0;
}

示例说明：

当sum()函数被调用时，它将参数k加到所有小于k的数的和中并返回结果。当k变为0时，函数返回0。当运行时，程序遵循以下步骤:

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

因为函数在k为0时不调用自身，所以程序在这里停止并返回结果。

3、递归跳出条件

就像循环会遇到无限循环的问题一样，递归函数也会遇到无限递归的问题。 无限递归是函数永不停止调用自己。 每个递归函数都应具有停止条件，即该函数停止自行调用的条件。 在前面的示例中，跳出条件是参数k变为0时。

看到各种不同的示例有助于更好地理解该概念。 在此示例中，该函数在开始和结束之间添加多个数字。 此递归函数的跳出条件是end不大于start时：

例如：

使用递归将5到10之间的所有数字相加。

#include <iostream>
using namespace std;
int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
}
int main() {
  cout << sum(5,10) << endl;
  return 0;
}

4、递归的应用

求一个数的阶乘是练习简单而典型的例子，阶乘的递推公式为：factorial(n)=n*factorial(n-1)，其中n为非负整数,且0!=1,1!=1

我们根据递推公式可以轻松的写出其递归函数：

#include <iostream>
using namespace std;
int factorial(int n){
    if (n < 0)
        printf("参数不能为负！");
    else if (n == 1 || n == 0)
        return 1;
    else
        return n * factorial(n - 1);
    return 0;
}
int main() {
  cout << factorial(6) << endl;
  return 0;
}

递归过程如下图所示，

5、递归解决汉诺塔问题

汉诺塔问题是一种经典递归问题，要求将 n 个圆盘从源柱移动到目标柱，且只能将小圆盘放在大圆盘上，一次只能移动一个圆盘。

#include <iostream>
using namespace std;

void hanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) { // 基本情况
        cout << "Move disk 1 from " << source << " to " << destination << endl;
        return;
    }
    // 将 n-1 个圆盘从源柱移动到辅助柱
    hanoi(n - 1, source, auxiliary, destination);
    // 将第 n 个圆盘从源柱移动到目标柱
    cout << "Move disk " << n << " from " << source << " to " << destination << endl;
    // 将 n-1 个圆盘从辅助柱移动到目标柱
    hanoi(n - 1, auxiliary, destination, source);
}

int main() {
    int num = 3; // 圆盘数量
    hanoi(num, 'A', 'C', 'B');
    return 0;
}