[책] 누구나 자료구조와 알고리즘 - 10장 재귀를 사용한 재귀적 반복

https://product.kyobobook.co.kr/detail/S000001834743

누구나 자료 구조와 알고리즘 | 제이 웬그로우 - 교보문고

 

재귀(recursion)는 이후에 나올 보다 고급 알고리즘을 이해하기 위한 컴퓨터 과학의 핵심 개념이다.

재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어다.

잘못 사용하게 되면 무한재귀가 되어 전혀 쓸모없게 되지만, 올바르게만 활용하면 재귀는 강력한 도구가 될 수 있다.

 

루프 대신 재귀

루프 대신 재귀를 사용할 수 있다.

기저 조건

재귀가 영원히 지속되는 것을 막을 방법이 있어야 완벽한 방법이 된다.

재귀에 쓰이는 용어로 함수가 반복되지 않는 경우를 기저 조건(base case)이라 부른다.

모든 재귀 함수에는 무한대로 호출되지 않게 하는 기저 조건이 적어도 하나 있어야 한다.

재귀 코드 읽기 (작성하기)

계승(factorial)을 계산하는 예제를 살펴보자.

이미지 출처: https://steemit.com/kr/@hunhani/6f3yi1-chapter-5

# 루비로 작성된 코드
def factorial(number)
	if number == 1 # 기저 조건
    	return 1
    else
    	return number * factorial(number-1)
    end
end

재귀를 읽는 방법

1. 기저 조건을 찾는다
2. 기저 조건에서 함수가 어떻게 동작하는지 살핀다.
3. "끝에서 두 번째" 조건을 찾는다. -  기저 조건 바로 전 조건
4. "끝에서 두 번째" 조건에서 함수가 어떻게 동작하는지 살핀다.
5. 방금 분석한 조건의 바로 전 조건을 찾아가며 위 절차를 반복하고 그 때마다 함수가 어떻게 동작하는지 살핀다.

factorial(1) 호출 시 단순히 1이 반환된다.

이처럼 기저 조건부터 분석을 시작해서 나아가는 것은 재귀 코드를 추론하는 훌륭한 방법이다.

 

컴퓨터의 눈으로 바라본 재귀

위 예제를 다시 이용하여, 컴퓨터는 factorial(3)를 다 실행하지 않았는데 factorial(2)를 실행하게 된다.

factorial(3)을 다 수행하지 않았다는 사실을 어디에 어떻게 기록하게 되는걸까?

호출 스택

컴퓨터는 스택을 활용해 어떤 함수를 호출 중인지 기록한다.

이 스택을 목적에 딱 맞게 호출 스택(call stack)이라 부른다.

가장 최근에 호출 된 함수를 제거한다.

push 작업

1. factorial(3) 을 실행하게 되면 호출 스택에 factorial(3)를 넣는다.
2. factorial(3) 수행 중에 factorial(2)가 실행되게 되어 factorial(2)를 호출 스택에 넣는다.
3. factorial(2) 수행 중에 factorial(1)가 실행되게 되어 factorial(1)를 호출 스택에 넣는다.

pop 작업

1. factorial(1)가 수행 완료되어 호출 스택에서 제거 된다.
2. factorial(2)가 수행 완료 되어 호출 스택에서 제거 된다.
3. factorial(3)가 수행 완료 되어 호출 스택에서 제거 된다.

이러한 방법을 호출 스택을 통해 값 위로 전달하기(passing a value up through the call stack) 라고 부르기도 한다.

각 재귀 함수는 계산된 값을 "부모" 함수에 반환한다.

최초로 호출 된 함수가 최종 값을 계산한다.

 

무한 재귀는 단기 메모리에 더 이상 데이터를 저장할 공간이 없을 때까지 호출 스택은 점점 늘어난다.

결국 스택 오버플로(stack overflow)라는 오류가 발생하게 되고, 컴퓨터는 재귀를 강제로 중단하고 오류를 반환하게 된다.

 

재귀는 몇 단계나 깊이 들어가야 하는지 모르는 상황에서 문제를 여러 단계로 파고 들어야 할 때의 문제 유형과 자연스럽게 들어맞는다.

ex) 파일 시스템 순회

예시 상황) 어떤 디렉터리 내에 있는 모든 파일에 대해 모든 하위 디렉터리명을 출력하는 작업을 하는 스크립트 실행

-> 하위 디렉터리의 하위 디렉터리의 하위 디렉터리의..... 까지 모두 출력.

-> 몇단계까지 내려가야하는지 모른다.

# 루비로 작성된 코드
def find_directories(directory)
	# 현재 경로에 있는 모든 파일 혹은 디렉터리를 탐색한다.
	Dir.foreach(directory) do |filename|
    	# 현재 파일이 하위 디렉터리면 (기저 조건)
    	if File.directory?("#{directory}/#{filename}") &&
        filename != "." && filename != ".."  # "." 현재 디렉터리, ".." 이전 디렉터리
        	# 전체 경로명을 출력한다.
        	puts "#{directory}/#{filename}"
            
            # 하위 디렉터리에 대해 함수를 재귀적으로 호출한다.
            find_directories("#{directory}/#{filename}")
        end
    end
end

 

관련된 절차는 18.5절 깊이 우선 탐색에서 다시 한번 시작적으로 자세히 설명 할 예정이다.

 

마무리

알고리즘이 임의의 단계 만큼 깊이 들어가야 한다면 재귀가 좋은 방법일 수 있다.

11장에서는 재귀적으로 작성하는 법을 보다 쉽게 익히는 기법을 알아 볼 예정이다.

그 과정에서 재귀가 매우 유용한 도구로 쓰이는 주요 유스케이스도 살펴본다.