【至急】再帰的なプログラムを非再帰的なものへ

[みなみ]

再帰的なプログラムを非再帰的なものへと書き換えたいです。
途中まで挑戦していたのですが、うまくいきません。
関数recurAが元の関数で、この表記方法と同じ表記にするように関数recurBを書き換えたいです。
情けないながら未だ初心者知識しかなく、理解力に乏しい状況です。
そこで、大変申し訳ないのですがわかりやすい解説も頂ければ幸です。
何卒よろしくお願い申し上げます。
環境はLinuxです。
以下未完成のソースになります。

//再帰に対する理解を深めるための真に再帰的な関数３
#include <stdio.h>

/*真に再帰的な関数recurA*/

void recurA(int n)
{
if(n>0){
if(n%2 == 0) recurA(n/2);
else recurA(n-1);
printf("%d",n);
recurA(n-2);
}
}



/*再帰を除去した関数recurB*/
void recurB(int n){//0
int D,K;
D = K = 0;
D = K = n;


/*------第１判定------*/
Top:

if(n>1){

if(n%2==0){
n = n/2;
}

else {
n = n-1;
}
printf("%d",n);
goto Top;
}


/*------与えられたnを表示させる------*/
if(D==K)printf("%d",D);


/*------第2判定------*/
D = D-2;
n = D;

if(D>0){
printf("%d",D);
goto Top;
}
}





int main(void)
{
int x;

printf("整数を入力せよ : ");
scanf("%d",&x);

recurA(x);
printf("\n");

recurB(x);
printf("\n");

return 0;
}

[double-clutch.]

今晩は　double-clutch.　と申します。
自分も初心者です。

ソースコードはタグ で囲ってください。
[ code] と [ /code] ....　ここでは　[　の直後に『半角スペース』を入れていますが、投稿される際は不要です。

あなたのcode

► スポイラーを表示

コード:

//再帰に対する理解を深めるための真に再帰的な関数３
#include <stdio.h>

/*真に再帰的な関数recurA*/

void recurA(int n)
{
	if(n > 0){
		if(n % 2 == 0) recurA(n/2);
		else recurA(n - 1);

		printf("%d", n);
		recurA(n - 2);
	}
}



/*再帰を除去した関数recurB*/
	void recurB(int n) { //0
		int D, K;
		
		D = K = 0;
		D = K = n;


		/*------第１判定------*/
		Top:

		if(n > 1){

		if(n % 2 == 0){
		n = n/2;
		}

		else {
		n = n - 1; 
		}
		printf("%d",n);
		goto Top; 
		} 


		/*------与えられたnを表示させる------*/
		if(D==K)printf("%d",D);


	 	/*------第2判定------*/
		D = D-2;
		n = D;

		if(D>0){ 
		printf("%d",D);
		goto Top;
		}
	}





int main(void)
{
	int x;

	printf("整数を入力せよ : ");
	scanf("%d",&x);

	recurA(x);
	printf("\n");

	recurB(x);
	printf("\n");

 	return 0;
}

....　すいません、28行目の記述...

コード:

		Top:

とは、なんでしょうか??

上記のプログラムの実行結果は次になりました。
整数を入力せよ : 今回は 10 を入力しました。


1241251231101241281231612412
5421108421632142121

[box]

....　すいません、28行目の記述...

コード:

		Top:

とは、なんでしょうか??

goto文の飛び先を示すラベルです。
コードの中に
goto Top;
っていう記載がありますよね。

[みなみ]

仰るとおり、Topはこのソースコードに置けるラベルとなっております。
goto Topに差し掛かったら自動でTop:の箇所まで戻り、そこから再び実行されます。

はいの整数１０の場合上の関数Aが正しい表記なので、下のBを上と同じ表記にさせたいのです。
1241251231101241281231612412
5421108421632142121

個人的な見解としては、n-2まで実行した後のnがn-1の判定を通り抜けてしまっているものと思っています。
それとnのソートがうまくいっていないため、正しいnが求められていても、正しいならびかたになりません...。

[box]

それとnのソートがうまくいっていないため、正しいnが求められていても、正しいならびかたになりません...。

nのソートって何でしょうか。
そもそも、再帰呼び出しを使った想定解を出力するコードにおいて
nをソートしているわけではなさそうに見えますので、
非再帰の場合においても同様なのではないですか？

[double-clutch.]

みなみ　さん


再帰処理では、仮引数の値を使用して何かしらの処理をさせるのですが、

この『仮引数の値』を使う順番が、『FILO (入れ後出し)』または、『FIFO(先入れ先出し)』で使用していきます。
つまり、データ構造『スタック』『キュー』に『仮引数の値』を『push』または『enq』し、
それらの情報を使いたいときに、『pop』または『deq』すればよいことになります。

具体的には、

コード:

void recurA(int n)
{
    if(n > 0){
        if(n % 2 == 0) recurA(n/2);
        else recurA(n - 1);
 
        printf("%d", n);
        recurA(n - 2);
    }
}

の『仮引数の値を使用して何かしらの処理をさせる』部分の

コード:

        printf("%d", n);

以前に呼び出しに使用した引数（== 次の関数での仮引数）が、『FILO (入れ後出し)』、
以後に呼び出しに使用した引数（== 次の関数での仮引数）が、『FIFO(先入れ先出し)』となります。


ここまで、偉そうに書いていますが自分は『スタック』までしか学習していません。
なので、『仮引数の値を使用して何かしらの処理をさせる』部分の、以前の記述しかでませんでした。

あと、出力形式が少し違いますがご了承ください。

► スポイラーを表示

コード:

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

#define SIZE 30

typedef struct {
	int dete[SIZE];
	int sp;					// stack_pointer の略...
} stack;

/*	スタックの実装の注意点
	一　情報を構造体 stack のメンバ配列 dete に保持する
	二　配列 dete の取り出し処理の対象要素を、メンバ変数 sp で指定したい。
	三　『空のスタック』状態では、メンバ変数 sp の値を 0 とする
	四　データの数をメンバ変数 sp で、1_bace で表現する
		一方、添字は 0_bace である点に注意する
 */

// 再帰関数のプロトタイプ
void recur(int, int);
void recur_goto(int);


// stack 処理の関数プロトタイプ
int pop(stack *);
void push(stack *, int);



void recur(int N, int count) {
	if (N > 0) {
		if (N % 2 == 0) recur(N / 2, count + 1);
		else recur(N - 1, count + 1);
		
		fprintf(stdout, "仮引数 N の値:: %3d 関数の使用回数:: %2d\n", N, count);
	}
}


/* 再帰処理を、再帰を用いず表現する.... */
void recur_goto(int N) {
	stack s_1;
	s_1.sp = 0;
	
	Top:
	if (N > 0) {
		
		
		if (N % 2 == 0) {
			push(&s_1, N );
			N /= 2;
		}
		else {
			push(&s_1, N);
			N -= 1;
		}
		goto Top;
	}
	
	while (s_1.sp != 0.) fprintf(stdout, "仮引数 N の値:: %3d\n", pop(&s_1));
}



int main(void)
{
	int i;					// 入力値受け取り用
	char str[SIZE];			// 入力値受け取り用
	
	fputs("整数値を入力してください ::", stdout);
	i = atoi(fgets(str, SIZE, stdin));
	
	recur(i, 1);
	
	fputc('\n', stdout);
	
	recur_goto(i);
	
	return 0;
}

void push(stack *p, int i) {
	if (p->sp >= SIZE) exit(1); 	// エラー処理
	else  p->dete[++(p->sp) - 1] = i;
}

int pop(stack *p) {
	if (p->sp == 0) exit(2); 	// エラー処理
	return (p->dete[(p->sp)-- - 1]);
}

みなみ　さん　の質問には答えきれていませんが、参考程度にどうぞ

[かずま]

スタックを使えばよいのでは？

コード:

#include <stdio.h>

int s[10000], p;

void recurB(int n)
{
    while (1) {
        while (n > 0) {
            s[p++] = n;
            n = n & 1 ? n - 1 : n / 2;
        }
        if (p == 0) return;
        n = s[--p];
        printf(" %d", n);
        n -= 2;
    }
}

int main(void)
{
    int x;

    while (printf("整数を入力せよ : "), scanf("%d", &x) == 1) {
        recurB(x);
        printf("\n");
    }
    return 0;
}

[かずま]

元のプログラムに合わせて、n & 1 を (n % 2 == 0) にしました。

コード:

#include <stdio.h>

void recurB(int n)
{
    static int s[10000], p;

    while (1) {
        while (n > 0) {
            s[p++] = n;
            n = (n % 2 == 0) ? n / 2 : n - 1;
        }
        if (p == 0) return;
        n = s[--p];
        printf(" %d", n);
        n -= 2;
    }
}

int main(void)
{
    int x;

    while (printf("整数を入力せよ : "), scanf("%d", &x) == 1) {
        recurB(x);
        printf("\n");
    }
    return 0;
}