如何学习递归呢？

Recursion, at its core, is a powerful programming concept that allows you to solve problems by breaking them down into smaller, identical subproblems. Instead of using loops, you define a function that calls itself. While it might sound a bit mindbending at first, with a systematic approach and plenty of practice, you'll find it to be an incredibly elegant and efficient way to tackle many coding challenges.

Let's dive in, and I'll try to explain it as clearly as possible, as if we were sitting down together to figure this out.

The Core Idea: Breaking Down the Problem

Imagine you have a really big task to do. Recursion is like saying, "Okay, this task is too big to do all at once. But, if I can figure out how to do a slightly smaller version of the same task, I can keep doing that until the task is so small I can handle it easily. Then, I'll just put all those small solutions back together."

Think about it like stacking Russian nesting dolls. To open the whole set, you open the biggest doll. Inside, there's a smaller doll. You repeat the same action: open the smaller doll. You keep going until you find the tiniest doll that can't be opened further. That's your "base case." Once you have that smallest doll, you can then close them all up, one by one, in reverse order.

The Two Essential Ingredients of Recursion

Every recursive function needs two key components to work correctly and avoid infinite loops:

1. The Base Case (or Stopping Condition): This is the simplest possible version of the problem, the one that can be solved directly without making another recursive call. It's the "tiny nesting doll" that doesn't open. Without a base case, your function would keep calling itself forever, leading to a "stack overflow" error (think of it as your computer getting overwhelmed with too many nested instructions).

2. The Recursive Step (or Recursive Call): This is where the magic happens. The function calls itself but with a modified input that moves it closer to the base case. It's breaking the problem down into a smaller, identical subproblem. You're essentially saying, "To solve this problem, I need to solve a slightly simpler version of it first."

A Classic Example: Calculating Factorial

Let's use a really common example to illustrate this: calculating the factorial of a nonnegative integer. The factorial of a number `n`, denoted as `n!`, is the product of all positive integers less than or equal to `n`.

`5! = 5 4 3 2 1 = 120`
`3! = 3 2 1 = 6`
`1! = 1`
By convention, `0! = 1`

Now, let's think about how we could define factorial recursively.

What's the base case? The simplest factorial we know is `0!` or `1!`, which is just `1`. So, if the input `n` is `0` or `1`, we can immediately return `1`.

What's the recursive step? How can we express `n!` in terms of a smaller factorial?
We know `5! = 5 4 3 2 1`.
Notice that `4 3 2 1` is just `4!`.
So, `5! = 5 4!`.
In general, `n! = n (n1)!` for `n > 0`.

This `n! = n (n1)!` is our recursive step. We're defining `n!` in terms of `(n1)!`, which is a smaller version of the same problem.

Here's how you might write this in Python (it's quite similar in many other languages):

```python
def factorial(n):
1. The Base Case: When to stop?
if n == 0 or n == 1:
return 1
2. The Recursive Step: Break down the problem
else:
return n factorial(n 1)

Let's test it
print(factorial(5)) Output: 120
print(factorial(0)) Output: 1
print(factorial(3)) Output: 6
```

Let's trace `factorial(4)`:

1. `factorial(4)` is called. `n` is 4.
2. Is `n == 0` or `n == 1`? No (4 is not 0 or 1).
3. So, it goes to the `else` block: `return 4 factorial(3)`.
Now, `factorial(3)` needs to be calculated.
4. `factorial(3)` is called. `n` is 3.
5. Is `n == 0` or `n == 1`? No.
6. So, it goes to the `else` block: `return 3 factorial(2)`.
Now, `factorial(2)` needs to be calculated.
7. `factorial(2)` is called. `n` is 2.
8. Is `n == 0` or `n == 1`? No.
9. So, it goes to the `else` block: `return 2 factorial(1)`.
Now, `factorial(1)` needs to be calculated.
10. `factorial(1)` is called. `n` is 1.
11. Base Case Hit! Is `n == 0` or `n == 1`? Yes!
12. `factorial(1)` returns `1`.
13. Back to `factorial(2)`: it was waiting for `factorial(1)`. Now it can complete: `return 2 1`, which is `2`.
14. Back to `factorial(3)`: it was waiting for `factorial(2)`. Now it can complete: `return 3 2`, which is `6`.
15. Back to `factorial(4)`: it was waiting for `factorial(3)`. Now it can complete: `return 4 6`, which is `24`.

And that's how `factorial(4)` returns `24`. See how the problem gets broken down and then the results are combined on the way back up?

How to Approach Learning Recursion

1. Understand the Two Pillars: Always, always, always identify your base case and your recursive step. If you miss one, you're in trouble.

2. Trace, Trace, Trace! This is crucial. When you write a recursive function, or look at an example, don't just read it. Mentally (or on paper) trace how the function calls itself with different inputs until it hits the base case, and then how the results propagate back. Use a debugger if it helps!

3. Start Simple: Tackle wellknown recursive problems first. Factorial is great. Others include:
Sum of numbers: `sum(n) = n + sum(n1)` with base case `sum(0) = 0`.
Fibonacci sequence: `fib(n) = fib(n1) + fib(n2)` with base cases `fib(0)=0` and `fib(1)=1`. (Be careful, the naive recursive Fibonacci is very inefficient due to repeated calculations, but it's a good conceptual example.)
Traversing treelike structures: This is where recursion truly shines. Think about how to process a file system (each folder can contain files and other folders), or how to search through a binary tree.

4. Visualize the Call Stack: Imagine each function call being placed on a stack. When a function calls itself, a new "frame" is pushed onto the stack. When a function returns, its frame is popped off. The base case is when you start popping off frames. This mental model helps understand the flow.

5. Compare with Iteration: For many problems that can be solved recursively, there's an iterative (loopbased) solution too. Try to solve the same problem both ways. This helps you understand the tradeoffs and the fundamental logic. Sometimes recursion is more natural; sometimes iteration is more efficient.

6. Don't Be Afraid to Draw: When dealing with more complex recursive structures (like trees or linked lists), drawing them out and tracing the function's path on the drawing can be incredibly helpful.

7. Practice with Different Data Structures:
Arrays/Lists: Think about operations on subarrays. For example, finding the maximum element in an array: `max(array) = max(first_element, max(rest_of_the_array))`.
Strings: Reversing a string: `reverse("hello") = reverse("ello") + 'h'`.
Trees: This is where recursion is almost always the most elegant way. To process a node, you often process its left child and then its right child.

Potential Pitfalls to Watch Out For

Missing Base Case: We've covered this – it leads to infinite recursion.
Incorrectly Moving Towards Base Case: If your recursive call doesn't actually simplify the problem (e.g., `n + factorial(n)` instead of `n factorial(n1)`), you'll never reach the base case.
Overlapping Subproblems (Inefficiency): As with the naive Fibonacci, some recursive solutions recalculate the same values many times. This can be fixed with techniques like memoization (caching results), but it's something to be aware of.
Stack Overflow: If your recursion goes too deep (e.g., factorial of a very large number, or a poorly designed recursion), you can run out of memory on the call stack.

When is Recursion Particularly Useful?

Recursion is a natural fit for problems that have a selfsimilar structure. This often appears in:

Tree and Graph Traversal: Searching, sorting, and manipulating data in treelike structures.
Divide and Conquer Algorithms: Problems like Merge Sort and Quick Sort break a problem into smaller parts, solve them recursively, and then combine the results.
Fractals: Geometric shapes that exhibit selfsimilarity at different scales.
Parsing and Grammars: Understanding the structure of languages.

Putting It Into Practice

The best way to learn recursion is to do it. Pick a problem, try to define the base case, try to define the recursive step, and then write the code. Don't get discouraged if it doesn't work perfectly the first time. That's part of the process! Trace it, debug it, and refine it.

Think of it like learning a new language. At first, you focus on individual words and simple sentences. Then, you start combining them, and eventually, you can construct complex thoughts. Recursion is no different. Start with the simple building blocks, and with practice, you'll be able to build incredibly elegant solutions.

谢邀。

我们从小，就一直听着一个递归的故事长大：从前有座山，山里有座庙，庙里有个老和尚在讲故事，老和尚在讲：从前有座山，山里有座庙.......

关于递归的学习，有一个很经典的例子：在学习递归，首先，你应该学习一下，什么是递归。

递归是一种思考问题、描述问题的方法。一个基本的思想就是，把一个复杂问题化为一系列简单问题的重复。

我们以遍历树为例，遍历一棵树，首先先从根节点开始，首先先遍历根节点下的每一个子节点，然后，再把这些子节点，作为一个新的树的根节点，重复上述的遍历过程。伪代码如下

tree_travel( tree_node root )
{
foreach( node in root.children )
tree_travel( node );
}

通过这个例子，我们可以发现，递归还有一个特点，就是问题的规模和解决问题的方法没有关系，或者只是一个参数没有很大的影响。递归所做的，就是把复杂的问题一级一级的展开，使得每一级的处理方法都一模一样。我们在讲一下汉诺塔的例子，我们假设三个柱子分别是ABC，盘子由小到大分别用1、2、3...表示。

对于两个盘子的情况：

首先，先将1盘子从A移动到B，然后将2盘子从A移动到C，最后将1盘子从B移动到C。

三个盘子的情况：

首先，先将1、2盘子从A移动到B，然后将3盘子从A移动到C，最后将1、2盘子从B移动到C。

那么1、2两个盘子怎么样从A移动到B，再从B移动到C呢？其实，这个问题我们刚刚在举两个盘子的例子的时候已经解决过了。

那么，对于64个盘子的情况，我们也可以很容易解决。

首先，先将1，2，3......63盘子从A移动到B，然后将64盘子从A移动到C，最后将1，2，3......63盘子从B移动到C。

而对于1，2，3.....63这63个盘子怎么样从A移动到B，再从B移动到C，我们在解决63个盘子的情况的时候，已经处理过了。

关于递归，上面有几位讲得也比较好，我也就不赘述了。

关于另一个问题，为什么平时的项目中，很少见到递归。这个是因为，一个正经的程序，是应当尽量少或者尽可能不出现递归的程序。在程序中使用递归，除了能够少写几行代码，给程序员带来一点点方便以外，没有别的太多的好处，甚至有时候是有害的。

首先，你应当明确一点，所有的递归程序，都可以改写成非递归的方法，而在这个非递归的方法中，你不得不维护一个栈，来完成原来程序调用栈的能够，从而使得程序能达到跟递归一样的效果。为什么说递归是不好的呢，那是因为调用栈的大小是有限的，而递归的深度，有的时候是不好估计的。一旦递归的深度过大，使得调用栈溢出了，那么对程序的影响是非常大的。而在非递归的方法中，由于栈由自己维护，即使“递归”的深度过大，程序也在你的控制范围之内，可以自己中断“递归”过程并作相应的处理。

然后，递归使得程序书写的效率提高，但并不意味着执行的效率会提高，比如那个斐波那契数列的例子，你自己算一下就会发现有将近一般的计算式重复的，比如那个fibo(n-2)是会计算两次的，而越深的项重复次数就会越多。除了这个问题外，递归程序的执行效率一般也不必循环高，因为在栈上开辟新空间、分配局部变量的时间也是不小的。你可以自己尝试的写一下这样的程序，和@陈甫鸼 同学的那个程序一样，还是那个斐波那契数列的例子，也还是python，非递归的解法。数字不用很大，求斐波那契数列的第50项，递归的方法就已经很难在你能容忍的时间内完成了。

def fibo( n ):
if n <= 0:
raise Exception()
elif n == 1:
return 0
elif n == 2:
return 1
else:
a = 0
b = 1
s = 0
while n > 2:
s = b + a
a = b
b = s
n -= 1
return s

最后，关于递归的建议，一定要会递归的解决问题，但是要避免写递归的程序。