💻 CSC1003 LEC13-15 递归

递归(Recursion)

递归的结构

  • 递归是一种在定义时引用自身的技术。

  • 基准条件：递归必须有一个终止条件，当问题缩小到一定程度时，直接给出结果。

  • 递归条件：问题被分解为一个或多个更小的子问题，然后递归地解决这些子问题。

示例：整数转换为二进制

public class Binary 
{ 
   public static String convert(int N)
   { 
      if (N == 1) return "1";   // (Base Case)基准条件
      return convert(N/2) + (N % 2);   // 方法中调用自己
   } 
   public static void main(String[] args) 
   { 
      int N = Integer.parseInt(args[0]); 
      System.out.println(convert(N)); 
   } 
}

  • 我们来详细的解释 convert() 递归部分：

    1. 假设命令行输入“42”，它先在 main 方法中转为整型数据，然后 main 方法调用 convert 方法，42被输入。
    2. 42 ≠ 1，所以方法返回值为 “convert(21) + 0”。因为 convert() 方法的返回值是 String 类型的，所以这不是加法而是字符的拼接。
    3. 接着 convert(21) 再次调用自己，返回值变为 “convert(10) + 1 + 0"。以此类推，直到第五次递归时达到基准条件(即输入值为 1)，因为 return 在没有递归时会立即结束一个方法，最终会输出”101010“。

  • 时间轴(括号代表还在递归内)：

(42)→(21)+0
	  ↓
	 (10)+1+0
	  ↓
	 (5)+0+1+0
	  ↓
	 (2)+1+0+1+0
	  ↓
	 (1)+0+1+0+1+0 → 101010

栈溢出(Stack Overflow)

  • 以下是两个可能无线递归并导致栈溢出的递归：
public static double bad(int N) 
{ 
   if (N == 1) return 1.0; 
   return bad(1 + N/2) + 1.0/N; 
}

public static double worse(int N) 
{ 
   return worse(N-1) + 1.0/N; 
}
  • 问题：bad() 中，1 + N/2 的增长太慢，可能导致无限递归。worse() 中，没有基准条件，导致无限递归。
  • 解决方案：递归程序必须有明确的基准条件，确保递归能够在有限且合理次数的步骤内结束。

栈(Stack)与堆(Heap)

特性 栈(Stack) 堆(Heap)
管理方式 全部由操作系统自动管理(用于局部变量和方法调用栈帧) 由程序员手动分配，垃圾回收器自动回收
空间大小 通常较小(几MB) 通常较大（可达到数GB）
分配与释放速度 快速，LIFO(后进先出) 相对较慢，依赖垃圾回收(GC)
使用对象 局部变量、方法调用信息(栈帧)、递归调用 对象实例、数组等
主要风险 递归过深可能导致栈溢出（StackOverflowError） 内存泄漏(如果垃圾回收器无法释放无用对象)
数据访问 直接访问，速度快 通过引用间接访问，速度较慢

指数级浪费

递归的一个常见问题是指数级的浪费，特别是在涉及到重复计算时。Fibonacci 序列是一个典型的例子。

public class FibonacciStack {
   public static long F(int n) {
      if (n == 0) return 0; 
      if (n == 1) return 1; 
      return F(n-1) + F(n-2); 
   }
   public static void main(String[] args) {
      int n = Integer.parseInt(args[0]);
      System.out.println(F(n));
   }
}

  • 在如上的斐波那契递归中，递归树的每一层大约会有两倍于上一层的递归调用，因此时间复杂度大约是 O(2^n)。这意味着输入 n 增加时，计算所需的时间将会呈现指数级增长，导致计算非常慢。比如：

  • 计算 fibonacci(5) 需要大约 15 次调用。 计算 fibonacci(10) 需要大约 177 次调用。 计算 fibonacci(50) 可能需要数十亿次调用，时间会非常长。

  • 更大的数可能直接导致栈溢出。

  • 解决方案：使用动态规划（Dynamic Programming）或者记忆化（Memoization）来避免重复计算。

public class FibonacciHeap {
   static long[] memo = new long[100]; 
   public static long F(int n) {
      if (n == 0) return 0; 
      if (n == 1) return 1; 
      if (memo[n] == 0) 
         memo[n] = F(n-1) + F(n-2); 
      return memo[n]; 
   }
   public static void main(String[] args) {
      int n = Integer.parseInt(args[0]); 
      System.out.println(F(n)); 
   }
}
  • 该算法会将每个计算过的 Fibonacci 数存储在 memo 数组中，因为数组存储在堆中，不会发生溢出。同时避免每次调用方法需要重复计算。
comments powered by Disqus