二重forループとwhileループを組み合わせた関数をどのような手順を踏んで再帰関数に書き換えられるか

Question

下記のコードを再帰関数に書き換えたいのですが、どのような手順を踏んで再帰に書き換えることが考えられますでしょうか？

私がいつも再帰を実装するときに踏んでいる手順では、フィボナッチ数列や簡単な順列の問題での再帰呼び出しが一つの場合には、有効なのですが、下記の重複したループを考えるときには、すんなりとはいきません。
なにかお気づの点ありましたらご教示いただけませんしょうか？

私がいつも踏んでいる手順は下記です。
ーーーー
1. ループがある箇所を再帰にできそうか否か。
2. 再帰にできるループが何個あるか。
3. 再帰にできるループの数だけ、base caseを考える。
4. それぞれのループの終了条件を確認し、それをbase caseとして実装する。
5. base caseに向かって再帰で呼び出す関数の引数にどんな値を渡せばいいかを考える
6. 再帰で呼び出す関数の実行前に引数にわたす値を計算するコードを実装

ーーーー


再帰関数に書き換えたいコード
(合計値がtargetと同等のユニークな組み合わせを出力するコード)
```python
def combination_sum(candidates, target):
    outputs = [[]]
    results = []
    for c in candidates:
        tmps = []
        for output in outputs:
            while target >= sum(output):  # >=にするのは、targetと同じものを含めて、後で取り出す、という考えがあるから。
                tmps.append(output.copy())
                output.append(c)
                if sum(output) == target: # ターゲットと同じリストを保持する -> backtrackingの条件1
                    results.append(output.copy())
        outputs = tmps # リストの更新(2のみの組み合わせ, 2,3の組み合わせ、2,3,6の組み合わせ....) -> backtrackingの条件2
    return results

if __name__ == "__main__":
    candidates = [2,3,6,7]
    target = 7
    print(combination_sum(candidates, target))
```

アウトプット
```shell
$ python backtracking.py 
[[2, 2, 3], [7]]
```

Accepted Answer

通常、事前条件などはコード化されません。コメントに書かれればいいところで、プログラムの一部として表明(アサーション)されることは稀です。今回のコードにも、「ここを見ればわかるでしょ」といえるほど明確に示してる部分があるとは思いません。

ではなぜこれが重要なのかというと、これを理解することがコードを理解することだと思ってるからです。特に強調したいのが、これは再帰だとか関係なく、コードの読み書き全般において重要だと考えているということです。
例えば、ソースコードが与えられたときに紙と鉛筆を使って同じ処理を行えることも理解してるといえる状況の一つです。しかし、ふつうはこれを理解してるとは言わないでしょう。それぞれのコードがどういう役割を果たして、どう関係しているのかがわからなければ理解したとは言えません。

それさえわかってしまえば再帰関数への書き換えは大きく進みます。あとは、その役割を再帰関数で行うにはどうしたらいいのか、完全に同じ役割の再帰関数でないのならほかの役割をどう変えなきゃいけないのか、これを考えるだけですから。

コメントを見ていて気になったのは手続き的には理解できると言ってるところで、きちんと理解しようと思ったら手続き的だろうがそれなりに大変です。逆に手続き的なコードのほうが本質的ではない部分が入り込みやすいので理解しづらいことすらあります。
たとえば今のコードでも、tmpsのような典型的な一時変数は言語の都合上置かれてるだけで理解する上では冗長なだけです。
一番内側のwhileループ中でresultsに追加している部分も同様です。resultsに追加している部分がない場合このwhileループの役割は__**「outputにcを0個以上追加したもののうち合計がtarget以下のものをtmpsに入れる」**__ことで、resultsに追加する部分を付け加えることで**__「outputにcを0個以上追加したもののうち合計がtarget以下のものをtmpsに入れる + outputにcを1個以上追加したもののうち合計がtargetになるものをresultsに入れる」__**になります。
なんでtmpsに入れるのが「**__0個以上追加したもの__**」で、resultsに入れるのが「**__1個以上追加したもの__**」なんでしょう? あんまり深入りしませんがややこしくないですか? 実はresultsへの追加はここでやる必要はないのでこんなこと考えないようにすることも可能なんです。ありうる組み合わせを列挙してその中から合計がちょうどtargetになるものを選び出すと考えれば、むしろループが終わってからoutputsから合計がちょうどになるものを抜き出すほうが自然です。そういう意味ではこのwhileループは手続き型のコードにありがちな、分離可能な処理を一つのループで同時に行っている状態です。

そんなこともあって、別にループで書かれてるからと言って理解する難しさにはそんなに差がないのにループなら理解できると思っているのは、ループのコードに関しては深く追及してないんじゃないかと思ってしまいます。

再帰で書いたコードの全体です。Pythonの言語仕様に詳しくないので同名の関数がどう扱われてるのかわかりませんが、とりあえず期待通り動いてるのでそのまま貼ります。appendの呼び出しはすべてここで定義しているappendを呼び出しているつもりです。
```Python
def append(combination: List[int], value: int) -> List[List[int]]:
    if sum(combination) > target: #base case すでにtargetを超えていたら組み合わせは存在しない
        return []

    return [combination] + append(combination + [value], value) # valueを一つも追加しない組み合わせと一つ以上追加したものの和集合

def rec(i: int) -> List[List[int]]:
    if i == len(candidates):
        return [[]] #使える要素がないので、何も選ばない組み合わせしかない

    return [appended for combination in rec(i + 1) for appended in append(combination, candidates[i])] #i + 1以降を使う組み合わせ(combination)それぞれに対してcandidates[i]を0個以上追加したもので合計がtarget以下のもの

return [combination for combination in rec(0) if sum(combination) == target]
```
---
少し話はそれますが「事前条件」「事後条件」「(ループ)不変条件」という考え方になじみはありますか?

再帰関数に限らず、複雑なアルゴリズムを扱う上で必須の考え方です。もしあまり気にしてこなかったなら、意識してほしいと思います。質問者さんのいつもの手順がこういった考えと違ってあまりに機械的に思えたので強調のため先頭に書きました。


さて本題の再帰関数ですが試しに以下の再帰関数での置き換えをします。
`def append(combination, value):` combination(組み合わせ)にvalueを0以上追加したもので合計がtarget以下のものを重複なくすべて返す
`def rec(i):` candidatesのi番目以降の要素を使った組み合わせで合計がtarget以下のものを重複なくすべて返す

まずappendは
```Python
def append(combination: List[int], value: int) -> List[List[int]]:
    if sum(combination) > target: #base case すでにtargetを超えていたら組み合わせは存在しない
        return []

    return [combination] + append(combination + [value], value) # valueを一つも追加しない組み合わせと一つ以上追加したものの和集合

```
とかけます。気を付けなければいけないのは、base caseの正しさと、`append(combination + [value], value)`が正しい結果を返した場合に`append(combination, value)`が正しい結果を返すかということです。

次にrecを考えると
```Python
def rec(i: int) -> List[List[int]]:
    if i == len(candidates):
        return [[]] #使える要素がないので、何も選ばない組み合わせしかない

    return [appended for combination in rec(i + 1) for appended in append(combination, candidates[i])] #i + 1以降を使う組み合わせ(combination)それぞれに対してcandidates[i]を0個以上追加したもので合計がtarget以下のもの

```
と書けます。appendと同様に、base caseの正しさと、rec(i + 1)が正しい結果を返した場合にrec(i)も正しい結果を返すかに気を付ける必要があります。

最後にrec(0)から合計が一致するものだけ選び出せばほぼ同質のの関数が出来上がります。

次に、ループバージョンで書かれていたものを見てみます。
`for c in candidates:` の各イテレーションの先頭で、outputsはcより前の要素を使った合計がtarget以下の組み合わせです。ただし最初のループでは使える要素がないので何も選ばない組み合わせしかありません。そして各イテレーションの最後ではoutputsはcとcより前の要素を使った合計がtarget以下の組み合わせです。
なぜそう言えるかというと、cより前の要素を使った組み合わせそれぞれに対して(`for output in outputs:`)、合計がtarget以下になるような(`target >= sum(output):`)、cを0個以上追加した組み合わせを求めてる(`tmps.append(output.copy()); output.append(c)`)からです。この処理は、outputsがcより前の要素を使った合計がtarget以下の組み合わせであるとき、cとcより前の要素を使った合計がtarget以下の組み合わせを列挙できます。

こうしてみると今回のコードに関しては、再帰で書こうがループで書こうが考えなければいけないことは対して違いがなくて、ループ/再帰だからというような難しさはあまりないように思います。それでもそこがなかなかはっきりしないのは「事前条件」「事後条件」「(ループ)不変条件」といったことに意識が向いてないからじゃないかと思います。

Answer

ループは機械的に再帰にできますが、多分これは求めている解ではないでしょう。
```Python
def combination_sum(candidates, target):
	outputs = [[]]
	results = []
	def f1(i):
		if i < len(candidates):
			c = candidates[i]
			tmps = []
			nonlocal outputs
			def f2(i):
				if i < len(outputs):
					output = outputs[i]
					def f3():
						if target >= sum(output):
							tmps.append(output.copy())
							output.append(c)
							if sum(output) == target:
								results.append(output.copy())
							f3()
					f3()
					f2(i+1)
			f2(0)
			outputs = tmps
			f1(i+1)
	f1(0)
	return results

if __name__ == "__main__":
	candidates = [2,3,6,7]
	target = 7
	print(combination_sum(candidates, target))
```
**追記**
forループを再帰にする方法
```python
a = [11, 22, 33, 44]

for e in a:
	print(e)
print('---')

for i in range(len(a)):
    e = a[i]
	print(e)
print('---')

def f(i):
	if i < len(a):
        e = a[i]
		print(e)
		f(i+1)
f(0)
print('---')
```
whileループを再帰にする方法
```python
a = []
i = 1
while sum(a) < 10:
	print(i, a)
	a.append(i)
	i += 1
print('---')

a = []
def f(i):
	if sum(a) < 10:
		print(i, a)
		a.append(i)
		i += 1
		f(i)
f(1)
print('---')
```

関連した質問