[Hello Coding 알고리즘] 3장. 재귀

3장. 재귀

시작하기에 앞서

• 예제 코드 직접 실행해 보기
• 적어도 한 번은 연필과 종이를 가지고 재귀함수의 실행 과정을 따라가 보기.
• 의사코드(pseudocode, 슈도코드) : 문제와 풀이 방법을 간단한 코드로 설명한 것. 실제로 동작하진 않음

재귀 recursion

• 재귀
  • 함수가 자기 자신을 호출하는 것.

문제 : 여러 겹으로 포장된 상자들이 있고, 그 상자가 또 다른 상자들 속에 들어 있다. 몇 개일지 모르는 상자들 중 열쇠가 들어있는 상자를 찾아야 한다.

방법 1 : 반복문 사용하기

1. 내부를 확인할 상자를 쌓아놓는다(=상자 더미).
2. 상자 하나를 집어서 내부를 확인한다.
   1. 만약 안에 상자가 있다면, 확인할 상자 더미에 놓은 뒤 2로 돌아간다.
   2. 만약 안에 열쇠가 있다면 작업을 종료한다.

아래는 위 과정에 대한 슈도코드.

def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                print "열쇠를 찾았어요!"

방법 2 : 재귀 사용하기

1. 상자 안을 확인한다.
   1. 만약 상자를 발견하면 1.로 간다.
   2. 만약 열쇠를 발견하면 작업을 종료한다.

아래는 위 과정에 대한 슈도코드.

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)
        elif item.is_a_key():
            print "열쇠를 찾았어요!"

재귀의 특징

• 알고리즘 풀이를 명확하게 해 준다.
  • 성능이 더 나아지는 것은 아님. 성능은 반복문이 더 좋다.
• "프로그램에 반복문을 사용하면 프로그램의 성능을 향상시킬 수 있지만, 재귀를 사용하면 프로그래머의 능력을 향상시킬 수 있습니다. 상황에 따라 적절한 방법을 골라 사용하세요."
• 대부분의 중요한 알고리즘들이 재귀를 사용한다.

기본 단계와 재귀 단계

재귀함수는 자기 자신을 호출하기 때문에 무한루프에 빠지기 쉽다.

재귀함수를 만들 때에는 언제 재귀를 멈출지 반드시 알려 주어야 한다.

그래서 모든 재귀함수는 기본 단계와 재귀 단계로 나누어져 있다.

• 기본 단계 base case : 재귀를 빠져나가는 단계. 무한반복에 빠지는 것을 막는 부분이다.
• 재귀 단계 recursive case : 함수가 자기 자신을 호출하는 단계.

아래는 카운트다운을 하는 코드. (무한루프)

def countdown(i):
    print i
    countdown(i-1)

무한루프 코드에 기본 단계를 추가하면 정상 동작하는 재귀함수를 만들 수 있다.

def countdown(i):
    print i
    if i <= 1: ## 기본 단계
        return
    else: ## 재귀 단계
        countdown(i-1)

스택 (콜 스택)

호출 스택은 프로그램의 중요 개념이다. 재귀를 사용할 때는 더 중요하다.

스택 stack : 푸시(push, 삽입)와 팝(pop, 빼내서 읽기) 두 동작만 가능한 자료구조.

• 푸시 : 가장 위에 새 항목을 추가
• 팝 : 가장 위의 항목을 빼내어 읽기

콜 스택 (call stack, 호출 스택)

컴퓨터가 함수에 사용되는 변수를 저장하는 스택을 콜 스택이라고 한다.

함수가 한 번 호출될 때 마다, 컴퓨터는 그 함수 호출에 필요한 메모리를 할당해 스택으로 쌓는다(push).

• 함수에 사용된 변수도 해당 함수의 스택 내에 저장된다.
• 해당 함수가 종료(리턴)되기 전까지 그 스택은 유지된다.
  • 해당 함수가 종료(리턴)되면 그 스택은 사라진다(pop).
• 함수(A) 내에서 다른 함수(B)를 호출하면, A 스택 위에 B 스택이 쌓인다.
  • 함수 호출 후 종료되기 전이라도 다른 함수를 호출할 수 있으며, 이 때 중지된 함수의 변수 값들은 해당 스택으로 메모리에 저장된다.
  • 맨 위에 쌓여 있는 스택이 현재 실행되고 있는 함수에 대한 스택이다.

재귀 함수에서 콜 스택 사용

재귀 함수도 콜 스택을 사용한다.

아래는 팩토리얼 함수에 대한 재귀함수.

• 콜스택 모양은 꼭 교재를 확인하자 : 59~61페이지.

def fact(x):
    if x == 1:
        return 1
    else:
        return x * fact(x-1)

재귀 함수에서 콜 스택의 역할은?

= 반복문에서 필요했던 상자 더미(pile)의 역할.

재귀를 사용해 구현하면, 확인해야 할 상자 더미를 스택에 저장하는 것과 같다.

• 우리가 직접 상자 더미를 만들고 추적하지 않아도 되기 때문에 편리한 것!

콜 스택의 단점

: 모든 정보를 컴퓨터 메모리에 저장해야 하므로 메모리를 많이 소비한다.

• 함수 호출을 한 번 할 때마다 메모리를 사용하게 됨.
• 재귀가 깊어져 스택이 커지면, 컴퓨터가 과다한 함수 호출정보를 저장하게 됨
• 재귀가 깊어지면(특히 무한루프에 빠지면) 스택이 계속 커지는데, 모든 프로그램은 콜스택에 할당할 수 있는 메모리 공간이 정해져 있으므로 그 공간을 다 사용하면 스택 오버플로우 오류가 발생하며 프로그램이 종료된다.

해결 1 : 재귀 대신 반복문으로 전환

해결 2 : 꼬리재귀 tail recursion 방법을 사용 - 고급 재귀 방법.