给定前两项的斐波那契数列第n项求解及JavaScript递归/非递归实现

Got it, let's work through this problem. You're dealing with a Fibonacci-style sequence where instead of starting with 0 and 1, you get two custom initial numbers, and need to find the nth term. Let's cover both recursive and iterative (non-recursive) approaches—each has its own tradeoffs, so I'll break them down clearly.

Recursive Approach #

Recursion follows the core logic of Fibonacci sequences directly: each term is the sum of the two preceding ones. The base cases here are when n is 1 (return the first initial number) or n is 2 (return the second initial number). For any n > 2, we recursively calculate the sum of the (n-1)th and (n-2)th terms.

Note: Recursion can be inefficient for large n because it recalculates the same terms over and over. But it's great for understanding the sequence's mathematical definition.

function getNthTermRecursive(first, second, n) {
    // Base cases: return the initial values for n=1 and n=2
    if (n === 1) return first;
    if (n === 2) return second;
    
    // Recursive case: sum of the two previous terms
    return getNthTermRecursive(first, second, n - 1) + getNthTermRecursive(first, second, n - 2);
}

// Test the example: initial terms 2,4, 4th term should be 10
console.log(getNthTermRecursive(2, 4, 4)); // Output: 10

Non-Recursive (Iterative) Approach #

Iteration is the better choice for performance, especially with large n values. We'll use a loop to calculate each term from the third one up to the nth, keeping track of the last two terms as we go. This avoids redundant calculations and runs in O(n) time with O(1) space.

function getNthTermIterative(first, second, n) {
    // Handle base cases first
    if (n === 1) return first;
    if (n === 2) return second;
    
    // Initialize variables to track the last two terms
    let prevPrev = first;
    let prev = second;
    let current;
    
    // Loop from 3 to n to compute each term
    for (let i = 3; i <= n; i++) {
        current = prevPrev + prev;
        // Shift the variables for the next iteration
        prevPrev = prev;
        prev = current;
    }
    
    return current;
}

// Test the example
console.log(getNthTermIterative(2, 4, 4)); // Output: 10

Extra: Memoized Recursive Approach (Optimized) #

If you want the readability of recursion but better performance, you can add memoization (caching computed terms) to avoid redundant calculations. This brings the time complexity down to O(n) as well.

function getNthTermMemoized(first, second, n) {
    const memo = { 1: first, 2: second };
    
    function helper(n) {
        if (memo[n]) return memo[n];
        memo[n] = helper(n - 1) + helper(n - 2);
        return memo[n];
    }
    
    return helper(n);
}

// Test the example
console.log(getNthTermMemoized(2, 4, 4)); // Output: 10

All three approaches will correctly compute the nth term for your custom Fibonacci sequence. For most practical purposes, the iterative approach is the best bet—it's fast and uses minimal memory.

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