재귀 호출, Memoization

재귀 호출

---

재귀 호출이란?

• 再歸
• 자기 자신을 호출하여 순환 수행되는 것
• 함수 호출은 메모리 구조에서 스택을 사용한다. (이름만 같은 다른 메서드)
  • 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능 저하가 발생한다
• 일반적으로 기본 부분 (Base case), 재귀 부분 (Recursive case)로 구성된다
  • Base case: 재귀 호출에서 빠져나가기 위한 조건 (탈출 조건)
  • Recursive case: 자신을 호출하는 부분 (Base case로 유도하는 방향으로 작성한다)
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다
• 하고자 하는 연산에서 여러 가지 분기가 있을 때 적용하기 좋다.

재귀 호출 작성

재귀 호출의 예) 팩토리얼 계산

• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성
  • 재귀 호출의 예) factorial
    • n에 대한 factorial: 1부터 n까지의 모든 자연수를 곱하여 구하는 연산
    • n! = n * (n-1) ! (n-1)! = (n-1) * (n-2)! (n-2)! = (n-2) * (n-3)! ... 2! = 2 * 1! 1! = 1
    • 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 작업을 반복

재귀 호출의 예) 피보나치 수열

• 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라 한다
  • 0, 1, 1, 2, 3, 5, 8, 13, …
• 피보나치 수열의 i번째 값을 계산하는 함수 F를 정의하면 다음과 같다
  • F0 = 0, F1 =1
  • Fi = Fi-1 + Fi-2 for i≥2
• 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀 함수로 구현할 수 있다
• 피보나치 수를 구하는 재귀 함수
• public static int fibo(int n) { if (n<=1) { return 1; } else { return fibo(n-1) + fibo(n-1); } }

Memoization

• 앞의 예에서 피보나치 수를 구하는 함수를 재귀 함수로 구현한 알고리즘은 문제점이 있다
• → 엄청난 중복 호출이 존재한다

피보나치 수열의 Call Tree

• 앞의 예에서 피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하자마자 저장하면 (memoize), 실행시간을 Θ(n)으로 줄일 수 있다.
• Memoization 방법을 적용한 알고리즘은 다음과 같다.
• memo를 위한 배열을 할당하고, 모두 0으로 초기화 한다; memo[0]을 0으로 memo[1]는 1로 초기화한다; public static int mFibo(int n) { if (n>=2 && memo[n] == 0) { memo[n] = mFibo(n-1) + mFibo(n-2); } return memo[n]; }

 

이전 국비 교육을 수강하면서 프론트엔드 파트로 프로젝트를 할 때에도 메모이제이션을 많이 사용했다. 막연히 연산을 줄이는 수단이라고만 생각했는데, 기본적인 부분에서 메모이제이션을 다시 만나니 반갑기도 했고 이해가 쉬웠다.