Pythonで理解する再帰関数

概要

再帰関数、使ってますか？
再帰関数は実装が難しいと感じる方もいらっしゃると思いますが、コツを掴めば実はそれほど難しくはありません。
以下、Pythonを使ったサンプルコードで解説を試みます。（なんとなくPythonにしましたが、それ以外の言語でも考え方は変わりません）

末尾再帰などの発展的な内容には立ち入らず、再帰関数をなんとなく実装できるようになることを目指します。

本記事は、こちらの記事をパクリ 参考にしています。
再帰関数を理解するための最もシンプルな例

動作環境

Python3

再帰関数とは？

関数の定義の中で、その関数自身が登場する関数のことです。自分で自分を呼び出すということです。
再帰呼び出しと呼ばれることもあります。

なんで再帰関数を使うの？

再帰関数を使うことで、for文などのループ構文を使わずに繰り返し処理を実装することができます。
for文使えばいいじゃんと思われるかもしれないですが、for文よりも再帰関数を使って実装したほうがいい場合もあります。
例えば木構造のデータを処理するには再帰関数のほうが適していますが、この記事ではその辺りの説明には立ち入りません。

再帰関数を実装する時に考えること

さて、早速本題です。ここでは、整数値nを一つ受け取り、1からnまでの和を返す関数totalを再帰関数として実装してみることにします。

関数の仕様を明確にする

まず必要なことは、関数の仕様を明確にすることです。ここで言っている仕様とは、要するに「引数」と「戻り値」です。「入力」と「出力」といってもいいでしょう。

どんな値が入力されたら、どんな値を出力するのか。今回のtotal関数では、ある整数値を入力すると、1からその整数値までの合計値が出力されるというのが仕様ですね。
ただ、それだけでは不十分です。なぜなら、この仕様は1未満の値が入力された場合のことを想定していないからです。
1未満の値が入力された場合の出力をどうするかは決めの問題とも言えますが、出力は合計値ですから、何も計算をしていないという意味で0を返すことにしましょう。この処理であれば、再帰など考えずに簡単に書けるので、まずはそれを実装してみましょう。

def total(n):
    if n < 1:
        return 0

もちろん、まだ動きません。肝心の合計値を計算する処理を実装する必要があります。

あたかも関数が実装済みであるかのように考える

ここで、再帰関数を実装する上で重要な考え方を述べたいのですが、それは見出しの通り、今実装しようとしているtotal関数は、既に実装済みであるかのように考えることです。
何言ってんだこいつと思われるかもしれませんので、説明します。

今実装しようとしているのは、1からn（引数）までの合計値を計算して返す関数なわけですが、最終的な出力となる合計値は、引数nと「1から(n - 1)までの合計値」を足したものと等しくなるはずです。
nは引数として渡されている値ですから、あとは「1から(n - 1)までの合計値」さえわかればtotal関数は実装できるということになります。

「1から(n - 1)までの合計値」はどうすれば求められるでしょうか。ここで、先述の「関数が既に実装済みであるかのように考える」ということが重要になってきます。今実装しようとしているtotal関数は、1から引数までの合計値を求める関数です。それが既に実装済みなのだとしたら、total関数に(n - 1)を引数として渡せば「1から(n - 1)までの合計値」を得られるということになります。
引数nと「1から(n - 1)までの合計値」を足したのが最終的な答えですから、それをそのまま書いてあげればtotal関数の実装は完了です。つまり、下記のようになります。

def total(n):
    if n < 1:
        return 0

    return n + total(n - 1)

え、それでいいの？と思われるかもしれませんが、それでいいのです。
実際動かしてみると、ちゃんと動作します。

print(total(5))      # 15
print(total(10))     # 55
print(total(100))    # 5050

なんか不思議な感じがしますが、あれこれ考えるよりも、そういうものだとしてパターンを覚えてしまえば再帰関数を実装する敷居が下がると思います。

無限ループにならない？

無限ループにはなりません。
再帰呼び出しされるtotal関数には引数として(n - 1)が渡されるので、total関数が再帰呼び出しされるたびに引数nの値は1ずつ小さくなっていきます。やがてnの値は0になり、最初のif文の条件に引っかかり、そこで再帰呼び出しが止まります。そのため、無限ループにはならないのです。

このように、再帰関数には再帰呼び出しを止めるための終了条件が必要不可欠です。ここで重要なのは、再帰呼び出しをする際の引数は、元の引数の値を加工したものであること、それも最終的には終了条件に引っかかるような加工である必要があります。元の引数をそのまま、もしくは誤った加工をした上で引数として渡して再帰呼び出しをすると、永遠に終了条件に引っかからないのでそれこそ無限ループになってしまいます。¹

しかし、今回1未満の値が渡された時の仕様を考えたように、関数の仕様をしっかり決めて実装すれば、再帰の終了条件に相当する条件分岐は自然と実装されていたりします。

補足

現状のコードでは、total関数に渡す引数が大きな数だとエラーとなってしまいます。これはPythonの仕様に起因するものです。
しかし、今回のコードはあくまでも再帰関数の実装方法について理解するためのサンプルにすぎないということでご容赦ください。

どうしても気になる方は、「sys.setrecursionlimit」でググっていただければいいかなと思います。

別の例

せっかくなので、復習も兼ねてもう一つ例を見てみます。
今度はintのリストを入力すると、各要素を2倍にしたリストを出力するdouble_list関数を再帰関数として実装してみます。

double_list関数の仕様

まずは、関数の仕様を明確にするのでした。intのリストを入力すると、各要素が2倍になったリストが出力されるというのが仕様です。また、空リストが入力された際の出力も考える必要があります。
入力が空リストの場合は、出力も空リストとするのが妥当でしょう。これは、再帰呼び出しの終了条件にもなります。

def double_list(lst):
	if lst == []:
		return []

double_list関数を再帰呼び出しする

次に、double_list関数を再帰呼び出しする箇所を実装します。その際は、再帰呼び出しする関数があたかも実装済みであるかのように考えるのでしたね。
リストの場合、先頭要素と、先頭要素を除いたリストに分けて考えます。便宜上、先頭要素のことをfirst、先頭要素を除いたリストのことをrestと呼称することにします。

def double_list(lst):
	if lst == []:
		return []
	
	first = lst[0]
	rest = lst[1:]

total関数の例と同様に、値を2倍にしたfirstと、各要素を2倍にしたrestを結合すれば最終的な出力になると考えます。そして、リストの各要素を2倍にしたリストを返すdouble_list関数は「実装済み」なわけですから、「各要素を2倍にしたrest」は、restをdouble_list関数に渡せば得られます。
そして、double_list(rest)が出力するリストの先頭に、2倍にしたfirstを追加したリストを返すようにすれば実装完了です。

こんな感じです。

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]
print(double_list([4, 5, 6]))    # [8, 10, 12]

restは先頭要素を除いたリストなので、再帰呼び出しされるたびに要素が減っていき、最終的には空リストになるので最初のif文に引っかかり、そこで再帰呼び出しが止まります。

まとめ

再帰関数を実装するには、下記のようなことを考えます。

• 関数の入力と出力を明確にする
• 特に、空リストが入力されたら空リストを出力するなど、再帰呼び出しをしなくても出力値が決まるようなパターンも網羅し、それを処理するための条件分岐を実装する
• 上記のようなパターンが再帰呼び出しを止めるための終了条件になる
• そのような終了条件は再帰関数には必要不可欠（無いと無限ループになってしまう）
• 再帰呼び出しする関数は、あたかも既に実装済みであるかのように考える
• 既に実装済みであると考えるということは、再帰呼び出しする関数は先に決めた仕様通りの出力を期待できる
• 元の引数の値と、再帰呼び出しした関数の出力値を使って最終的な出力値を生成する
• 再帰呼び出しする際は、元の引数の値を加工した値（整数なら1を引く、リストなら先頭要素を取り除く等）を引数として渡す必要がある
• 値の加工内容は、最終的には終了条件に引っかかるものでなければならない

参考図書（アフィリエイトではありません）

• すごいHaskellたのしく学ぼう!
• 関数型言語Haskellの入門書。関数型言語は繰り返し処理を再帰で実装するのが普通なため参考になります
• 英語版なら無料で読めます http://learnyouahaskell.com/chapters
• 著作権的にヤバそうな挿絵が多い
• プログラミングの基礎
• 関数型言語OCamlを使ったプログラミング入門書。やはり繰り返し処理は再帰で実装するので参考になります

1. 実際にはコールスタックがどんどん積まれていくのでそのうちエラーになりますが ↩