Recursion

구글링을 통해 이해했다고 생각했는데 막상 코딩테스트에 가면 구현이 어려우셨나요?

저뿐만 아니라 많은 초보자분들이 재귀 방법에서 손에 잡힐 듯 잡히지 않는 느낌을 받는다고 합니다.

그래서 저는 오늘 재귀를 확실히 이해해보려고 합니다.

필요성

반복문을 쓸까 재귀 함수를 쓸까?

재귀를 쓴다고 항상 성능이 좋아지는건 아닙니다. 오히려 재귀 함수 호출이 반복될 때마다 스택에 정보를 저장하게 되므로 많은 메모리를 사용하게 됩니다. 스택이 너무 커질 경우에는 반복문을 사용하는 것이 더 좋습니다.

하지만 중요한 알고리즘들 (예>퀵 정렬 )에 재귀가 사용되므로 확실한 개념 이해가 필요합니다.

예를 들어 생각하는대로 손코딩을 하다보면 어느새 같은 기능을 반복해서 적는 구간이 생깁니다.
저는 이럴때마다 recursion(재귀)을 떠올리면서 def recursion을 정의하고 코드를 간결하게 만들려고 합니다.
하지만 재귀 방법 구현 경험이 없다보니 error가 생기면서 당황할 일이 많더라구요.

이번 기회에 완벽히 이해해서 앞으로 복잡한 데이터 분석 코드를 작성할 때도 재귀를 에러없이 한 번에 적용할 수 있도록 해보겠습니다.

정의

Recursion 함수는 결과를 return하기 전에 자기 자신을 호출하는 방법입니다.

구현

재귀 함수를 작성할 때는

1.무한 반복을 멈추기 위한 기본 단계와

2.재귀 단계를 넣어주면 됩니다.

예시

한 list에 있는 원소들을 모두 더하는 함수를 재귀 함수로 작성해봅니다.

def sum(list):
    if len(list) == 1: #기본 단계
        return list[0]       #가장 간단한 array는 더할 원소가 없는 array = []이며, 이때 합은 0입니다.
    else:						 #재귀 단계
        return list[0] + sum(list[1:])

print(sum([2,4,6]))  

호출 순서 이해하기

컴퓨터는 재귀 함수를 어떤 방식으로 처리하는 걸까요?

이 질문에 답하기 위해서는 data structure(자료 구조) 중 linear structure(선형 구조)에 속하는 stack (스택)에 대한 이해가 필요합니다.

예시의 재귀 함수가 돌아가면 컴퓨터는 함수를 호출할 때마다 호출에 사용된 변수의 값을 메모리에 저장합니다. 이때 새로운 함수에 의한 메모리는 이전에 호출한 함수의 변수가 저장된 메모리 위에 저장되는 호출 스택이 만들어집니다.

호출 스택은 한 방향, 즉 위쪽 방향으로 push(삽입)되고 실행할 때는 가장 위에 있는 것부터 제거(pop) 합니다.

우리가 예제에 있는 재귀함수인 sum([2,4,6])를 호출하면 컴퓨터는 다음과 같은 호출 스택을 만듭니다.

아래에 쌓인 함수 호출들은 기본 단계를 만나기 전까지 완료되지 않고 호출 상태가 저장된 상태로 멈추게 됩니다.

가장 위에 있는 호출이 먼저 처리되며 sum([6])이 실행되고 6을 반환합니다.

그 결과 3 번째 호출은 4 + 6이 반환합니다.

	호출 스택이 쌓여있는 모습
3 번째 호출	4+sum([6])
2 번째 호출	2+sum([4,6])
1 번째 호출	sum([2,4,6])

값을 반환한 3 번째 호출은 제거(pop)되며, 남은 호출 스택의 모습은 다음과 같게 됩니다.

	호출 스택이 쌓여있는 모습
2 번째 호출	2+sum([4,6])
1 번째 호출	sum([2,4,6])

다음으로는 3 번째 호출이 반환한 4 + 6이 2번째 호출에 대입되고, 2 번째 호출은 2+(4+6)를 반환합니다.

마찬가지로 1 번째 호출은 1+ (2+(4+6))를 반환하여 최종 답인 12가 구해집니다.