如何掌握高效递归思维方法？分享递归解题思路及斐波那契实现

Hey folks, I’ve been hacking away at recursion practice problems today. I can usually tell when a problem is a good candidate for recursion and eventually get the solution working, but it always takes longer than I’d like—mostly because I have to consciously flip my brain into that recursive way of thinking.

I figured I’d walk through my thought process for tackling recursive problems, using Fibonacci number calculations as a concrete example. Let’s look at two implementations for finding the Fibonacci number at a specific position: the standard findFabNumber() and my own optimized take, findLastFabNumber().

Quick Fibonacci Refresher #

First, a quick reminder: the Fibonacci sequence starts with 0 and 1, and each subsequent number is the sum of the two before it. So:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) for any n > 1

The Standard Recursive Approach: findFabNumber() #

Here’s what the classic recursive implementation looks like (I’m using JavaScript, but the logic translates to most languages):

function findFabNumber(n) {
  // Base cases: smallest problems we can solve directly
  if (n === 0) return 0;
  if (n === 1) return 1;
  
  // Recursive step: break into smaller subproblems
  return findFabNumber(n - 1) + findFabNumber(n - 2);
}

This works, but it’s pretty inefficient—for larger values of n, it recalculates the same Fibonacci numbers over and over (like fib(3) gets computed multiple times when finding fib(5)).

My Optimized Version: findLastFabNumber() #

I wanted to cut down on those redundant calculations, so I built a tail-recursive version that tracks the last two values in the sequence as we go:

function findLastFabNumber(n, prev = 0, curr = 1) {
  // Same base cases as before
  if (n === 0) return prev;
  if (n === 1) return curr;
  
  // Recursive step: update the tracked values and decrement n
  return findLastFabNumber(n - 1, curr, prev + curr);
}

How I Worked Through This #

Let me break down the thinking that led to this code:

• Start with base cases – I always nail these down first, since they’re the foundation of any recursive solution. No base cases = infinite loops or wrong answers.
• Spot the inefficiency – The standard approach’s repeated calculations bugged me. I thought: "Instead of recalculating past values, what if I carry them along with each recursive call?"
• Add state-tracking parameters – I added prev and curr to keep track of the last two numbers in the sequence. Each call updates these: prev becomes the old curr, and curr becomes the sum of the old prev and curr.
• Test with small inputs – I manually walked through findLastFabNumber(5) to make sure it worked: it counts down from 5 to 1, updating the values each time, and finally returns 5 (which is correct, since fib(5) is 5).

My Go-To Recursive Problem-Solving Steps #

From this example, here’s the general workflow I follow for any recursive problem:

• 1. Define base cases first – These are the simplest scenarios where you know the answer immediately (no recursion needed). Always validate these with small inputs first.
• 2. Break the problem into smaller subproblems – Ask yourself: "How can I express the solution for n using the solution for a smaller n (like n-1 or n-2)?"
• 3. Track state if needed – If the naive recursive approach is inefficient, consider adding parameters to carry necessary state through each call (like prev and curr here).
• 4. Test incrementally – Start with tiny inputs to verify your base cases and recursive steps work, then move to larger values.
• 5. Intentionally switch to recursive mode – This is the hardest part for me. I have to stop thinking about loops and start thinking about "what’s the smallest version of this problem, and how do I build up from there?"

It’s still a mental shift every time, but breaking it down into these steps has helped me get more comfortable (and faster) with recursion.

内容的提问来源于stack exchange，提问作者Indiver kumar