누구나 자료구조와 알고리즘 - (9) 재귀

 

 

 

재귀 함수

올바르게만 사용하면 재귀는 강력한 도구가 될 수 있다.

 

사용 예시 1.

카운트다운 함수를 for문으로 작성할 수도 있겠지만 재귀를 사용할 수도 있다.

// for문으로 작성
function countdown(number) {
    for (let i=number i>=0; i--) {
        console.log(i);
    }
}

// 재귀로 작성
function countdown(number) {
    console.log(i);
    if (number === 0) {
        return;
    } else {
        countdown(number - 1);
    }
}

 

사용 예시 2.

모든 하위 디렉토리까지 반환하는 함수의 경우 하위 디렉토리의 단계를 알 수 없다.

이 때 재귀를 사용하여 원하는 만큼 아래로 가 하위 디렉토리를 알 수 있다.

 

재귀 함수를 여러번 호출하는 경우 첫번째 호출이 채 다 끝나기도 전에 두번째 호출이 이뤄질 수도 있다. 컴퓨터는 이러한 호출을 스택을 사용하여 어떤 함수를 호출중인지 기록한다. 따라서 첫번째 호출의 결과를 토대로 두번째 호출이 완료될 수 있다. 재귀함수는 계산된 값을 "부모" 함수에 반환한다.

 

 

 

 

 

재귀적으로 작성하기

 

1.1. 재귀 카테고리 - 반복 실행

반복적으로 한 작업을 실행하는 알고리즘이다.

// 배열의 각 수를 2배로 만든다.
function doubleArray(array, index = 0) {
    if (index >= array.length()) {
        return;
    }
    
    array[index] *= 2
    doubleArray(array, index + 1)
}

 

 

 

1.2. 재귀 카테고리 - 계산

재귀가 유용하게 쓰이는 영역 2가지는 아래와 같다.

• 임의의 단계만큼 깊이 들어가는 문제 풀 때
• 하위 문제의 계산 결과에 기반해 계산할 수 있을 때

function factorial(n) {
    product = 1
    
    for (let i=1; i >= n; i++) {
    	product *= i
    }
    
    return product
}

 

예를 들어 팩토리얼을 만들 때 factorial(6)은 factorial(5)의 결과에 6을 곱한 것이다.

다르게 표현하면 factorial(6) = 6 x factorial(5)이다.

factorial(5)는 더 큰 문제의 결과를 계산하는 데 쓰이는 더 작은 문제이므로 factorial(6)의 하위 문제라 부른다.

 

코드로 구현하면 아래와 같다.

function factorial(number) {
    if (number === 1) {
        return;
    } else {
    	return number * factorial(number - 1)
    }
}

 

 

 

 

 

하향식 재귀

 

1.1. 하향식 재귀

재귀 전략에는 상향식, 하향식이 있다. 상향식으로 답을 찾아 가거나, 문제의 하위 문제에 기반해 계산함으로서 하향식으로 문제를 해결해나갈 수 있다. 상향식에서는 루프를 쓰는 재귀를 쓰든 같은 전략으로 계산한다. 하지만 하향식에서는 재귀를 써야 한다. 하향식 전략을 구현할 방법은 재귀뿐이며 이것이 재귀가 강력한 도구로 자리매김한 주된 이유 중 하나다.

 

 

1.2. 하향식 사고 절차

하향식 재귀에 경험이 부족하면 시간을 갖고 하향식으로 생각하는 법을 연습하자.

• 작성 중인 함수를 이미 누군가 구현해 놓았다고 상상하자.
• 문제의 하위 문제를 찾자.
• 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.

 

sum 함수가 이미 구현되어있다고 가정한다.

만약 [1, 2, 3, 4, 5]를 배열로 전달했을 때 sum([2, 3, 4, 5])에 1을 더하면 된다.

function sum(array) {
    // 기저 조건: 배열에 원소가 하나만 남았을 때
    if (array.length === 1) {
    	return array[0]
    }
    
    return array[0] + sum(array[1, array.length - 1])
}

 

 

 

 

 

재귀함수와 동적 프로그래밍

 

재귀 함수를 작성하다보면 O(2²) 알고리즘의 함정에 빠질 수 있다. 불필요한 재귀 호출은 효율성을 떨어뜨린다.

• 방법 1. 필요한 함수 호출을 한 번만 수행하고 그 결과를 변수에 저장함으로써 함수를 다시 호출하지 않아도 되게 해야 한다.
• 방법 2. 메모이제이션을 통한 동적 프로그래밍을 수행한다.

 

1.1. 동적 프로그래밍

동적 프로그래밍이란 하위 문제가 중첩되는 재귀 문제를 최적화하는 방법이다. (동적이라는 말에는 의미가 없다고 한다.) 

 

동적 프로그래밍 방법 1: 메모이제이션(memoizaion)

하위 문제가 중첩될 때 재귀 호출을 감소시키는 방법으로 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다. 새로 계산한 결과를 모두 메모이징하여 해시테이블에 저장하고 이미 저장된 결과값이 있다면 호출하지 않는다.

 

가령 피보나치 수열의 n번째 수를 반환하는 fib(n)라는 재귀함수가 있을 때 fib(4)를 호출하면 하위 문제인 fib(3), fib(2)를 호출하게 된다. (함수가 자기 자신을 2번 호출하는 경우 머릿속에 경고음이 울려야한다.) 하지만 메모이제이션을 사용하면 fib(4)는 fib(3)을 호출하는 대신 해시테이블을 뒤져 결과가 미리 계산되었는지 확인 후 결과가 없을 때에만 호출한다.

 

function fib(n, memo) {
    if (n === 0 || n === 1) {
        return n;
    }
    
    // memo 해시 테이블에서 fib(n)이 이미 계산되어 있는지 확인한다.
    if (memo.get(n)) {
            
        // n이 memo에 없으면 재귀로 fib(n)을 계산한 후 결과를 해시테이블에 저장한다.
        memo[n] = fib(n - 2, memo) - fib(n - 1, memo)
    }
}

 

 

동적 프로그래밍 방법 2: 상향식으로 풀기

재귀가 아닌 상향식 접근법(루프)으로 접근하는 방식이다.

어떤 방식을 선택해야 할까? 재귀가 주어진 문제를 푸는 간결하고 직관적인 해법이라면 재귀로 풀면서 메모이제이션으로 하위 문제 중첩을 처리하고 싶을 수 있다. 하지만 반복적 방식도 충분히 직관적이면 반복으로 해결하고 싶을 수도 있다.

 

재귀가 매우 직관적이지 않은 이상 일반적으로 상향식을 택하는게 낫다. 재귀가 더 직관적이라면 재귀를 사용하되 메모이제이션으로 빠르게 만들어야 한다.

 

 

 

 

---

출처

제이 웹그로우, 누구나 자료구조와 알고리즘 (길벗, 2021)

 

 

 

 

---

개인적으로 공부한 내용을 정리하는 블로그로
잘못된 개념을 게시하지않도록 주의하고 있으나 오류가 있을 수 있습니다.