反復諸法 - 繰り返し、イテレータ、再帰、（続く）

[.｡oO(さっちゃんAdvent Calendar) : ATND http://atnd.org/events/22829 ]2日目

繰り返し

programmingには繰り返しと云う実行構造が有ります。forとかwhileとかforeachとか。

# Python
for i in range(12):
  print(i * 2)

# Python
i = 0
while i < 19:
  print(i - 21)
  i += 1

// JavaScript
var i = len = 0,
    items = ['momon', 'momen', 'nomom'],
    item;

for (i = 0, len = items.length; i < len; ++i) {
  console.log(items[i] + 'is also momonga?');
}
i = -1;
while (item = items[++i]) {
  console.log(item + 'is doronga!');
}

イテレータ（反復子、繰返子）も繰り返しです。

# Python
for item in ['somonga', 'guminga']:
  print('dehaha' + item)

// JavaScript
var prop,
    hash = {
      'mobonga': 9,
      'loromma': 8
    };

for (prop in hash) if (hash.hasOwnProperty(prop)) {
  console.log('KAERE ' + hash[prop] + '匹の' + prop);
}

// D Programming language
import std.stdio;

void main(string[] args) {
  string[] items = ['gehehe', 'yunyun', 'myoho'];

  foreach (item; items) {
    writeln(item);
  }
}

イテレータは意図としては集合演算に近いですね。動作は反復ですが。
JavaScriptのArray.prototype.forEachやRubyのeachは、高階map関数の様なもので、イテレータとはちょっと違う。もっと強い。

再帰

再帰関数とは、中から自身を呼び出す関数の事。洞う呼び出すかは関係ない。

; Scheme
(define factorial n
  (if (= n 0)
    1
    (* n (factorial (- n 1)))))

%% Erlang
factorial(0) -> 1;
factorial(N) -> N * factorial(N - 1).

再帰には、再帰的な（recurcive）再帰と、反復的な（iterative）再帰が有る。再帰的な再帰関数は、あんまり重ねられない。(factorial 12)を手で実際にワンステップづつ書き換えてみるがよろし。反復的な再帰は、末尾呼び出し最適化を行う処理系では効率よく実行される。

; Scheme
(define factorial n
  (define factorial-iter n a
    (if (= n 0)
      a
      (factorial-iter (- n 1) (* n a))))
  (factorial-iter n 1))

%% Erlang
-module(factorial).
-export([factorial/1]).
factorial(N) -> factorial(N, 1);
factorial(0, A) -> A;
factorial(N, A) -> factorial(N - 1, N * A).