Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

再帰を用いて基本的な関数を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]

分かりやすい解説は、こちら

ユークリッドの互除法

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文はわかりやすいですよね。

rA9-S
pythonで機械学習を勉強しています。まずは備忘録として使用していこうかと思います。 初心者ですので何か間違っているところがあれば優しく教えて下さるとありがたいです。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away