将多个递归调用转换为尾递归

Question

只是想知道这样的函数是否可以尾递归完成。我觉得很难，因为它调用了两次。

这是我在 javascript 中的非尾递归实现。（是的，我知道大多数 javascript 引擎不支持 TCO，但这只是理论上的。）目标是找到给定数组（arr）的特定长度（大小）的所有子列表。例如：getSublistsWithFixedSize([1,2,3] ,2) returns [[1,2], [1,3], [2,3]]

function getSublistsWithFixedSize(arr, size) {
    if(size === 0) {
        return [[]];
    }
    if(arr.length === 0 ) {
        return [];
    }
    let [head, ...tail] = arr;
    let sublists0 = getSublistsWithFixedSize(tail, size - 1);
    let sublists1 = getSublistsWithFixedSize(tail, size);
    let sublists2 = sublists0.map(x => {
        let y = x.slice();
        y.unshift(head);
        return y;
    });

    return  sublists1.concat(sublists2);
}

Answer 1

其中一种方法是使用连续传递样式。在这种技术中，一个额外的参数被添加到你的函数来指定如何继续计算

下面我们用/**/

强调每个尾调用

function identity(x) {
/**/return x;
}

function getSublistsWithFixedSize(arr, size, cont = identity) {
    if(size === 0) {
/**/   return cont([[]]);
    }
    if(arr.length === 0 ) {
/**/    return cont([]);
    }
    let [head, ...tail] = arr;
/**/return getSublistsWithFixedSize(tail, size - 1, function (sublists0) {
/**/    return getSublistsWithFixedSize(tail, size, function (sublists1) {
            let sublists2 = sublists0.map(x => {
                let y = x.slice();
                y.unshift(head);
                return y;
            });
/**/        return cont(sublists1.concat(sublists2));
        });
    });
}

console.log(getSublistsWithFixedSize([1,2,3,4], 2))
// [ [ 3, 4 ], [ 2, 4 ], [ 2, 3 ], [ 1, 4 ], [ 1, 3 ], [ 1, 2 ] ]

你可以把延续想像成我们发明自己的 return 机制；这里只是一个函数，不是一个特殊的语法。

如果我们在调用站点指定我们自己的延续，这可能会更明显

getSublistsWithFixedSize([1,2,3,4], 2, console.log)
// [ [ 3, 4 ], [ 2, 4 ], [ 2, 3 ], [ 1, 4 ], [ 1, 3 ], [ 1, 2 ] ]

甚至

getSublistsWithFixedSize([1,2,3,4], 2, sublists => sublists.length)
// 6

使用更简单的函数可能更容易看到该模式。想想著名的 fib

const fib = n =>
  n < 2
    ? n
    : fib (n - 1) + fib (n - 2)

console.log (fib (10))
// 55

下面我们将其转换为continuation-passing风格

const identity = x =>
  x

const fib = (n, _return = identity) =>
  n < 2
    ? _return (n)
    : fib (n - 1, x =>
        fib (n - 2, y =>
          _return (x + y)))

fib (10, console.log)
// 55

console.log (fib (10))
// 55

我想指出，对于这个特定问题，不需要使用 .slice 和 .unshift。在分享替代方案之前，我会给你一个机会想出一些其他的解决方案。

编辑

您重写了您的程序，但正如您所指出的，仍有可以改进的地方。我认为您最困难的一个领域是使用数组变异操作，例如 arr[0] = x 或 arr.push(x)、arr.pop() 和 arr.unshift(x)。当然，您可以使用这些操作来达到预期的结果，但在函数式程序中，我们以不同的方式考虑事情。我们不是通过覆盖旧值来破坏旧值，而是只读取值并构造 new 值。

我们还将避免高级操作，例如 Array.fill 或 uniq（不确定您选择了哪种实现），因为我们可以使用递归自然地构建结果。

你的递归函数的归纳推理是完美的，所以我们不需要调整它

如果size为零，return空结果[[]]
如果输入数组为空，return一个空集，[]
否则 size 至少是一个，我们至少有一个元素 x - 获取小一号的子列表 r1，获取相同大小的子列表 r2, return r1 和 r2 的组合结果在 r1

x

我们可以用一种直接的方式对其进行编码。请注意与您的原始程序相比在结构上的相似性。

const sublists = (size, [ x = None, ...rest ], _return = identity) =>
  size === 0
    ? _return ([[]])

  : x === None
    ? _return ([])

  : sublists              // get sublists of 1 size smaller, r1
      ( size - 1
      , rest
      , r1 =>
          sublists        // get sublists of same size, r2
            ( size
            , rest
            , r2 =>
                _return   // return the combined result
                  ( concat
                      ( r1 .map (r => prepend (x, r)) // prepend x to each r1
                      , r2
                      )
                  )
            )
      )

我们用一个 size 和一个输入数组

来调用它

console.log (sublists (2, [1,2,3,4,5]))
// [ [ 1, 2 ]
// , [ 1, 3 ]
// , [ 1, 4 ]
// , [ 1, 5 ]
// , [ 2, 3 ]
// , [ 2, 4 ]
// , [ 2, 5 ]
// , [ 3, 4 ]
// , [ 3, 5 ]
// , [ 4, 5 ]
// ]

最后，我们提供依赖identity、None、concat和prepend - 下面concat是提供功能接口的例子到一个对象的方法。这是用于增加程序中函数重用并同时提高可读性的众多技术之一

const identity = x =>
  x 

const None =
  {}

const concat = (xs, ys) =>
  xs .concat (ys)

const prepend = (value, arr) =>
  concat ([ value ], arr)

您可以在下面的浏览器中运行完整程序

const identity = x =>
  x 
  
const None =
  {}

const concat = (xs, ys) =>
  xs .concat (ys)

const prepend = (value, arr) =>
  concat ([ value ], arr)

const sublists = (size, [ x = None, ...rest ], _return = identity) =>
  size === 0
    ? _return ([[]])
  
  : x === None
    ? _return ([])

  : sublists             // get sublists of 1 size smaller, r1
      ( size - 1
      , rest
      , r1 =>
          sublists       // get sublists of same size, r2
            ( size
            , rest
            , r2 =>
                _return   // return the combined result
                  ( concat
                      ( r1 .map (r => prepend (x, r)) // prepend x to each r1
                      , r2
                      )
                  )
            )
      )

console.log (sublists (3, [1,2,3,4,5,6,7]))
// [ [ 1, 2, 3 ]
// , [ 1, 2, 4 ]
// , [ 1, 2, 5 ]
// , [ 1, 2, 6 ]
// , [ 1, 2, 7 ]
// , [ 1, 3, 4 ]
// , [ 1, 3, 5 ]
// , [ 1, 3, 6 ]
// , [ 1, 3, 7 ]
// , [ 1, 4, 5 ]
// , [ 1, 4, 6 ]
// , [ 1, 4, 7 ]
// , [ 1, 5, 6 ]
// , [ 1, 5, 7 ]
// , [ 1, 6, 7 ]
// , [ 2, 3, 4 ]
// , [ 2, 3, 5 ]
// , [ 2, 3, 6 ]
// , [ 2, 3, 7 ]
// , [ 2, 4, 5 ]
// , [ 2, 4, 6 ]
// , [ 2, 4, 7 ]
// , [ 2, 5, 6 ]
// , [ 2, 5, 7 ]
// , [ 2, 6, 7 ]
// , [ 3, 4, 5 ]
// , [ 3, 4, 6 ]
// , [ 3, 4, 7 ]
// , [ 3, 5, 6 ]
// , [ 3, 5, 7 ]
// , [ 3, 6, 7 ]
// , [ 4, 5, 6 ]
// , [ 4, 5, 7 ]
// , [ 4, 6, 7 ]
// , [ 5, 6, 7 ]
// ]

Answer 2

这是我借助累加器的解决方案。它远非完美，但它确实有效。

function getSublistsWithFixedSizeTailRecRun(arr, size) {
    let acc= new Array(size + 1).fill([]);
    acc[0] = [[]];
    return getSublistsWithFixedSizeTailRec(arr, acc);
}


function getSublistsWithFixedSizeTailRec(arr, acc) {
    if(arr.length === 0 ) {
        return acc[acc.length -1];
    }
    let [head, ...tail] = arr;
    //add head to acc
    let accWithHead = acc.map(
        x => x.map(
            y => {
                let z = y.slice()
                z.push(head);
                return z;
            }
        )
    );
    accWithHead.pop();
    accWithHead.unshift([[]]);

    //zip accWithHead and acc
    acc = zipMerge(acc, accWithHead);

    return getSublistsWithFixedSizeTailRec(tail, acc);
}

function zipMerge(arr1, arr2) {
    let result = arr1.map(function(e, i) {
        return uniq(e.concat(arr2[i]));
    });
    return result;
}

将多个递归调用转换为尾递归

Convert multiple recursive calls into tail-recursion

javascript

recursion

tail-recursion