理解递归(在冒泡排序中应用它)

Question

我试图弄清楚如何在程序中使用递归.我理解递归如何在像"阶乘"这样的经典例子中起作用,但我不确定如何将它应用于我自己...

我开始将迭代冒泡排序代码转换为递归代码...我已经在网上搜索相同的内容......但是我无法找到令人信服的解决方案/解释..

冒泡排序的示例迭代代码是:

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]);

如果有人可以暗示如何去做,会感到很有帮助......

Answer 1

public void sort(int[] arr, int first, int last){

    if(first < last && last > 0){
        if(arr[first] > arr[first+1]){
            int temp = arr[first];
            arr[first] = arr[first+1];
            arr[first+1] = temp;
        }
        sort(arr, first+1, last);
        sort(arr, first, last-1);
    }
    else
        return;
}

迟了2年,但也许对某人有用

Answer 2

我不确定冒泡排序是否是练习递归的好算法。将其转换为递归会非常难看，因为它是一个嵌套循环。它看起来像这样：

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 循环相同，只是定义时间更长，使用更多内存。

相反，您应该尝试实现快速排序。它需要递归，并且在大多数情况下比冒泡排序快得多。大多数平台已经实现了它，因此您不必自己编写它，但了解它是如何工作的很有好处，并且有助于理解递归。

如果你愿意，你也可以尝试使用递归来解决这个问题：
你有一个 NxM 的数字表和一个起始坐标（位置）。这是^旅行者^的立场。旅行者可以前往相邻的单元格（右、左、上或下），该单元格的编号小于他所在的单元格的编号。您必须编写一个程序来计算旅行者在这些约束下可以通过的最长路径。使用随机生成数组，或手动生成。