再帰呼び出しの様子を標準出力に表示

再帰呼び出しの様子を可視化するために、以下のように出力する動作を後付けしてみる。

ユークリッドの互除法

# 普通に再帰関数を定義
def gcd(a, b)
	b.zero? ? a.abs : gcd(b, a % b)
end

# 出力するよう指定
require './print_recursive_call'
extend PrintRecursiveCall
print_recursive_call :gcd

# 再帰関数を実行
gcd(1920, -1080)

output

gcd(1920, -1080)
|   gcd(-1080, -240)
|   |   gcd(-240, -120)
|   |   |   gcd(-120, 0)
|   |   |   #=> 120
|   |   #=> 120
|   #=> 120
# => 120

関数の呼び出し順序や再帰の深さ、引数と戻り値がひと目でわかる。さすがに再帰の終了条件や値の加工については元のコードを見ないとわからないものの、コードの流れを追うヒントにはなるだろう。

モジュールのコード

設定方法は Module#attr_accessor をイメージしている。そこでまずはクラス内で呼び出すためのメソッドを作成し、後からトップレベル（mainオブジェクト）でも使えるように微修正した。

メソッドの中では、再帰関数の別名（エイリアス）＝コピーを作成しておき、元の名前でコンソール出力を組み込んだラッパー関数として再定義する。また、再帰呼び出しの深さを管理することで、出力時に必要なインデント量がわかる。

print_recursive_call.rb

module PrintRecursiveCall
	INDENT_STR = "|   "

	def print_recursive_call(*mtds)
		mtds.each do |mtd|
			mtd_org = :"#{mtd}_noprint"
			if respond_to? :alias_method, true
				alias_method mtd_org, mtd
			else # object main
				instance_eval "alias #{mtd_org} #{mtd}"
			end

			define_method mtd do |*args|
				@rec_depth ||= 0

				puts INDENT_STR * @rec_depth + "#{mtd}(#{args.map(&:inspect).join(", ")})"
				@rec_depth += 1
				result = send(mtd_org, *args)
				@rec_depth -= 1
				puts INDENT_STR * @rec_depth + "#=> #{result}"

				result
			end
		end
	end
end

利用する際は、利用したいオブジェクト（その文脈における self ）にメソッドが定義されるように extend または include を用いてモジュールを組み込む。

利用方法

require './print_recursive_call'

# 特定のクラスでのみ利用 → そのクラス内でextend
class Foo
	extend PrintRecursiveCall
	print_recursive_call :mtd1 # 定義済みのメソッド名
end

# 全てのクラスで利用 → Classクラスまたはその親クラスでinclude
Module.include PrintRecursiveCall
class Bar
	print_recursive_call :mtd2
end

# トップレベルでのみ利用 → extend
extend PrintRecursiveCall
print_recursive_call :mtd3

# どこでも利用 → Objectクラス相当でinclude
include PrintRecursiveCall
print_recursive_call :mtd4

動作サンプル

『再帰的なアルゴリズムの実例集』に書いたものをいくつか可視化してみる。

短い再帰関数は本記事に直接書いているが、元記事のファイルを require './xxx' などと読み込んでも構わない。（最後の例はそうしている）

[分割統治法] クイックソート

どの再帰呼び出しの中でも同じ関数を2回呼び出す様子が見える。

def quick_sort(ary)
	return ary if ary.size <= 1

	pivot = ary.pop   # 毎回同じ結果になるよう、rand不使用
	ary_less_eq, ary_greater = ary.partition { |x| x <= pivot }
	quick_sort(ary_less_eq) + [pivot] + quick_sort(ary_greater)
end

require './print_recursive_call'
extend PrintRecursiveCall
print_recursive_call :quick_sort

ary = [5, 1, 3, 9, 7, 0, 4, 2, 8, 6]
quick_sort(ary)

output

quick_sort([5, 1, 3, 9, 7, 0, 4, 2, 8, 6])
|   quick_sort([5, 1, 3, 0, 4, 2])
|   |   quick_sort([1, 0])
|   |   |   quick_sort([])
|   |   |   #=> []
|   |   |   quick_sort([1])
|   |   |   #=> [1]
|   |   #=> [0, 1]
|   |   quick_sort([5, 3, 4])
|   |   |   quick_sort([3])
|   |   |   #=> [3]
|   |   |   quick_sort([5])
|   |   |   #=> [5]
|   |   #=> [3, 4, 5]
|   #=> [0, 1, 2, 3, 4, 5]
|   quick_sort([9, 7, 8])
|   |   quick_sort([7])
|   |   #=> [7]
|   |   quick_sort([9])
|   |   #=> [9]
|   #=> [7, 8, 9]
# => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

[メモ化再帰] フィボナッチ数列

処理が進むにつれて再帰呼び出しせず値を返すようになっていく様子が見える。

$table = [0, 1]
def fibonacci(n)
	$table[n] ||= fibonacci(n-2) + fibonacci(n-1)
end

require './print_recursive_call'
extend PrintRecursiveCall
print_recursive_call :fibonacci

fibonacci(5)
puts
fibonacci(5) # メモ済みの状態でもう1回

output

fibonacci(5)
|   fibonacci(3)
|   |   fibonacci(1)
|   |   #=> 1
|   |   fibonacci(2)
|   |   |   fibonacci(0)
|   |   |   #=> 0
|   |   |   fibonacci(1)
|   |   |   #=> 1
|   |   #=> 1
|   #=> 2
|   fibonacci(4)
|   |   fibonacci(2)
|   |   #=> 1
|   |   fibonacci(3)
|   |   #=> 2
|   #=> 3
# => 5

fibonacci(5)
# => 5

ちなみに fibonacci(n-2) と fibonacci(n-1) を入れ替えると再帰呼び出しの形が変わる。

[相互再帰] 再帰下降構文解析

再帰関数が複数になっても問題ない。コードは長いため転記せず require で読み込む。

require './expr_parser'
require './print_recursive_call'

# 定義済みのクラスを開いて処理を追加
class ExprParser
	extend PrintRecursiveCall
	print_recursive_call :additive, :multitive, :primary, :decimal
end

ExprParser.new.parse("1+2*(3*(4+5)+6)*(7+8)+9")

output

additive(0)
|   multitive(0)
|   |   primary(0)
|   |   |   decimal(0)
|   |   |   #=> [1, 1]
|   |   #=> [1, 1]
|   #=> [1, 1]
|   multitive(2)
|   |   primary(2)
|   |   |   decimal(2)
|   |   |   #=> [3, 2]
|   |   #=> [3, 2]
|   |   primary(4)
|   |   |   decimal(4)
|   |   |   #=> [nil, nil]
|   |   |   additive(5)
|   |   |   |   multitive(5)
|   |   |   |   |   primary(5)
|   |   |   |   |   |   decimal(5)
|   |   |   |   |   |   #=> [6, 3]
|   |   |   |   |   #=> [6, 3]
|   |   |   |   |   primary(7)
|   |   |   |   |   |   decimal(7)
|   |   |   |   |   |   #=> [nil, nil]
|   |   |   |   |   |   additive(8)
|   |   |   |   |   |   |   multitive(8)
|   |   |   |   |   |   |   |   primary(8)
|   |   |   |   |   |   |   |   |   decimal(8)
|   |   |   |   |   |   |   |   |   #=> [9, 4]
|   |   |   |   |   |   |   |   #=> [9, 4]
|   |   |   |   |   |   |   #=> [9, 4]
|   |   |   |   |   |   |   multitive(10)
|   |   |   |   |   |   |   |   primary(10)
|   |   |   |   |   |   |   |   |   decimal(10)
|   |   |   |   |   |   |   |   |   #=> [11, 5]
|   |   |   |   |   |   |   |   #=> [11, 5]
|   |   |   |   |   |   |   #=> [11, 5]
|   |   |   |   |   |   #=> [11, 9]
|   |   |   |   |   #=> [12, 9]
|   |   |   |   #=> [12, 27]
|   |   |   |   multitive(13)
|   |   |   |   |   primary(13)
|   |   |   |   |   |   decimal(13)
|   |   |   |   |   |   #=> [14, 6]
|   |   |   |   |   #=> [14, 6]
|   |   |   |   #=> [14, 6]
|   |   |   #=> [14, 33]
|   |   #=> [15, 33]
|   |   primary(16)
|   |   |   decimal(16)
|   |   |   #=> [nil, nil]
|   |   |   additive(17)
|   |   |   |   multitive(17)
|   |   |   |   |   primary(17)
|   |   |   |   |   |   decimal(17)
|   |   |   |   |   |   #=> [18, 7]
|   |   |   |   |   #=> [18, 7]
|   |   |   |   #=> [18, 7]
|   |   |   |   multitive(19)
|   |   |   |   |   primary(19)
|   |   |   |   |   |   decimal(19)
|   |   |   |   |   |   #=> [20, 8]
|   |   |   |   |   #=> [20, 8]
|   |   |   |   #=> [20, 8]
|   |   |   #=> [20, 15]
|   |   #=> [21, 15]
|   #=> [21, 990]
|   multitive(22)
|   |   primary(22)
|   |   |   decimal(22)
|   |   |   #=> [23, 9]
|   |   #=> [23, 9]
|   #=> [23, 9]
# => [23, 1000]

引数の数字は文字列の開始位置、戻り値の数字の組は文字列の終了位置と部分的な数式の計算結果である。この動作のうち構文解析成功部（nilを返していないところ）だけを見やすく図にしたものが以下の絵になる。