再帰を理解するのに苦労したので自分用にまとめておこうと思い書いたメモです。今後も追加するかもしれません。
言語は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で理解する再帰関数]
(https://qiita.com/dhirabayashi/items/2f079e62fa2e286f1766)
[Pythonで再帰関数を理解する]
(https://note.com/shimakaze_soft/n/nf17633fe257c)
ループを再帰関数にする考え方

感想

再帰ってなかなかイメージしずらくて今も苦労してます…
コードの見た目はシンプルになる気がするのですが、どう動いているのかを理解するのに時間がかかってしまいます。その点for文はわかりやすいですよね。