Erlang World

top > sequential programming > recursive function

Recursive Function

再帰関数

再帰関数とは自分自身を呼び出す関数のことです。

プログラムを通して学んでみましょう。
サンプルを見てみて下さい。

-module(mymath).
-export([start_factorial1/1,start_factorial2/1]).

start_factorial1(N) when is_integer(N) ->
    factorial1(N).
    
factorial1(0) ->
    1;
factorial1(N) ->
    N * factorial1(N-1).

これは階乗を返す関数のサンプルです。
階乗とは1からNまでの値を掛け合わせた値のことです。

例えば、5の階乗は「5! = 5 * 4 * 3 *2 * 1 = 120」となります。

factorial1/1は階乗を計算する関数です。
実験してみましょう。

> mymath:start_factorial1(5).
120
> mymath:start_factorial1(10).
3628800

どのように動作しているのか、書き下してみます。

再帰関数をスタートさせる関数を実行。
start_factorial1(3) when is_integer(3) ->
    factorial1(3).
    
自分の処理の中で、自分の関数を呼び出している。
factorial1(3) ->
    3 * factorial1(3-1)
    
factorial1(2) ->
    2 * factorial1(2-1)
    
factorial1(1) ->
    1 * factorial1(1-1)

再帰がないので、この関数は終了する。
factorial1(0) ->
    1

どんどんNが小さくなっていき、最後は0になります。すると初めて返り値が決定するので、今度は値を上位の関数に返して行きます。

この関数は

factorial1(factorial1(factorial1(factorial1(0)*1)*2)*3)

というように、奥に奥に入って行きます。 factorial1(0)が来た時点で奥に潜り込むのをやめて、どんどん上がってきます。

これはスタック(詳しくはOSの本を参照下さい。)という機能を使うのですが、非常に無駄が多いです。なぜなら、factorial(N)からfactorial(0)まで全ての結果を保有している必要があるからです。
次に、スタックを使わないプログラムを見ていきましょう。

末尾再帰

スタックを使ったデータ構造を解決するには、以下のようにすれば大丈夫です。

-module(mymath).
-export([start_factorial1/1,start_factorial2/1]).

start_factorial2(N) when is_integer(N) ->
    factorial2(N,1).
    
factorial2(0,X) ->
    X;
factorial2(N,X) ->
    factorial2(N-1,X*N).

この関数は先ほどのfactorial1と違い、値は関数の中に残っていません。
別の言い方をすれば、関数の最後の式が自分自身だけから構成されているとも言えます。

スタックのように前の状態を保持する必要がなくなるため、可能なら関数の中に状態を残さず引数として状態を受け継ぐような設計にするべきです。
このような設計を末尾再帰と呼びます。

サンプル

-module(listsum).
-export([sum/1]).

sum(List) ->
    sum1(List,0).

sum1([], Sum) ->
    Sum;	
sum1([H | T], Sum) ->
    sum1(T,Sum + H).

1> listsum:sum([4,5,8,2,9,0,4]).
32

自分の中に残しておきたい状態があれば、それを引数として渡すような工夫をすれば大丈夫です。

mail to :