头歌C++之递归进阶练习题

头歌C++中的递归是一种高级技巧，它通过函数自身调用来解决问题，尤其适用于那些可以分解为相同子问题的复杂算法。递归练习题通常涉及经典的计算机科学问题，如计算阶乘、斐波那契数列、二分查找等。下面是一些递归进阶练习题的例子：

1. **阶乘计算**：编写一个函数，输入一个整数n，返回n的阶乘（n! = n * (n-1) * ... * 1）。

int factorial(int n);

2. **斐波那契数列**：生成并返回给定位置的斐波那契数，F(n) = F(n-1) + F(n-2)。

unsigned long long fibonacci(int n);

3. **汉诺塔**：经典的递归问题，移动三柱塔的盘子，每次只能移动一个盘子，并且大盘子不能放在小盘子上面。

4. **二分查找**：在有序数组中查找特定元素，采用递归的方式实现。

int binarySearch(int arr[], int left, int right, int x);

5. **深度优先搜索（DFS）**：在图或树中找到从起点到终点的路径，使用递归探索所有可能路径。