TSpython 発言

廣島です．

> 　最近、Scheme をかじって「もしかしたら、再帰プログ
> ラムをループにしてくれるのかな？」と思い、以下のプ
> ログラムを書いてみました。
> 
> def func(x):
>   if x == 0:
>     return 0
>   else:
>     return 5 + func(x - 1)

この func を Scheme で書くと

(define (func x)
  (if (zero? x)
      0
      (+ 5 (func (- x 1))))) ; 末尾再帰でない!!

となります．Scheme の実装の 1 つ SCM の場合，
x = 1000000 を与えるとセグメンテーション違反になりました．
guile でも Stack overflow になります．

理由は再帰が 末尾再帰 (または 終端再帰 とも言う) になっていないからです．

func の呼び出しが 次の func の返り値を待ち，
それに 5 を加えて値を返しています．
つまり，次の func の呼び出しが，
前の func の最後の処理(末尾)になっていません．


そこで，内部関数 foo を使って func を

(define (func x)
  (define (foo x y)
    (if (zero? x)
	y
	(foo (- x 1) (+ y 5)))) ; 末尾再帰
  (foo x 0)) ; 内部関数呼び出し(これも末尾呼び出しなので goto で置き換わる)

と定義すれば，次の foo の呼び出しが，
前の foo の最後の処理になり，
この再帰はループに置き換わります．

内部関数にしない方がコードが見やすく，
分かりやすいかも知れませんね．

(define (foo x y)
  (if (zero? x)
      y
      (foo (- x 1) (+ y 5))))

(define (func x)
  (foo x 0))


python で書くなら
# 動作確認出来ませんので間違っているかも...

def foo(x, y):
    if x == 0:
       return y
    else:
       return foo(x - 1, 5 + y)

def func(x):
    return foo(x, 0)

と言う感じでしょうか．

ちなみに Scheme では，
foo を「名前付き let」でバインドするのが普通だと思います．

(define (func x)
  (let foo ((a x) (b 0))
    (if (zero? a)
	b
	(foo (- a 1) (+ 5 b))))) ; やはりこれも末尾再帰

-----------------------------
	廣島 勉
	(tsutomu@...)