Понимание рекурсии (применение ее к Bubble Sort)
Я пытаюсь понять, как использовать рекурсию в программах. Я понимаю, как рекурсия работает в классических примерах, таких как "факториал", Я искал по сети то же самое .... но не могу найти убедительного решения / объяснения ..
Пример итеративного кода для сортировки по пузырькам:
arr [n] -> массив с элементами ( 1..n) который должен быть отсортирован
for(i:1 to n)
for(j:1 to n-1)
if(arr[j+1]>arr[j])
swap(arr[j+1],arr[j]);
Было бы полезно, если бы кто-то мог дать подсказку о том, как поступить ...
2 ответа
Я не уверен, что Bubblesort - хороший алгоритм для отработки рекурсии. Было бы довольно некрасиво преобразовать его в рекурсию, потому что это вложенный цикл. Это выглядело бы примерно так:
function pass(i,j,n,arr)
{
if(arr[i]>arr(j))
swap(arr[i],arr[j]);
if(j==n)
{
j=0;
i=i+1;
}
if(i==n+1)
return arr;
return pass(i,j+1,n,arr);
}
Это тот же цикл for, только более длинный по определению и использующий гораздо больше памяти.
Вместо этого вам следует попробовать реализовать QuickSort. Она не требует рекурсии, и в большинстве случаев работает намного быстрее, чем BubbleSort. В большинстве платформ она уже реализована, так что вам не придется писать ее самостоятельно, но полезно знать, как она работает, и это поможет понять рекурсию.
Если вы хотите, вы также можете попробовать решить эту проблему с помощью рекурсии:
У вас есть таблица NxM чисел и начальная координата (позиция). Это позиция ^путешественника^. Путешественник может переместиться на соседнюю клетку (вправо, влево, вверх или вниз), которая имеет меньшее число, чем та, на которой он находится. Вы должны написать программу, которая вычисляет самый длинный путь, который может пройти путешественник при данных ограничениях. Используйте random для генерации массива или сгенерируйте его вручную.
Рекурсия - это метод проектирования, основанный на индуктивных доказательствах. Рассматривает один или несколько базовых (простых) случаев для вашей проблемы и один или несколько способов приблизить проблему к проблеме базового случая. Затем на каждом шаге алгоритма вы либо распознаете завершение (и соответствующим образом работаете с базовым случаем), либо делаете проблему немного ближе к базовому случаю.
Пузырьковая сортировка - это просто приложение наблюдения, что в отсортированном массиве все соседние пары элементов упорядочены. Определенный рекурсивно, он работает следующим образом:
- Базовый случай: есть массив размером 1 (или меньше) для сортировки. Конечно, отсортировано.
- Индуктивный случай: переместите самый большой элемент в верхнюю часть массива. Теперь нужно отсортировать одноэлементный массив меньшего размера, что и нужно.
Вы можете написать эту самую идею на любом языке программирования, и вы получите пузырьковую сортировку. О, но вы должны определить, что значит «пузыри на самом большом элементе». Что ж, это еще одна возможность для рекурсивного дизайна. Я думаю, вы поняли идею.
Более быстрые сортировки в основном основаны на наблюдениях за тем, как вы приближаетесь к цели с меньшим трудом. Быстрая сортировка, например, основывается на представлении о том, что если массив сортируется, то есть некоторый элемент P, и все элементы меньше P находятся слева от P, а все элементы больше P находятся справа от P. Если вы можете установить это свойство в массиве, а также выбрать P, вы можете сократить проблему примерно вдвое на каждом шаге, а не просто на один.