再帰関数の処理の仕方がわからない

Question

発生している問題・エラーメッセージ

以下のプログラムを実行させたいです。

このプログラムでは、Nの値を変えて平均時間計算量を求めるようになっています。

hanteiという関数が再帰関数になっているのですが、実行すると無限ループが発生してしまいます。

探索終了したらmain関数に戻りたいのですが、どのようにすればよいでしょうか。

それとも、このようなプログラムの書き方が間違っているのでしょうか？

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define visit 1
#define nonvisit 0
#define revisit 2
#define stop 2
#define M 100

int i,j,k,min,sum;
clock_t start_clock, end_clock;
int a[M+1][M+1], r[M+1][M+1], d[M+1], v[M+1];

void ransuu(int);

int hantei(int, int, int);

int main(void){
    srand((unsigned int)time(NULL));
    int sum2,b[M+1];
    for(int n=1;n<=M;n++){
        start_clock=0,end_clock=0;
        printf("%d回目\n",n);
        ransuu(n);
        start_clock=clock();
        hantei(1,n,n);
        end_clock=clock();
        b[n]=(double)(end_clock-start_clock)/CLOCKS_PER_SEC;
        sum2+=b[n];
    }
    printf("平均時間計算量:%f\n",sum2/M);
    return 0;
}

void ransuu(int N){
    printf("Adjacency Matrix:\n");

    for(i = 1; i <= N; i++){
        for(j = 1; j <=N; j++){
            a[i][j]=rand()%2;
            if(i==j) a[i][j]=0;
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }

    printf("Flowing Matrix:\n");

    for(i = 1; i <= N; i++){
        for(j = 1; j <=N; j++){
            if(a[i][j]==1){
                r[i][j]=rand()%100;}else{
                    r[i][j]=0;
                }
            printf("%3d",r[i][j]);
        }
    printf("\n");
    }
}

int hantei(int s,int t,int N){
    int current, count, p=0;
    current=s; count=1; min=N+1;

    for(k=1;k<=N;k++){
        v[k]=nonvisit;
        d[k]=0;
    }

    v[s]=visit; d[count]=current;
    j=current;

    while(current!=t){
        if(v[t]==visit) break;
        if((a[current][j]==1)&&(v[j]==nonvisit)){
            printf("%dから%dへ行く\n",current,j);
            if(j>N){
                if(p==N){
                    printf("探索終了\n");
                    printf("最大流量は%d\n",sum);
                    return 1;
                }
                if(v[d[count]]=revisit){
                    v[d[count]]=nonvisit;
                    current=d[count-1];
                    p++;
                    j=1;
                    continue;
                }
                v[current]=revisit;
                current=d[count-1];
                count--;
                p++;
                j=1;
                continue;
            }
            count++;
            d[count]=j;
            printf("d[%d]:%d\n",count,j);
            v[j]=visit;
            if(r[current][j]<min) min=r[current][j];
            current=j;
            j=0;
        }
        j++;
    }

    int l=count;
    printf("min:%d\n",min);
    sum+=min;

    for(count=1;count<l;count++){
        printf("r[%d][%d]:%d\n",d[count],d[count+1],r[d[count]][d[count+1]]);
        r[d[count]][d[count+1]] = r[d[count]][d[count+1]]-min;
        if(r[d[count]][d[count+1]]==0) a[d[count]][d[count+1]]=stop;
        printf("r[%d][%d]:%d\n",d[count],d[count+1],r[d[count]][d[count+1]]);
    }
    hantei(s,t,N);//1回目はだいだいこの部分にたどり着く
    return 1;//このreturnが必要
}

###追記
回答ありがとうございました。
最初にhanteiを呼び出したときに、return文を下につけておかなかったことで、判定終了して再帰関数で戻ったときに、hantei関数が終了しなかったのが原因だったようです。

Comments

[pepperleaf]

シンプルに無限ループ。
hantei()の最後で、hantei()を読んでますね。
細かなところまで読んでないので、こちらの指摘とします。

Answer 1

ロジックを追っていませんが、
なぜ『再帰関数』なのに、『終了するための条件』がないのでしょうか。

別の例を出すと、

while( 1 ){
    printf("Hello");
}

と大差ないです。

ロジックを追ってみてください。

1. 以下の処理をする
   1.1. "Hello"を表示する

なのですが、『終了するにはどうすればいいでしょうか』。

(1) -> (1.1) -> (1) -> (1.1) -> (1) ...

と動きますが、『いつ終了するのでしょうか』。

終了の条件が無いので、無限ループに陥ります。

これを

int a = 0;
while( a <= 100 ){
    a++;
    printf("Hello");
}

のようにするとどうでしょうか。

1. a を 0 で初期化
2. a が 100 以下なら
　　2.1. a をインクリメント( +1 する )
　　2.2. "Hello"と表示する

とするのですね。

となると、

まず(1)でa = 0 なので 0≦100 に該当するので ループ条件を満たす。
だから (2.1)や(2.2)を処理。
すると a++ は a = a + 1 と一緒なので 0 + 1 = 1 だから a = 1 となる。
また (1) に戻って a = 1 なので 1≦100 に該当するのでループ条件を満たす。
...
a = 101 になっているとき、101≦100 を満たさないので終了。

となりますね。

そういう風に終了条件があるので終了可能です。

でも質問にあるものだと、シンプルに書くと、

while( 1 ){
    printf("Hello");
}

なので、

1という条件を満たす。だから printfの部分を処理。
1という条件を満たす。だから printfの部分を処理。
...

という風に『終了条件がない』ので終了できず、無限ループに陥る。

これを再帰関数としてやっているのです。

デバッガで処理を追ってみてください。
すると、『処理を終了する条件がない』ことに気づくはずです。

---

[追記1]

通常、再帰関数は

型  関数名(引数){
    if( /* 終了の条件 */ ) return   戻り値;
    
    // ここで再帰してまでやりたい処理
    自分関数を呼び出す(...);
return   戻り値;
}

のような感じで『最初に終了の条件を書く』のが一般的らしいです。(あくまでパターン的に。必ずではないと思いますが)