編集：これは現在、language-agnosticというタグが付けられていますが、pythonは良好な実行可能な疑似擬似コードです。
あなたはすなわちdef f(x): return f(g(x))のように見える形で、末尾再帰形で関数を書くことができれば、それが反復形にそれを回すのは簡単です。残念ながら、通常はテール再帰呼び出しで終わることはないので、いくつかの手口を知る必要があります。
まず第一に、我々はこのように見える機能を持っているとしましょう：
def my_map(func, my_list):
if not my_list:
return []
return [func(my_list[0])] + change_my_list(my_list[1:])
[OK]を、それは再帰が、再帰的な尾ではありませんので、：それは本当に
def my_map(func, my_list):
if not my_list:
return []
result = [func(my_list[0])] + change_my_list(my_list[1:])
return result
だ代わりに、私たちが必要機能をわずかに調整して、伝統的にアキュムレータとして知られているものを追加します。
def my_map(func, my_list, acc = [])
if not my_list: return acc
acc = acc + func(my_list[0])
return my_map(func, my_list[1:], acc + func(my_list[0]))
真の末尾再帰関数を持っている：私たちは今、def f(x): return g(f(x))からdef f(x): return f(g(x))に
を行ってきた、それは非再帰的な形式にその機能をオンにする非常に簡単です：今
def my_map(func, my_list, acc=[]):
while True: #added
if not my_list: return acc
#return my_map(func, my_list[1:], acc + func(my_list[0])) #deleted
func, my_list, acc = func, my_list[1:], acc + func(my_list[0]) #added
、アップ私たちはきちんと少し：
def my_map(func, my_list):
acc = []
while my_list:
acc.append(func(my_list[0])
my_list = my_list[1:]
return acc
注意あなたがさらにforループやリストの内包表記を使用して、それをクリーンアップすることができますが、それは読者の練習として残しています。
これは病理学的な例です。pythonにはmapという組み込み関数がありますが、プロセスは同じです：末尾の再帰的フォームに変換し、再帰呼び出しを引数の再割り当てで置き換えます。アップ。だから、
、あなたが持っている場合：、再び
def make_products(list_of_lists):
acc=[]
while list_of_lists:
first_list = list_of_lists[0]
rest = list_of_lists[1:]
acc = product_of(acc, first_list)
list_of_lists = rest
return acc
この缶：
def make_products(list_of_lists):
if not list_of_lists: return []
first_list = list_of_lists[0]
rest = list_of_lists[1:]
return product_of(first_list, make_products(rest))
をあなたに簡素化すること、そして、末尾再帰形式に
def make_products(list_of_lists, acc=[]):
if not list_of_lists: return acc
first_list = list_of_lists[0]
rest = list_of_lists[1:]
acc = product_of(acc, first_list)
return make_products(rest, acc)
を変換することができますさらに清掃して、forループに入れます：
def make_products(list_of_lists):
acc=[]
for lst in list_of_lists:
acc = product_of(acc, lst)
return acc
あなたは組み込み関数で見てきた場合、あなたはこのことを気づくかもしれませんが、多少よく知っている：
def reduce(function, iterable, initializer):
acc = initializer
for x in iterable:
acc = function(acc, x)
return acc
ので、最終的な形は
def make_products(list_of_lists):
return reduce(product_of, list_of_lists, []) # the last argument is actually optional here
のようなものがある：それは、本質的に
reduce機能です
それでは、product_of関数の記述について心配する必要があります。
タグが付けられたすべての言語のソリューションを明示的に求めているのですか、それともあなただけに興味がありますか？ – AndyG
ねえ、あなたは 'php'タグを忘れています:) –
言語を選んでください。 –