recursion function的問題

c recursive 程式設計程式語言遞迴

pilistar0222 2016-07-01 18:04:47 ‧ 3008 瀏覽

分享至

輸入字串 => 1, 3 , (2,4,6), 5, 7
輸出以下

1+3

1+ ( (2+4)+(2+6)+(4+6))

1+5

1+7

3+ ( (2+4)+(2+6)+(4+6))

3+5

3+7

( (2+4)+(2+6)+(4+6)) +5

( (2+4)+(2+6)+(4+6))+7

5+7

我在練習遞迴,所以我寫了一個會先計算題目中(2,4,6)的總和的程式,
但出來總和一直是錯誤的

以下是我的程式片段

#include<stdio.h>
     int recursion(int* array,int i,int j,int size){
     	int sum = 0;
            if(i < size-1){
                   if(j < size ){
                        printf("%d\n",array[i]+array[j]);
                        sum = sum+array[i]+array[j];
                        j++;
                        recursion(array,i,j,size);
                   }
                   else{
                         printf("\n");
                         i++;
                         j=i+1;
                         recursion(array,i,j,size);
                   }
            }       
            return sum;
     }

    int main(){
       int i=0,j=i+1,sum=0;
       int a[3]={2,4,6};
      
       int c =recursion(a,i,j,3);
       printf("\n\n%d",c);
       return 0;
    }

程式print的地方都是正確的都有印出來,但是sum 一直只有算到 6 (應該是2+4算出的)

所以好像只有抓到第一次進入遞迴function的樣子!

請問錯誤在哪裡呢??

看更多先前的討論...收起先前的討論...

weiclin iT邦高手 4 級 ‧ 2016-07-01 18:08:55 檢舉

(2,4,6) 的總合為什麼是 ( (2+4)+(2+6)+(4+6)) ?

pilistar0222 iT邦新手 5 級 ‧ 2016-07-01 18:12:59 檢舉

題目的要求是這樣@@，但我算不出來

pilistar0222 iT邦新手 5 級 ‧ 2016-07-01 18:13:57 檢舉

題目要求的那些1+3
1+ ( (2+4)+(2+6)+(4+6))
1+5
1+7 那些應該也都是要算出來然後print的

weiclin iT邦高手 4 級 ‧ 2016-07-01 18:54:12 檢舉

看起來比較像是"組合", 不是"總和"

weiclin iT邦高手 4 級 ‧ 2016-07-01 19:15:59 檢舉

然後先不要管什麼組合跟總和了, 你的 main 裡面的 sum 跟函式裡面的 sum 根本不是同一個變數, 你知道區域變數嗎? 另外 recursion 裡面 return sum, 那呼叫 recursion 的地方是不是都要加上這些 return 的 sum?

pilistar0222 iT邦新手 5 級 ‧ 2016-07-01 22:57:40 檢舉

我知道兩個是不一樣的區域變數我知道，我也知道它CALL BY VALUE 只是複製進去而已
我把它改成
int recursion(int* array,int i,int j,int size,int sum){
if(i < size-1){
if(j < size ){
printf("%d\n",array[i]+array[j]);
sum = sum+array[i]+array[j];
j++;
sum+recursion(array,i,j,size,sum);

}
else{
printf("\n");
i++;
j=i+1;
sum+recursion(array,i,j,size,sum);
}
}
return sum;
}
相加起來則是回傳一個很怪的數

weiclin iT邦高手 4 級 ‧ 2016-07-02 00:25:16 檢舉

所以正確的數字應該是什麼?

pilistar0222 iT邦新手 5 級 ‧ 2016-07-02 09:59:41 檢舉

fillano iT邦超人 1 級 ‧ 2016-07-02 13:20:06 檢舉

你的處理方式（遞增陣列索引）沒辦法處理4取2耶？你要先正確遞迴出組合的方式再做計算吧？

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

2 個回答

海綿寶寶

iT邦大神 1 級 ‧ 2016-07-02 11:39:37

最佳解答

#include<stdio.h>
     int recursion(int* array,int i,int j,int size){
     	int sum = 0;
            if(i < size-1){
                   if(j < size ){
                        printf("+(%d+%d)",array[i], array[j]);
                        sum = sum+array[i]+array[j];
                        j++;
                        sum = sum + recursion(array,i,j,size);
                   }
                   else{
                         i++;
                         j=i+1;
                         sum = sum + recursion(array,i,j,size);
                   }
            }       
            return sum;
     }

    int main(){
       int i=0,j=i+1,sum=0;
       int a[3]={2,4,6};
      
       int c =recursion(a,i,j,3);
       printf("=%d",c);
       return 0;
    }

回應 2
分享
檢舉

海綿寶寶 iT邦大神 1 級 ‧ 2016-07-02 11:41:42 檢舉

運氣好的話, 這裡可以看到執行結果

pilistar0222 iT邦新手 5 級 ‧ 2016-07-02 13:43:16 檢舉

感謝，我試過return sum = sum + recursion(array,i,j,size);
這樣意思差不多怎麼就會抓到奇怪的值@@

登入發表回應

WilliamHuang

iT邦研究生 1 級 ‧ 2016-07-01 22:24:26

【＊＊此則訊息已被站方移除＊＊】

fillano

iT邦超人 1 級 ‧ 2016-07-02 15:23:02

我寫一個Javascript的例子，你再用C實作看看：

function compose2(arr) {
    if(arr.length < 2) return [];
    if(arr.length > 2) {
        var ret = [];
        for(let i=1; i<arr.length; i++) {
            ret.push([arr[0], arr[i]]);
						//用陣列第一個元素跟其他元素組合
        }
        return ret.concat(compose2(arr.slice(1)));
				//拿掉陣列第一個元素再遞迴下去
    } else {
        return [arr];
				//如果傳入陣列只有兩個元素，直接返回
    }
}

//var a = [1,2,5,3,8,15,24];
var a = [2, 4, 6];
console.log(compose2(a, 2));
//印出 [ [ 2, 4 ], [ 2, 6 ], [ 4, 6 ] ]
console.log(compose2(a, 2).reduce(function(p, c) {return p + c[0] + c[1]}, 0));
//印出 24

我的作法是先找出所有組合，再把這些組合算出來。