当结合迭代与递归时，如何将递归转换为尾调用？（分数组合场景）

我已经写出了一道练习题的递归解决方案，但没法把它改成尾递归形式。核心疑问是：当迭代和递归结合时，怎么用尾调用实现递归？

这个问题可以归纳为以下三点：

• 在递归步骤中，需遍历当前步骤的所有可选选项；
• 探索每个选项时，需发起递归调用；
• 递归返回后，需判断是否找到解，再决定是否继续探索下一选项。

具体问题 #

给定目标值与分数列表，编写函数返回和为目标值的分数索引列表。

伪代码实现 #

Function findScoresThatReachTarget(target, scores):
    scoreIndexes = range(0, scores.length);
    return generateCombos([])

注：假设generateCombos可访问target、scores和scoreIndexes的闭包作用域

Function generateCombos(currentCombo):
    Iterate through the scores that are not already in the combo:
        newCombo = [...currentCombo, currentScore]
        if score of the newCombo is greater than target:
            Start the next iteration
        if score of the newCombo equals the target:
            Return the solution
        else
            potentialSolution = generateCombos(newCombo)
            if potentialSolution
                Return the solution
            else
                Start the next iteration

JavaScript实现 #

const _ = require('lodash');

function findScoresThatReachTarget(target, scores) {
    const scoreIndexes = _.range(0, scores.length);
    return generateCombos([]);

    function generateCombos(currentCombo) {
        const newScoreIndexes = _.difference(scoreIndexes, currentCombo);
        return findResult(newScoreIndexes, currentScoreIndex => {
            const newCombo = [...currentCombo, currentScoreIndex];
            const scoreOfNewCombo = calculateScoreOfCombo(newCombo);
            if (scoreOfNewCombo > target) {
                return; // 进入下一轮迭代
            } else if (scoreOfNewCombo === target) {
                return newCombo; // 找到解
            } else {
                const potentialSolution = generateCombos(newCombo);
                if (potentialSolution) {
                    return potentialSolution;
                }
            }
        });
    }
    
    // 类似Array.prototype.find，但返回的是函数计算后的结果而非数组元素
    function findResult(arr, func) {
        for(const i of arr){
            const result = func(i);
            if(result) {
                return result;
            }
        }
    }

    function calculateScoreOfCombo(combo) {
        return combo.reduce(
            (totalScore, scoreIndex) => totalScore + scores[scoreIndex],
            0
        );
    }
}

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