再帰を用いて基本的な関数をPythonで書いてみたメモ
再帰を理解するのに苦労したので自分用にまとめておこうと思い書いたメモです。今後も追加するかもしれません。
言語はPython3です。
再帰関数とは
- 再帰関数とは、関数の中で自分自身を呼び出すような関数
- 必ずどこかで終了するように実装しなければならない
- 大きな問題を小さな問題に分割して解決する分割統治法で使われる手法
1からnまでの和を求める再帰関数
sum.py
def sum(n):
if n <= 1:
return n
return n + sum(n-1)
print(sum(100)) # 5050
sum.py
def sum(n):
res = 0
if n >= 1:
res = n + sum(n-1)
return res
print(sum(100)) # 5050
nの階乗を求める再帰関数
factorical.py
def fractorial(n):
if n <= 1:
return n
return n * fractorial(n-1)
print(fractorial(5)) # 120
factorical.py
def factorial(n):
res = 1
if n >= 1:
res = n * factorial(n-1)
return res
print(factorial(5)) # 120
リストの各要素を2倍にしたリストを求める再帰関数
def double_list(lst):
if lst == []:
return []
first = lst[0]
rest = lst[1:]
return [first*2] + double_list(rest)
print(double_list([1,2,3])) # [2, 4, 6]
sum.py
def sum(n):
if n <= 1:
return n
return n + sum(n-1)
print(sum(100)) # 5050
sum.py
def sum(n):
res = 0
if n >= 1:
res = n + sum(n-1)
return res
print(sum(100)) # 5050
nの階乗を求める再帰関数
factorical.py
def fractorial(n):
if n <= 1:
return n
return n * fractorial(n-1)
print(fractorial(5)) # 120
factorical.py
def factorial(n):
res = 1
if n >= 1:
res = n * factorial(n-1)
return res
print(factorial(5)) # 120
リストの各要素を2倍にしたリストを求める再帰関数
def double_list(lst):
if lst == []:
return []
first = lst[0]
rest = lst[1:]
return [first*2] + double_list(rest)
print(double_list([1,2,3])) # [2, 4, 6]
factorical.py
def fractorial(n):
if n <= 1:
return n
return n * fractorial(n-1)
print(fractorial(5)) # 120
factorical.py
def factorial(n):
res = 1
if n >= 1:
res = n * factorial(n-1)
return res
print(factorial(5)) # 120
def double_list(lst):
if lst == []:
return []
first = lst[0]
rest = lst[1:]
return [first*2] + double_list(rest)
print(double_list([1,2,3])) # [2, 4, 6]
分かりやすい解説は、こちら
ユークリッドの互除法
euclidean.py
def gcd(m, n):
r = m % n
if r == 0:
return n
return gcd(n, r)
print(gcd(1071, 1029)) # 21
参考
euclidean.py
def gcd(m, n):
r = m % n
if r == 0:
return n
return gcd(n, r)
print(gcd(1071, 1029)) # 21
再帰関数を理解するための最もシンプルな例
Pythonで理解する再帰関数
Pythonで再帰関数を理解する
ループを再帰関数にする考え方
感想
再帰ってなかなかイメージしずらくて今も苦労してます…
コードの見た目はシンプルになる気がするのですが、どう動いているのかを理解するのに時間がかかってしまいます。その点for文はわかりやすいですよね。
Author And Source
この問題について(再帰を用いて基本的な関数をPythonで書いてみたメモ), 我々は、より多くの情報をここで見つけました https://qiita.com/rA9-S/items/b4ffbb29d941da5cb43e著者帰属：元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .