再帰表現への書き換えが上手くいかず困っています。

[重曹]

申し訳ないです。どうしても自分で解答できないので質問させて頂きます。
C言語ど素人で初めてこのフォーラムを利用するので何か良からぬ間違いをしているかもしれません。
規約にも目を通しましたが、それでも何かしでかしているかもしれません。申し訳ないです。

提示された関数を再帰表現へと書き換えるように空欄を埋めろ、という問題が出題されたのですが、
どうにも上手く解答できずに困っております。

元の関数が以下のfunction1です。
動かしていただければわかると思いますが、要するに引数xと引数yをかけた結果を
出力する関数となっています。

コード:

int f4(int x, int y){
	int r;
	for(r=0; y>0; y = y/2){
		if(y%2 == 1){
			r= r+x;
		}
		x = x*2;
	}
	return r;
}

次に、穴埋め問題として出題された関数function2です。

コード:

int function2(int x, int y){
	if(y == 0){
		return /*（１）*/;
	}
	else if(y%2 == 1){
		return /*（２）*/;
　	}else{
	　　　　return function2( /*（３）*/,  /*（４）*/);
	}
}

function1を見て自分で解いた限りでは、
（１）x、（２）x + function2(x, y/2)、（３）x*2、（４）y/2
と入れて実行してみるのが正しいと思い動かしてみるのですが、yが偶数の時（？）に思うような値が出力されずに困っています。
例えば、x = 1, y = 2　を代入して実行すると、function1の返り値が2、function2の返り値が4となっています。

正直これ以上どう考えていいかさっぱりわかりません。
アプローチの方法をご教授いただければ幸いです。よろしくお願いいたします。

必要ないと思いますが、環境は以下のようになっています。
OS:Windows7 Home Premium
コンパイラ:明確に何を使用しているかはわかりませんがVisual Studio 2010のデフォルトものを使用しています。
ライブラリはstdio.hのみ使用しているため、おそらくどのような環境でも同じ結果が出力されると思います。

よろしくお願いいたします。

[みけCAT]

元の関数を、自分で再帰を用いて書いてみました。

コード:

function2 x y
 | y<=0 = 0
 | otherwise = let next = function2 (x*2) (div y 2)
               in if (mod y 2)==1 then x+next else next

比較すると、(1)と(2)が異なっているようですね。

[みけCAT]

途中経過を表示してみると、何かわかるかもしれません。

コード:

#include <stdio.h>

int f4(int x, int y){
    int r;
    puts("r\tx\ty");
    printf("%d\t%d\t%d\n",0,x,y);
    for(r=0; y>0; (y = y/2),printf("%d\t%d\t%d\n",r,x,y)){
        if(y%2 == 1){
            r= r+x;
        }
        x = x*2;
    }
    return r;
}

int main(void) {
	int a,b;
	while(scanf("%d%d",&a,&b)==2 && a>=0 && b>=0) {
		printf("result=%d\n",f4(a,b));
	}
	return 0;
}

再帰処理では、このコードで出力される表の上から関数が呼び出され、一番下に到達したあと上に向かって計算していきます。
(仮想的な)rに数値を足す順番は、元のコードと逆になります。

[non]

例えば６×５を計算する場合、
２進数であらわすと
１１０　×　１０１　です。
ですから
（１１０　×　１）×１　＋（１１０　×　１０）×０　＋　（１１０　×　１００）×１
これが、最初のプログラムの考え方ですね。

　

[重曹]

解決しました。

コード:

int function2(int x, int y){
	puts("x\ty");
    printf("%d\t%d\n",x,y);
	if(y == 0){
		return 0;
	}
	else if(y%2 == 1){
		return x + f6(x*2, y/2);
	}else{
		return f6(x*2, y/2);
	}
}

みけCAT様の
＞＞再帰処理では、このコードで出力される表の上から関数が呼び出され、一番下に到達したあと上に向かって計算していきます。
＞＞(仮想的な)rに数値を足す順番は、元のコードと逆になります。

この２文でモヤモヤしていたわかりづらい再帰表現に関するイライラがスッキリしました。
本当にありがとうございました。