Recursion

• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
  • 하나의 큰 문제를 해결할 수 있는 (해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다.
  • 재귀함수로 구현
• 재귀함수 (recursive function)
  • 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수.
  • 일반적으호 재귀적 정의를 이용해서 재귀함수를 구현한다.
  • 따라서, 기본부분(basis part)와 유도파트(inductive part)로 구성된다.
    • 기본부분 = 기저조건 : 재귀의 끝
  • 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다.
    • 그러나, 재귀에 대해 익숙하지 않은 개발자들은 재귀적 프로그램이 어렵다고 느낀다.
  • 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다.
  • 따라서 재귀 호출은 반복적인 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생한다.

  ---

팩토리얼 재귀 함수

• 재귀적 정의
• Basis rule : N<=1 경우 , n = 1 Inductice rule : N > 1, n! = n * (n-1)!
• n!에 대한 재귀 함수
• int fact(int n) { //Basis part if(n<=1) return 1; //Inductive part else return n*fact(n-1); }

• 프로그램 메모리 구조

• main()에서 factorial(4), factorial(4)에서 factorial(3) ... factorial(2)에서 factorial(1)을 호출한다.
• 그 이후 return 1에서 factorial(1)을 호출하고 .... factorial(3)에서 fatorial(4)를 호출하며 최종적으로 24라는 값이 반환된다.

• package algorithm.recursive.basic;
  
  public class FactorialTest {
  
      //메소드 정의 : n! 계산
      private static int factorial(int n) {
          if(n<=1) return 1;
          return n*factorial(n-1);
      }
  
      //main
      public static void main(String[] args) {
          int N = 5;
          System.out.println(factorial(N));
      }
  }

  ---

피보나치

• 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라한다.
  ex) 0,1,1,2,3,5,8,13...
• 피보나치 수를 구하는 재귀함수
• fibo(n) if (n<=1) then return n; else return fibo(n-1) + fibo(n-2); end fibo(n)

Memoization

• 메모이제이션(memoization)은 컴퓨터 프로그램을 실행할때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

• //memo를 위한 배열을 할당하고, 모두 0으로 초기화한다
  //memo[0] 을 0으로 memo[1]는 1로 초기화한다.
  
  fibo(n)
      if n>=2 and memo[n] is zero then
          memo[n] <- fibo(n-1) + fibo(n-2);
      return memo[n];
  end fibo()