如何快速将 '*' 重复 9 次？

如果是将 '*' 重复 8 次，一下子就可以想到这种快速算法：

'' + '' => ''
'' + '**' => '****'
'****' + '****' => Bingo!
用 JavaScript 代码实现

var n = 8;
var str = '*';
while ((n >>>= 1) > 0) {
  str += str;
}
console.log(str);

同样的算法可用于 16 次、32 次、64 次、1024 次...

但是如果是要求重复 9 次呢？这就需要调整一下上述的算法。

先抽象出一个函数 repeat: (str: string, n: number) => string:

repeat('', 3) => '**'
repeat('ab', 1) => 'ab'
repeat('abcd', 0) => ''
...
然后开始分析：

当 n 为偶数时：
repeat(str, n) <= repeat(str, n >>> 1) + repeat(str, n >>> 1)
比如：repeat('abc', 12) <= repeat('abc', 6) + repeat('abc', 6)
当 n 为奇数时，即 n - 1 为偶数：
repeat(str, n) <= str + repeat(str, n - 1)
比如：repeat('', 21) <= '' + repeat('*', 20)
当 n 为 1 时：repeat(str, 1) <= str
当 n 为 0 时：repeat(str, 0) <= ''
用 JavaScript 代码实现：

function repeat(str/*:string*/, n/*:number*/) {
  if (n === 0) return '';
  if (n === 1) return str;
  // `n` 为奇数
  if (n % 2) return str + repeat(str, n - 1);

  // `n` 为偶数，
  // 但是要把 `repeat(str, n >>> 1)` 缓存起来，
  // 以避免重复两次计算
  return (str = repeat(str, n >>> 1)) + str;
}