首页递归牛客题

递归牛客题

时间: 2025-03-12 21:19:35 浏览: 55

### 关于递归的牛客网编程题及其解法 #### 斐波那契数列问题斐波那契数列是一个经典的递归例子。虽然递归方法可以解决这个问题，但由于其效率低下，在处理较大数值时可能导致性能瓶颈[^1]。 ```cpp int Fibonacci(int n) { if (n <= 0) return 0; if (n == 1) return 1; return Fibonacci(n - 1) + Fibonacci(n - 2); } ``` 为了提高效率，可以通过迭代方式来计算斐波那契数列： ```cpp int Fibonacci_iterative(int n) { if (n <= 0) return 0; int a = 0, b = 1, c; for (int i = 2; i <= n; ++i) { c = a + b; a = b; b = c; } return (n >= 1) ? b : a; } ``` #### 阶乘计算阶乘也是另一个典型的递归应用场景。同样地，为了避免栈溢出等问题，建议采用非递归的方式实现更高效的解决方案。 ```cpp unsigned long long Factorial(unsigned int n){ unsigned long long result=1; while(n>1){ result*=n--; } return result; } ``` #### 汉诺塔问题汉诺塔问题是展示递归逻辑的经典案例之一。通过递归来模拟移动盘子的过程，可以使代码更加简洁易懂。 ```cpp void HanoiTower(int numDisks, char fromPeg, char toPeg, char auxPeg) { if(numDisks==1){ printf("Move disk %d from peg %c to peg %c\n",numDisks,fromPeg,toPeg); return ; } HanoiTower(numDisks-1,fromPeg,auxPeg,toPeg); printf("Move disk %d from peg %c to peg %c\n",numDisks,fromPeg,toPeg); HanoiTower(numDisks-1,auxPeg,toPeg,fromPeg); } ``` 上述几个例子展示了不同类型的递归应用以及相应的优化方案。值得注意的是，在实际开发过程中应权衡递归带来的清晰性和潜在的风险，选择最适合具体场景的方法。

阅读全文