Я хочу знать, как это работает
Я хочу знать, что произошло после самого вызова этой функции: она возобновится или будет продолжать вызывать себя до тех пор, пока условие не станет ложным.
void mergeSort(int arr[], int l, int r)
{
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
читайте на как работает рекурсия в C
Я не совсем понимаю, о чем вы спрашиваете, но, похоже, вы ищете базовое объяснение рекурсии (которое вы, вероятно, можете найти в Интернете).
@Gerhardh Кому-то, кто не понимает рекурсию, вероятно, будет трудно отлаживать рекурсивную функцию или даже просто отладить период.
@Dukeling Это как раз та ситуация, когда сеанс отладчика может сказать вам более тысячи слов. Повторение одного и того же кода снова и снова и, возможно, просмотр стека вызовов может открыть вам глаза на рекурсию. Возможно, версия p&p слишком сложна, я согласен.
Ответы 1
it will keeping calling itself until condition became false
да, вот как это работает.
Алгоритм берет диапазон от l до r, разбивает его на два диапазона и вызывает mergesort для каждого из диапазонов.
Пример (для краткости я использую ms вместо mergeSort)
Первоначальная серия звонков:
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
Поскольку значения 0 и 0 не соответствуют условию l < r, этот вызов просто вернется, и будет выполнен второй вызов mergeSort на предыдущем уровне рекурсии. Ведущий к:
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
|
--> ms(a, 1, 1)
Еще раз значения 1 и 1 не соответствуют условию l < r, так что этот вызов просто вернется, а после merge мы вернемся на предыдущий уровень рекурсии и выполним второй вызов mergeSort на этом уровне.
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
| |
| --> ms(a, 1, 1)
|
--> ms(a, 2, 2)
2 и 2 просто заставляют нас вернуться на предыдущий уровень рекурсии, где mergeSort вызывается во второй раз. Думаю, теперь вы видите картинку ...
ms(a, 0, 8) ---> ms(a, 0, 4) ---> ms(a, 0, 2) ---> ms(a, 0, 1) ---> ms(a, 0, 0)
| | | |
| | | --> ms(a, 1, 1)
| | |
| | --> ms(a, 2, 2)
| |
| --> ms(a, 3, 4) ---> ms(a, 3, 3)
| |
| --> ms(a, 4, 4)
|
--> ms(a, 5, 8) ---> ... finish this your self ...
Другой подход к пониманию последовательности вызовов - добавить «уровень рекурсии» и выполнить простую печать при вызове mergeSort:
#include <stdio.h>
void mergeSort(int arr[], int l, int r, int level)
{
printf("Recursion level %d l=%d r=%d\n", level, l, r);
if (l < r)
{
// Same as (l+r)/2, but avoids overflow for
// large l and h
int m = l+(r-l)/2;
// Sort first and second halves
mergeSort(arr, l, m, level+1);
mergeSort(arr, m+1, r, level+1);
// merge commented out as it is irrelevant for the call sequence
// merge(arr, l, m, r);
}
}
int main()
{
int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
mergeSort(a, 0, 8, 0);
return 0;
}
Выход:
Recursion level 0 l=0 r=8
Recursion level 1 l=0 r=4
Recursion level 2 l=0 r=2
Recursion level 3 l=0 r=1
Recursion level 4 l=0 r=0
Recursion level 4 l=1 r=1
Recursion level 3 l=2 r=2
Recursion level 2 l=3 r=4
Recursion level 3 l=3 r=3
Recursion level 3 l=4 r=4
Recursion level 1 l=5 r=8
Recursion level 2 l=5 r=6
Recursion level 3 l=5 r=5
Recursion level 3 l=6 r=6
Recursion level 2 l=7 r=8
Recursion level 3 l=7 r=7
Recursion level 3 l=8 r=8
Тот же результат, но с отступом, зависящим от уровня:
Recursion level 0 l=0 r=8
Recursion level 1 l=0 r=4
Recursion level 2 l=0 r=2
Recursion level 3 l=0 r=1
Recursion level 4 l=0 r=0
Recursion level 4 l=1 r=1
Recursion level 3 l=2 r=2
Recursion level 2 l=3 r=4
Recursion level 3 l=3 r=3
Recursion level 3 l=4 r=4
Recursion level 1 l=5 r=8
Recursion level 2 l=5 r=6
Recursion level 3 l=5 r=5
Recursion level 3 l=6 r=6
Recursion level 2 l=7 r=8
Recursion level 3 l=7 r=7
Recursion level 3 l=8 r=8
Добро пожаловать в SO. Для таких крошечных программ вам следует начать использовать отладчик. Это поможет вам пройтись по коду и посмотреть, что произойдет. Вы также можете выполнить инструкции ручкой и бумагой.