从生命内部递归

Question

我有一段代码，它通过在给定字符串的字母之间放置空格来生成所有可能的字符串，代码使用递归来实现这一点。下面是我的代码(这是一个C++源，我已经适应了JavaScript，它的工作原理与预期一样)：

    var genStringsUtil = function (str,buf,i,j,n){
      if(n == i){
        buf[j] = " ";
        console.log(buf.join(""));
        return;
      }
        buf[j] = str[i];
        genStringsUtil (str,buf,i+1,j+1,n);
        buf[j] = " ";
        buf[j+1] = str[i];
        genStringsUtil (str,buf,i+1,j+2,n);
    }

   var genStrings = function(s){
      var str = s;
      var n =str.length;
      var buf = [];
      buf[0] = str[0];

      genStringsUtil (str,buf,1,1,n);
    };

   function main(){
    genStrings("ABCDE");
   }

   main();

现在，我对它做了这样的修改，它仍然有效：

var genStrings = function (str,buf,i,j,n){
  if(n == i){
    buf[j] = " ";
    console.log(buf.join(""));
    return;
  }
  buf[j] = str[i];
  genStrings (str,buf,i+1,j+1,n);
  buf[j] = " ";
  buf[j+1] = str[i];
  genStrings (str,buf,i+1,j+2,n);
}

!function(s){
  var str = s;
  var n =str.length;
  var buf = [];
  buf[0] = str[0];

  genStrings (str,buf,1,1,n);
}("ABCDE");

但是，当我将最后一部分改为(带括号的生活)时：

(function(s){
  var str = s;
  var n =str.length;
  var buf = [];
  buf[0] = str[0];

  genStrings (str,buf,1,1,n);
})("ABCDE");

我收到一个错误：

TypeError: J是未定义的

如果我将结束括号放在("ABCDE")后面，如下所示：

(function(s){
  var str = s;
  var n =str.length;
  var buf = [];
  buf[0] = str[0];

  genStrings (str,buf,1,1,n);
}("ABCDE"));

我又犯了一个错误：

TypeError: genStrings不是一个函数

我一直以为IIFE是用！或者括号是一样的，但显然不是。所以我的问题是，在这三种情况下，到底发生了什么不同的事情？递归是问题吗？

我希望我的信息不要太长。

谢谢你的帮助。

Answer 1

C++有几个JavaScript没有的限制。有无数种方法可以在JavaScript中编码您的函数，但是这里有一种使用续传式的方法。

在这种风格中，第二个参数send将添加到genStrings函数的签名中，并接受默认的identity延续。这有效地将return转化为用户可配置的功能。之所以使用send名称，是因为return是一个保留关键字。

这个实现的另一个值得注意的方面是使用函数样式的属性参考透明度，其中函数总是对相同的输入返回相同的结果。由于递归是一种功能继承，因此我们肯定会维护该属性以获得最佳结果。

​

const identity = x =>
  x
  
const concat = (xs, ys) =>
  xs .concat (ys)
  
const genStrings = ([ char, ...rest ], send = identity) =>
  // base case: return empty set
  char === undefined
    ? send ([])

  // if there is only one char, return singleton result
  : rest.length === 0
    ? send ([char])
  
  // otherwise recur on rest
  // 1) add char plus space to each combination
  // 2) add char without space to each combination
  // 3) concat the result
  : genStrings
      ( rest
      , combs =>
          send ( concat ( combs .map (c => char + ' ' + c)
                        , combs .map (c => char + c)
                        )
               )
      )

console.log (genStrings ('ABC'))
// [ 'A B C'
// , 'A BC'
// , 'AB C'
// , 'ABC'
// ]

​

您还会注意到，不需要跟踪其他几个状态变量，如n、i和j，也不需要使用不同的值来增加它们。使用较少表达式和变量的程序更易于维护和调试。

genStrings也适用于更大的输入，如问题中的示例。

console.log (genStrings ('ABCDE'))
// [ 'A B C D E'
// , 'A B C DE'
// , 'A B CD E'
// , 'A B CDE'
// , 'A BC D E'
// , 'A BC DE'
// , 'A BCD E'
// , 'A BCDE'
// , 'AB C D E'
// , 'AB C DE'
// , 'AB CD E'
// , 'AB CDE'
// , 'ABC D E'
// , 'ABC DE'
// , 'ABCD E'
// , 'ABCDE'
// ]

我们还小心地使genStrings成为一个总程序，这意味着它返回一个有效的结果，即使输入字符串是空的。

console.log (genStrings (''))
// []

因为genStrings是使用连续传递样式定义的，所以我们也可以在调用站点上指定用户可配置的延续。

genStrings ('ABC', console.log)
// [ 'A B C', 'A BC', 'AB C', 'ABC' ]

genStrings ('ABC', combs => combs.length)
// 4

genStrings ('ABC', combs => combs .join (', '))
// 'A B C, A BC, AB C, ABC'

由于genStrings是一个纯函数，具有定义良好的域(输入)和协域(输出)，因此不需要立即调用函数表达式(IIFE)，更不用说调试一个函数表达式了。

我开始研究它，但是我不明白rest.length、=== 0和genStrings之前的冒号语法是什么？

?:是JavaScript的条件算子，也称为三元操作符。语法是conditionExpression ? trueExpression : falseExpression。当conditionExpression计算为特鲁西值时，只计算trueExpression，跳过falseExpression。相反，如果conditionExpression计算值为非真实值，则跳过trueExpression，只计算falseExpression。

它与if-else语句的表达式等价，但与所有其他表达式一样，它的计算结果不是依赖于副作用，而是值。

// conditional expression
let someValue =
  n === 0                // expression
    ? "n is zero"        // expression
    : "n is not zero"    // expression

// if statement
let someValue
if (n === 0)
  someValue = "n is zero"         // side effect
else
  someValue = "n is not zero"     // side effect

上面，if语句更冗长，并且依赖于副作用来设置someValue的值。条件表达式的计算结果为值，可以直接分配给变量。

与if-else if-else语句类似，条件表达式也可以链接在一起。这是您在上面的答案中看到的语法。

const animalSound =
  animal === "dog"    // if
    ? "woof"          // then

  : animal === "cat"  // else if
    ? "meow"          // then

  : "unknown"         // else

它帮助我看到以多种方式表示的相同程序。下面，我们使用祈使式if语句重写原来的答案。

​

const identity = x =>
  x

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

const genStrings = ([ char, ...rest ], send = identity) =>
{ if (char === undefined)
    return send ([])

  else if (rest.length === 0)
    return send ([char])

  else
    return genStrings
             ( rest
             , combs =>
                 send ( concat ( combs .map (c => char + ' ' + c)
                               , combs .map (c => char + c)
                               )
                      )
             )
}

console.log (genStrings ('ABC'))
// [ 'A B C'
// , 'A BC'
// , 'AB C'
// , 'ABC'
// ]

​