mizzsugar’s blog

Pythonで学んだことや読書録を書きます。

Python3で再帰処理を書いたよ

再帰処理を1日中学んだ翌日、夢の中で再帰処理を書いてしまうほどになってしまったので

これはお告げだと思い、ブログに書くことにしました。

【前提】

再帰処理とは

「プログラムのある関数の中から自分自身の関数を呼び出す」処理のことらしい

(「呼び出し」と書いてあるけど、やっていることは同じなので「処理」置き換えてもいいかな、と判断しました。あと、色々読んだ中でこの説明が一番しっくりきた)

www.weblio.jp

と言ってもイメージが沸かないので、実際に再帰処理を用いた処理を書きます。

リストに格納されている文字列の登場回数を数える関数です。 (collectionsのCounterで間に合うやつです汗)

count_name.py

from typing import Dict, List


l = ['a', 'b', 'a']



def count_name(name: str, list: List[str], num: int) -> int:
    if not list: # ①listが空の場合(listが[ ] の場合は、falseを返す)
        return num
    if list[0] == name:  # ②listの先頭がnameと一致する場合
        num += 1
    return count_name(name, list[1:], num) # ③listは先頭を1つずらしたものにし、次の再帰処理へ

print(count_name('a', l, 0)) # ④

こんな感じで処理が行われています。

1.list = ['a', 'b', 'a'], name = 'a'

①list == [ ] ではないのでスキップ

②list[0] == 'a'なので

num += 1

③return count_name('a' , list['b', 'a'])

2.list = ['b', 'a'], name = 'a'

①list == [ ] ではないのでスキップ

②list[0] = 'b'なのでスキップ

③return count_name('a' , list['a'])

3.list = ['a'], name = 'a'

①list == [ ] ではないのでスキップ

②list[0] == 'a'なので

num += 1

③return count_name('a' , list[ ])

4.list = [ ], name = 'a'

①list == [ ] なので retun num

③のcount_nameを繰り返した結果、2が返ってきています。 ④でcount_nameをprintすると、count_name内で呼び出しているcount_nameの返り値が2なので、 2がプリントされます。

ちなみに、③は「count_name(list[1:], name 」では駄目なのか? と私は思いました。 駄目です。

理由は、return がないと何も実行されず、処理が終わらないからです。

関数では、returnの箇所で処理が終了するのですが、それがないと

ifで当てはまらなかった場合に永遠に何も起こらないことになってしまいます。

おまけ。後から提案されたやつ↓

def count_name(name: str, list: List[str]) -> int:
    if not list:
        return 0
    
    head, *tail = list
    n = 1 if head == name else 0
    return n + count_name(name, tail)

print(count_name('a', l))

head, *tail = list 以下はこんな感じです。

head = list[0]
tail = list[1:]

if head == name:
    n = 1
else:
    n = 0
return n + count_name(name, tail)

それにしても、自分が書いたやつ、もっさりしてる(涙)

私のがもっさりスパゲッティなら、後者のコードはそうめんなので

私もそうめん書けるようにがんばります。