재귀 호출

생성 일시: 2023년 8월 17일 오전 9:00

재귀 호출

재귀 호출이란?

  • 再歸
  • 자기 자신을 호출하여 순환 수행되는 것
  • 함수 호출은 메모리 구조에서 스택을 사용한다. (이름만 같은 다른 메서드)
    • 간단한 문제에 대해서는 반복문에 비해 메모리 및 속도에서 성능 저하가 발생한다
  • 일반적으로 기본 부분 (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

Untitled

  • 앞의 예에서 피보나치 수를 구하는 알고리즘에서 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];
}

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