第六讲-递归

递归需满足的三个条件：

• 划分：一个问题可分解成多个子问题

• 求解更小的问题：除了问题规模不同，每个子问题的求解方法是一样的

• 综合解：存在递归终止条件

如何写好递归？

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码

递归的优缺点

优点：代码的表达力很强，简洁明了

缺点：空间复杂度高、有堆栈溢出风险、存在重复计算、过多的函数调用会耗时较多等问题

递归代码如何调试？

1.打印日志发现，递归值。
2.结合条件断点进行调试。

Algorithm SelectionSort
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in non-decreasing order.

Solution: sort(1)
Procedure sort(i)   //Sort A[i..n]
if i<n then
      k=i
      for j=i+1 to n
             if A[j] < A[k] then k=j
      end for
      if ki then interchange A[i] and A[k]
      sort(i+1)
end if