無限遞歸調用Objective-C

我正在執行Objective-C中的合併排序（代碼如下）我很難理解爲什麼我的遞歸調用是一個無限循環，當我不增量變量時'middle'由一個。無限遞歸調用Objective-C

所以[self sort:array fromLow:middle+1 toHigh:high];工作正常

但[self sort:array fromLow:middle toHigh:high];將我的程序變成一個無限循環。任何人都可以解釋爲什麼它發生？在這兩種情況下，if語句

if(high<=low) 
    { 
     return; 
    }

達到和執行，因此，我認爲我的計劃將進入第三語句（mergeLow：andHigh：andMiddle：inArray：andHelperArray :) 但它不」噸。

排序方法：

-(void)sort:(NSMutableArray *)array fromLow:(unsigned long)low toHigh:(unsigned long) high{ 


    if(high<=low) //recursive condition fullfilled 
    { 
     return; 
    } 
    unsigned long middle = low + (high - low)/2; //calculating middle element 

    [self sort:array fromLow:low toHigh:middle]; //(1)sort left 

    [self sort:array fromLow:middle+1 toHigh:high];//(2)sort right 

    [self mergeLow:low andHigh:high andMiddle:middle inArray:array andHelperArray:[array mutableCopy]];//(3) merge left and right 

}

調試我試圖調試。爲此，我將merge（）方法的call（3）註釋掉，並添加了高低變量的nslog語句記錄值。

MergeSort *is = [MergeSort new]; 
NSArray * a1 = @[@10,@9,@22,@5]; 
[is sort:a1.mutableCopy fromLow:0 toHigh:a1.count];

更新排序方法

-(void)sort:(NSMutableArray *)array fromLow:(unsigned long)low toHigh:(unsigned long) high{ 
    //recursive condition fullfilled 

    NSLog(@"High: %lu Low %lu ",high, low); 
    if(high<=low) 
    { 

     return; 
    } 
    unsigned long middle = low + (high - low)/2; 

    [self sort:array fromLow:low toHigh:middle]; 

    [self sort:array fromLow:middle + 1 toHigh:high]; 

    // [self mergeLow:low andHigh:high andMiddle:middle inArray:array andHelperArray:[array mutableCopy]]; 

}

調試輸出：中間+ 1

2013-10-28 11:37:21.484 Algorithms[52598:303] High: 4 Low 0 
2013-10-28 11:37:21.486 Algorithms[52598:303] High: 2 Low 0 
2013-10-28 11:37:21.486 Algorithms[52598:303] High: 1 Low 0 
2013-10-28 11:37:21.487 Algorithms[52598:303] High: 0 Low 0 
2013-10-28 11:37:21.487 Algorithms[52598:303] High: 1 Low 1 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 2 Low 2 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 4 Low 3 
2013-10-28 11:37:21.488 Algorithms[52598:303] High: 3 Low 3 
2013-10-28 11:37:21.489 Algorithms[52598:303] High: 4 Low 4

現在，在相同的方法我執行[self sort:array fromLow:middle toHigh:high];不增加middle變量和得到以下輸出：

調試輸出：中間

2013-10-28 11:45:55.689 Algorithms[52674:303] High: 4 Low 0 
2013-10-28 11:45:55.691 Algorithms[52674:303] High: 2 Low 0 
2013-10-28 11:45:55.691 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.692 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.692 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.693 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.694 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.695 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.695 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.696 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.697 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.697 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.698 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.698 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.699 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.700 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.701 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.701 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 1 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 0 Low 0 
2013-10-28 11:45:55.702 Algorithms[52674:303] High: 1 Low 0

來源

2013-10-28 Janusz Chudzynski

@JohnRiselvato是的，它被稱爲遞歸。 – trojanfoe

@JohnRiselvato * facepalm * http://en.wikipedia.org/wiki/Recursion#Recursion_in_computer_science – 2013-10-28 16:29:26

@JanuszChudzynski您是否嘗試過調試程序，以確定哪些特定的調用導致了遞歸？ –

要包括在兩個呼叫中間元素（ '左' 和 '右'）。

如果你只有2個元素，所以0和1，你會得到中間元素爲0.5，這是0作爲int，並且你定義'left'爲[0]，'right'爲[ 0,1]，所以'正確'最終就是你在開始時所擁有的。

這就是爲什麼如果你定義'righ't開始在中間+ 1你不明白。因爲'左'會上到中間，'右'將會在之後開始。他們不會有任何共同點。

EDIT（一些更多的信息）：

一個概念使用遞歸算法時，你應該始終有想到的是，終端只能如果每次你做一個調用遞歸函數你莫名其妙地減少了保證問題比以前更簡單一些。

通常做的是您定義了某種可以與遞歸函數調用相關的度量，然後證明每次調用都會減少此度量。如果您知道在終止條件下該措施應該具有一定的價值，您現在可以確定問題最終會減少到終止條件並結束。

在這種情況下，您可以用作度量的是您要訂購的數組的大小。您必須保證對遞歸函數的每次調用都將採用比調用時更小的數組。當數組的右半部分最終以與原始大小相同的尺寸被調用時，您失敗了。

來源

2013-10-28 17:09:56 manecosta

無限遞歸調用Objective-C

回答

相關問題