类斐波那契函数（fx(n)=fx(n-3)+fx(n-2)）尾递归版本实现求助

Hey there! Let's figure out where things went wrong with your tail-recursive implementation, and fix it up properly.

First, clarify the problem we're solving #

Your target recurrence relation is:
fx(n) = fx(n-3) + fx(n-2)
With base cases defined as:

• fx(0) = 0
• fx(1) = 1
• fx(2) = 1

Your non-tail-recursive code works because it directly follows this definition, but it’s not optimized for tail calls—since the final operation is adding two recursive results, not a single recursive call as the last step.

What’s wrong with your current factor3/factor2 approach? #

Your idea of splitting the problem into two separate functions doesn’t align with how tail recursion works. Here’s why:

1. Tail recursion requires the final operation to be the recursive call: Your approach would still need to add the results of factor3 and factor2, which makes the top-level call non-tail-recursive.
2. The internal logic is disconnected from the recurrence: For example, return factor3(p1, n + a) doesn’t track the actual values of fx(k) needed to compute the next term. The parameter a’s purpose is unclear, and the update step doesn’t follow the rule fx(n) = fx(n-3) + fx(n-2).

Correct Tail-Recursive Implementation #

The key to tail-recursive solutions for linear recurrences is to track necessary previous values as parameters, so each recursive call can compute the next term and update those state values. For your recurrence, we need to keep track of the last three sequence values (since each term depends on terms two and three positions back).

Here’s a working implementation matching your code’s style:

// Main function to trigger the tail-recursive helper
Long doCalc(long n) {
    if (n < 0) {
        throw new IllegalArgumentException("n must be a non-negative integer");
    }
    // Initialize with base cases: a=fx(0), b=fx(1), c=fx(2)
    return tailCalc(n, 0L, 1L, 1L);
}

// Tail-recursive helper function (all logic lives here)
private Long tailCalc(long currentN, long a, long b, long c) {
    // Base cases: return the precomputed base value directly
    if (currentN == 0) return a;
    if (currentN == 1) return b;
    if (currentN == 2) return c;
    
    // Compute the next term: fx(k+3) = fx(k) + fx(k+1) = a + b
    // Shift the tracked values forward for the next recursion:
    // New a = fx(k+1) (old b), new b = fx(k+2) (old c), new c = fx(k+3) (a+b)
    return tailCalc(currentN - 1, b, c, a + b);
}

How this works (example walkthrough) #

Let’s compute fx(4) to see the state updates:

1. Call tailCalc(4, 0, 1, 1) → currentN isn’t a base case, so compute new term 0+1=1, then call tailCalc(3, 1, 1, 1)
2. Call tailCalc(3, 1, 1, 1) → compute new term 1+1=2, then call tailCalc(2, 1, 1, 2)
3. Call tailCalc(2, 1, 1, 2) → currentN=2, return c=2 (which is correct, since fx(4)=fx(1)+fx(2)=1+1=2)

Each recursive call is the final operation of the function, so it qualifies as tail recursion—compilers/interpreters can optimize this to reuse the same stack frame, avoiding stack overflow for large n.

Quick notes #

• Added a check for negative n to make the function more robust (your original code didn’t handle this)
• Uses long values consistently to avoid overflow for larger input values

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