整数の一次元配列から最大値を求める再帰的アルゴリズムについて

最大値を求める再帰的プログラム

大きさが n であり、任意の整数を各要素にもつ一次元配列 a から最大値を求める再帰的アルゴリズムをC言語で書いてみた。

int func(int a[], int n){
    int v1, v2;
    if(n == 1){
        return a[0];
    }else{
        v1 = func2(a, n-1);
        v2 = a[n-1];
        if(v1 > v2){
            return v1;
        }else{
            return v2;
        }
    }
}

実行の様子を追ってみる

func({3,2,1,7,5}, 5)の場合

1巡目：func({3,2,1,7,5}, 5)
2巡目：func({3,2,1,7,5}, 4)
3巡目：func({3,2,1,7,5}, 3)
4巡目：func({3,2,1,7,5}, 2)
5巡目：func({3,2,1,7,5}, 1)

5巡目で n==1 となるので、return a[0] が返る。再帰的呼び出しは4回。

次はreturnで何の値が返ってくるのかを追う。
5巡目：n==1 より return[0] -> 3
4巡目：v1=3, v2[1]=2, v1>v2 より return v1 -> 3
3巡目：v1=3, v2[2]=1, v1>v2 より return v1 -> 3
2巡目：v1=3, v2[3]=7, v1<=v2 より return v2 -> 7
1巡目：v1=7, v2[4]=5, v1>v2 より return v1 -> 7

よって最大数 7 を得ることができる。