@soudai1025 が書いたブログ記事にPythonでFizzBuzzとかしてみたというエントリーがあって、まーいろいろ、あって突っ込みをいれました。

この中で再帰に関する記述があります。

で最後はみんな大好き再帰。 折角なのでループ文を使わずに与えられたintまでの１からの和を出してみました。

def sum(num, answer = 0):
    answer = answer + num
    num -= 1
    if num == 0: return answer
    return sum(num, answer)

「この再帰なんかおかしくね？」って直感的に思った。

おかしいというのはなんか複雑すぎないだろうか？ということである。answerって引数なくても実装できるよね。引き継ぎたい値がひとつしかないから戻り値で対応できる。

def sum(num):
    if num == 1:
      return 1
    return num + sum(num-1)

うん。これだ。これが正しい。

再帰を使う場合は、まず終了条件を考えます。この場合、num から 1へおりていくので、1で終了です。

次にのこったそれ以外のときのことを考えます。num と n-1 の和を足せば求める値がもとめられることに気づくことができればあとはそのままかくだけです。 再帰を使うと今作成している関数が動いている前提で考えることができます。そのあたりに慣れるとさくさくかけます。

再帰というのは スタック付きのループと見なせます。なのでループでできることはなんでも出きます。外のスコープの変数を引き継ぎたいときは、引数を増やせば伝搬できます。ただし、戻り値があるので、ひとつだけであれば伝搬可能です。この戻り値をリストにすることで複数の値を返すこともできます。

ちなみに、普通の関数プログラマの場合、こういうときは reduce を使います。 再帰より読みやすいですからね。

たぶん。