Chapter 10. 재귀를 사용한 재귀적 반복

Chapter 10. 재귀를 사용한 재귀적 반복

하단의 목차를 클릭하여 이동할 수 있습니다 :)

1. 루프 대신 재귀
2. 컴퓨터의 눈으로 바라본 재귀

1. 루프 대신 재귀

• 재귀(recursion)는 함수가 자기 자신을 호출하는 것을 뜻한다.
• Loop를 사용할 수 있는 코드라면 거의 대부분 재귀 또한 사용할 수 있다. 물론 주어진 문제에 따라 loop와 재귀 둘 중 무엇을 사용할 것인지 선택한다.
• 교재 예제 코드 python 변환

# for loop을 사용한 코드
def countdown(number):
    for i in range(number, -1, -1):
        print(i)

countdown(10)

# 재귀를 사용한 코드
def countdown(number):
    print(number)
    if number > 0:
        countdown(number - 1)

countdown(10)

• 재귀문은 특정 조건이 없다면 무한히 반복되는 문제가 있다. 이때 재귀문이 반복되지 않도록 하는 조건을 기저 조건(base case)이라 한다. 따라서 모든 재귀 함수는 적어도 하나의 기저 조건을 갖는다.

---

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

• 재귀는 함수가 완료되기 전 다시 자기자신을 호출한다. 즉 완료 전에 함수가 호출되기에 진행 중인 함수는 따로 기록을 해 두어야 한다. 컴퓨터는 이런 재귀를 처리하기 위해 호출 스택(call stack)을 사용한다.
  • step 1 : 재귀를 통해 함수가 호출되면 수행 중이던 함수를 호출 스택에 푸시한다.
  • step 2 : 재귀가 발생할 때마다 계속하여 호출 스택에 반복하여 푸시한다.
  • step 3 : 기저 조건으로 인하여 재귀가 종료되는 시점을 만나면 재귀를 그만 두고 현제 수행 중인 함수를 완료한다. 그리고 호출 스택에서 해당 함수를 팝한다.
  • step 4 : 이제는 반대로 호출 스택의 위부터 하나씩 함수를 완료하고 완료된 함수들을 호출 스택의 밑까지 팝한다.
  • step 5 : 호출 스택의 모든 함수가 완료되었다면 함수 수행이 완료된 것이다.
• 위와 같은 방식은 '호출 스택을 통해 값 위로 전달하기 (passing a value up through the call stack)'이라고도 한다.
  • 다시 말하면 재귀 함수는 계산된 값을 "부모"함수에 반환하는 것을 반복하며 최초로 호출된 함수의 최종 값을 계산한다.
• 기저 조건이 없는 경우 재귀 함수는 무한히 반복된다. 즉 호출 스택에 무한히 함수가 푸시된다. 결국 단기 메모리가 호출 스택을 저장할 공간이 없어질 때까지 재귀가 반복된다면 컴퓨터는 스택 오버플로(stack overflow)라는 오류를 반환한다.
  • 다시 말하면 메모리가 가득 찼으니 더이상의 함수 호출을 거부한다는 의미이다.
• 재귀는 알고리즘이 임의의 단계 만큼 깊이 들어가야 하는 경우 사용하기 좋다.