• 정의

  • Recursive call : 메소드를 부르는 것이 새로운 call을 만드는 것
  • Direct recursion : method가 direct하게 자신을 부르는 Recursion
  • Indirect recursion : 두 개 이상의 메서드가 호출된 체인이 체인을 시작한 메서드로 되돌아오는 재귀

• Recursion

  • Recursion 사용은 조심해야 함
  • Recursive solution은 iterative solution보다 less efficient

• 피보나치 수열 (5p)

  • recursion : $O(2^n)$
  • iteration : $O(N)$

Recursion

• Recursion은 어떻게 정의되는가

  • Base case : 솔루션이 nonrecursive하게 정의되는 케이스

  • General (recursive) case

    • solution이 그것의 smaller version으로 나타나는 것

  • Recursive algorithm

    • smaller instances of itself
    • base case

    → 이 두개로 솔루션이 표현되는 것

  → infinite sequence of function calls를 만드는 것을 피해야 함

• Recursive Solution

  • 각각의 successive recursive call은 답이 알려진 상황에 더 가까이 다가갈 수 있게 해줌
  • base case : 답이 이미 알려진 (recursion 없이 표현될 수 있는) 케이스
  • 각각의 recursive algorithm은 적어도 하나의 base case를 가지고, general case도 가짐

• General format

  void recursiveFunction(parameters){
  	if (some conditions for which answer is known){
  			solution statement // base case
  	}
  	else {
  			recursiveFunction() // general case
  	}
  }
  

• Ex1. Factorial 함수 (recursive)

  • O(N)

  int recursiveFactorial(int number) {
      if (number == 0) {
          return 1; // base case
      }
      return number * recursiveFactorial(number - 1); //general case
  }
  

• Ex2. Combinations 함수 (recursive)

  • $O(2^n)$ → 각 레벨마다 재귀 호출 2번 발생

  int combinations(int n, int k) {
      // Base cases
      if (k == 1) {
          return n;
      }
      else if (k == n) {
          return 1;
      }
      // Recursive case
      else {
          return combinations(n - 1, k - 1) + combinations(n - 1, k);
      }
  }
  

• Recursive Function 검증

  1. Base case Question
     1. function 밖에 non - recursive한 것이 있는지
  2. Smaller-Caller Question
     1. 각각의 recursive function call이 base case로 향하는 original problem의 smaller case를 포함하고 있는가
  3. General-Case Question
     1. 각각의 recursive call이 올바르게 작동한다 가정할 때 전체 함수가 바르게 작동하는가

• Ex3. x to power of n

  • O(N)

  int power(int x, int n) {
      if (n == 0)
          return 1; // base case
      else
          return x * power(x, n - 1); // general case
  }
  

Recursion + ADT