ジェネレータで再帰を制す

JavaScriptだと `function*` で宣言して `yield` で値を返すジェネレータ。これは何が便利なのか解説します。
JavaScriptで説明していきますが、最後に見るようにPython, Rubyでもジェネレータは使えます。


# ジェネレータとは？

## 例：自然数を無限に生成するジェネレータ

```natural-number-generator.js
function* createNaturalNumberGenerator() {
  let n = 1;
  while (true) {
    yield n;
    n += 1;
  }
}
 
const generator = createNaturalNumberGenerator();
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
```

```
1
2
3
4
5
```

- `function*`で定義される関数のことを**ジェネレータ関数**といい、
- ジェネレータ関数が返す値、つまり変数`generator`の値のことを**ジェネレータ**と言います

`for ... of`を使って呼び出すと、ジェネレータから値がなくなるまでループします。

```natural-number-generator2.js

function* createNaturalNumberGenerator() {
  let i = 1;
  while (true) {
    yield i;
    i += 1;
  }
}

const generator = createNaturalNumberGenerator();
for (let n of generator) {
  console.log(n);
}
```

と言っても自然数の場合は無限にあるので、無限に続きます。

```
1
2
3
4
5
...（無限につづく）
```

**[ポイント]**
**`createNaturalNumberGenerator`の中で無限ループしているけど、この関数が永久に戻らないわけではなく、`next()`を呼ぶごと、あるいは`for ...of`で1回ループを回るごとに1回`yield`が呼ばれて呼び出し元に戻っていることに注意してください。**

# そんなのクラスやクロージャでもできるよ

はい、確かにできます。

クラスを使う版

```class.js
class NaturalNumberGenerator {
  constructor() {
    this.n = 0;
  }

  get() {
    this.n += 1;
    return this.n;
  }
}

const g = new NaturalNumberGenerator();
console.log(g.get());
console.log(g.get());
console.log(g.get());
console.log(g.get());
```

しかし、この場合`this.n`という**今どこまで進んだかという状態**を自分で管理しなければならないことになります。
ジェネレータ関数を使うと、状態を自分で管理しなくて済むようになります。
まだ何のことか分からないと思いますので、次に具体的にメリットが分かる例を出します。

# 組み合わせ（nCr）を出力する関数（非ジェネレータ）

```combinations.js
function getCombinations(xs, r) {
  if (xs.length < r) {
    return [];
  }
  if (r == 1) {
    const result = [];
    for (let x of xs) {
      result.push([x]);
    }
    return result;
  }
  const x = xs[0];
  const xs_ = xs.slice(1);
  return getCombinations(xs_, r - 1).map(comb => [x, ...comb]).concat(getCombinations(xs_, r));
}

console.log(getCombinations([1, 2, 3, 4], 2));
```

```
[ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]
```

- 中で自分自身を2回呼び出している2重再帰
- パスカルの三角形を素直にアルゴリズム化したのがこの実装

![image.png](https://qiita-image-store.s3.amazonaws.com/0/79394/b32e5496-1618-8d75-2d1a-4dac77ae9aa6.png)

- [自分自身を1回しか呼び出さない実装](https://github.com/aoyama-val/es6-generator/blob/master/combinations2.js)もあり、そっちの方が効率はいいけど、こっちの方が発想は素直かと


- **問題点**
    - 入力が大きくなると結果の配列が大きくなり、メモリを圧迫する
    - `50C10 == 10272278170` （102億！）
    - **試しにさっきのプログラムでやってみると返ってこないです**

# ジェネレータなら

- さっきの関数とアルゴリズムは同じで、ジェネレータで書き換えたもの

```combinations-generator.js
function* createCombinationGenerator(xs, r) {
  if (xs.length < r) {
    return;
  }
  if (r == 1) {
    for (let x of xs) {
      yield [x];
    }
    return;
  }
  const x = xs[0];
  const xs_ = xs.slice(1);
  for (let comb of createCombinationGenerator(xs_, r - 1)) {
    yield [x, ...comb];
  }
  for (let comb of createCombinationGenerator(xs_, r)) {
    yield comb;
  }
}

const xs = [];
for (let i = 0; i < 50; i++) {
  xs.push(i + 1);
}

const generator = createCombinationGenerator(xs, 10);
for (let comb of generator) {
  console.log(comb);
}
```

```
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 12 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 13 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 14 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 15 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 16 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 17 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 18 ]
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 19 ]
...（相当な時間がかかるが、順次結果を出力する）
```

- **結果を保存しておく配列を考えなくてもよくなる**ので、コーディングも楽になります（この手の処理はしばしば配列の配列の配列とか出てきてややこしくなるので）

# ジェネレータはどう実装されているのか？

不思議に思いませんでしたか？どう実装されているのか。

## Node.jsの場合

[How does yield actually pause/resume the flow of a generator? : javascript]( https://www.reddit.com/r/javascript/comments/3i1td3/how_does_yield_actually_pauseresume_the_flow_of_a/)

- Node.jsではC++内でスタックフレームを保存・復元しているらしい
  - （C言語レベルのスタックフレームではなく、JavaScriptのスタックフレーム）

## BabelでES5に変換する場合

BabelでES5に変換できるのだから、C++で書かれたインタープリタ自体がサポートしていなくても実装できるはず。
Babalは有限状態機械に変換するらしい。
（変換されたコードを読もうとしてもメッチャ分かりづらい）

```Babelで変換したnatural-number-generator.js
"use strict";

var _marked =
/*#__PURE__*/
regeneratorRuntime.mark(createNaturalNumberGenerator);

function createNaturalNumberGenerator() {
  var i;
  return regeneratorRuntime.wrap(function createNaturalNumberGenerator$(_context) {
    while (1) {
      switch (_context.prev = _context.next) {
        case 0:
          i = 1;

        case 1:
          if (!true) {
            _context.next = 7;
            break;
          }

          _context.next = 4;
          return i;

        case 4:
          i += 1;
          _context.next = 1;
          break;

        case 7:
        case "end":
          return _context.stop();
      }
    }
  }, _marked);
}

var generator = createNaturalNumberGenerator();
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
console.log(generator.next().value);
```

# async/awaitも実はジェネレータで実装されている

…らしい。

自分でジェネレータを使ってasync/awaitを実装することもできます。
[ES6 Generatorを使ってasync/awaitを実装するメモ - maru source](http://blog.h13i32maru.jp/entry/2015/01/02/225457)

# PythonやRubyにもジェネレータはある

## Python

```natural-number-generator.py
def generate_natural_numbers():
    n = 1
    while True:
        yield n
        n += 1

for i in generate_natural_numbers():
    print(i)
```

## Ruby

```natural-number-generator.rb
generator = Enumerator.new {|yielder|
  n = 1
  loop do
    yielder.yield n
    n += 1
  end
}

generator.each do |n|
  puts n
end
```

# まとめ

- ジェネレータを使うと、巨大な組み合わせや探索をする再帰関数が効率的に書ける。楽に書ける