遞歸氣泡排序

Question

我遇到了一些麻煩。我們基本上被要求創建一個程序的兩個版本，該程序將對50個項目的數組進行排序，然後顯示LED中最大的數字。我已經使用基本的氣泡排序並顯示它。我的問題是當我必須使用遞歸來做到這一點。不幸的是，我對遞歸的瞭解非常有限，因爲我錯過了關於它的講座 - 他也沒有在線上放置筆記。我有一個很長的谷歌，但仍然無法讓我的頭靠近它。所以我問幾件事。首先，有人可以解釋使用sedo代碼進行氣泡排序的遞歸。其次，我的嘗試完全錯了嗎？

int numbers[49]; 

void setup() 
{     
    pinMode(12, OUTPUT); 
    pinMode(11, OUTPUT); 
    pinMode(10, OUTPUT); 
    pinMode(9, OUTPUT); 
    pinMode(8, OUTPUT); 
    pinMode(7, OUTPUT); 
    pinMode(6, OUTPUT); 
    pinMode(5, OUTPUT); 
    Serial.begin(9600); 
} 

void loop() 
{ 
    resetLEDLow(); 
    genNumbers(); 
    sortNumbers(); 
    displayNumber(); 
    delay(5000); 
} 

void resetLEDLow() 
{ 
    digitalWrite(12, LOW); 
    digitalWrite(11, LOW); 
    digitalWrite(10, LOW); 
    digitalWrite(9, LOW); 
    digitalWrite(8, LOW); 
    digitalWrite(7, LOW); 
    digitalWrite(6, LOW); 
    digitalWrite(5, LOW); 
} 

void genNumbers() 
{ 
    for(int i = 0 ; i < 50 ; i++) 
    { 
    numbers[i] = random(256); 
    } 
} 

void sortNumbers() 
{ 
    int sizeOfArray = sizeof(numbers)/sizeof(int); 
    int check = 1; 
    if(check != 0) 
    { 
    check = 0; 
    for(int i = 0 ; i < sizeOfArray ; i++) 
    { 
     for (int j = 1 ; j < sizeOfArray ; j++) 
     { 
     if(numbers[j-1] > numbers[j]) 
     { 
      int temp = numbers[j-1]; 
      numbers[j-1] = numbers[j]; 
      numbers[j] = temp; 
      check++; 
     } 
     } 
    } 
    sortNumbers(); 
    } 
} 

void displayNumber() 
{ 
    int i = 12; 
    int a = numbers[49]; 
    Serial.println(numbers[49]); 
    while (a > 0) 
    { 
    int num = a % 2; 
    a = a/2; 
    if(num == 1) 
    { 
     digitalWrite(i, HIGH); 
    }else{ 
     digitalWrite(i, LOW); 
    } 
    i--; 
    } 
} 

我知道，代碼不工作當它循環輪數被重置爲1這樣的條件永遠不會爲真因而這意味着將環圓，直到永遠。那麼，我需要改變什麼或者我所做的並不是真的遞歸呢？

真的需要一些幫助，讓我的大腦四處走動。

編輯：這是我的新遞歸嘗試。我刪除了與問題無關的代碼。

void loop() 
{ 
    int topLevel = 0; 
    int currentSort = 0; 
    int sizeOfArray = sizeof(numbers)/sizeof(int); 
    int numbers[49]; 
    sortNumbers(topLevel,currentSort,sizeOfArray,numbers); 
} 

int sortNumbers(p,c,l,numbers) 
{ 
// Swap if they are in the wrong order 
if(numbers[c-1] > numbers[c]) 
{ 
    int temp = numbers[c-1]; 
    numbers[c-1] = numbers[c]; 
    numbers[c] = temp; 
} 
// If we have finished this level and need to go to next level 
if(c == l) 
{ 
    c = 0; 
    p++; 
} 
// Finished 
if(p == l+1) 
{ 
    return numbers; 
} 
// Continue to the next place 
return sortNumbers(p,c+1,l, numbers); 
} 

Sort50Rec:-1: error: 'p' was not declared in this scope Sort50Rec:-1: error: 'c' was not declared in this scope Sort50Rec:-1: error: 'l' was not declared in this scope Sort50Rec:-1: error: 'numbers' was not declared in this scope Sort50Rec:-1: error: initializer expression list treated as compound expression Sort50Rec.cpp: In function 'void loop()': Sort50Rec:19: error: 'numbers' was not declared in this scope Sort50Rec:21: error: 'sortNumbers' cannot be used as a function Sort50Rec.cpp: In function 'void genNumbers()': Sort50Rec:42: error: 'numbers' was not declared in this scope Sort50Rec.cpp: At global scope: Sort50Rec:46: error: redefinition of 'int sortNumbers' Sort50Rec:-1: error: 'int sortNumbers' previously defined here Sort50Rec:46: error: 'p' was not declared in this scope Sort50Rec:46: error: 'c' was not declared in this scope Sort50Rec:46: error: 'l' was not declared in this scope Sort50Rec:46: error: 'numbers' was not declared in this scope

我的可以肯定的一部分的方式，我的權利我命名功能，我在想你可以只返回一個值？或不？

編輯：修正錯誤指出新的錯誤。

void loop() 
{ 
    int topLevel = 0; 
    int currentSort = 0; 
    int numbers [49]; 
    int sizeOfArray = sizeof(numbers)/sizeof(int); 
    numbers = sortNumbers(topLevel,currentSort,sizeOfArray,numbers); 
} 

int sortNumbers(int p,int c,int l,int numbers) 
{ 
// Swap if they are in the wrong order 
if(numbers[c-1] > numbers[c]) 
{ 
    int temp = numbers[c-1]; 
    numbers[c-1] = numbers[c]; 
    numbers[c] = temp; 
} 
// If we have finished this level and need to go to next level 
if(c == l) 
{ 
    c = 0; 
    p++; 
} 
// Finished 
if(p == l+1) 
{ 
    return numbers; 
} 
// Continue to the next place 
return sortNumbers(p,c+1,l, numbers); 
} 

Sort50Rec.cpp: In function 'void loop()': Sort50Rec:19: error: invalid conversion from 'int*' to 'int' Sort50Rec:19: error: initializing argument 4 of 'int sortNumbers(int, int, int, int)' Sort50Rec:19: error: incompatible types in assignment of 'int' to 'int [49]' Sort50Rec.cpp: In function 'void genNumbers()': Sort50Rec:40: error: 'numbers' was not declared in this scope Sort50Rec.cpp: In function 'int sortNumbers(int, int, int, int)': Sort50Rec:47: error: invalid types 'int[int]' for array subscript Sort50Rec:47: error: invalid types 'int[int]' for array subscript Sort50Rec:49: error: invalid types 'int[int]' for array subscript Sort50Rec:50: error: invalid types 'int[int]' for array subscript Sort50Rec:50: error: invalid types 'int[int]' for array subscript Sort50Rec:51: error: invalid types 'int[int]' for array subscript Sort50Rec.cpp: In function 'void displayNumber()': Sort50Rec:71: error: 'numbers' was not declared in this scope

感謝

Answer 1

你有多餘的檢查造成一個無限循環。現在

void sortNumbers() 
{ 
    ... 
    int check = 1; 
    if(check != 0) 
    { 
    ... 
    sortNumbers(); 
    } 
} 

，因爲這是顯然的功課，我只是提供一些一般性的建議。一般來說，您使用遞歸來減小特定大小的問題。找出問題的哪一部分變得越來越小，並且每次迭代都要進行遞歸調用而不是循環（提示：這意味着您可能希望將一些值傳遞給方法以告訴您的大小和/或當前迭代的位置）。並且記得在方法開始時或者在遞歸檢查問題的大小之前進行檢查。

---

void loop() 
{ 
    int topLevel = 0; 
    int currentSort = 0; 
    /* You never initialize this - what's supposed to be in it? */ 
    int numbers [49]; 
    int sizeOfArray = sizeof(numbers)/sizeof(int); 
    /* Two things here: you're passing an array (numbers) in where the 
    sortNumbers() function has it declared as an int; 
    and the return value is declared as an int, but you're storing it 
    into an array. */ 
    numbers = sortNumbers(topLevel,currentSort,sizeOfArray,numbers); 
} 

/* You're going to have to change this method signature - you're working 
    with arrays, not plain ints. You're changing numbers[] inline, so you 
    don't need to return anything. */ 
int sortNumbers(int p,int c,int l,int numbers) 
{ 
/* The first iteration has c = 0, so [c-1] is going to be out-of-bounds. 
    Also, when c = l, [c] will be out of bounds. */ 
if(numbers[c-1] > numbers[c]) 
{ 
    int temp = numbers[c-1]; 
    numbers[c-1] = numbers[c]; 
    numbers[c] = temp; 
} 
if(c == l) 
{ 
    c = 0; 
    p++; 
} 
if(p == l+1) 
{ 
    return numbers; 
} 
return sortNumbers(p,c+1,l, numbers); 
} 

這不是我想這樣做的，但我相信，一旦你解決問題，我已經指出了（可能還有一些我錯過了），它應該工作。