[Section 4] 재귀에 대하여...

파이썬 목차 보기

[Intro] 파이썬 미리보기

0. INTRO

프로그램을 제작할 때, 재귀적 방법을 자주 사용하곤 한다. 따라서 재귀(recursion)는 프로그래밍의 자료구조 이해에 필수적인 개념이다. 이번에는 재귀 함수가 무엇인지 그리고 왜 필요한지에 대해 알아보도록 하자.

1. 재귀적 방법(Recursive method)의 장점

프로그래밍에서 함수를 정의하게 되면, 그 함수를 반복해서 사용해도 될까? 재귀 함수(recursive function)는 프로그램이 컴파일(complied) 될 때 루프(loop) 안에서 같은 함수를 반복하여 사용하며 명령을 수행(interpreted)한다. 이러한 프로그래밍 방법은 자료의 분류(sort), 검색(search) 등의 문제에 아주 유용하게 사용될 수 있다.

 

재귀적 방법의 또 다른 장점에 대해 언급해보자면 다음과 같다.

• 사용하기 쉽다.
• 같은 응용 분야에 활용하기 쉽다.

2.  재귀 함수에 필요한 용어 정리

재귀 함수에 대해 본격적으로 알아보기 전에, 미리 필요한 용어를 알아두고 넘어가자. 

A. 종료 조건(base case)

재귀 함수로 프로그램을 만들게 되면, 지정된 명령이 재귀 함수로 정의된 명령을 차례차례 반복해서 수행해나간다. 이때 재귀 함수의 프로세스(process)가 n번 진행하여 프로그램 동작이 멈추었다고 가정하자. 이 n번째 프로세스에서는 재귀 함수가 동작하지 않는 단계이다. 따라서 이를 종료 조건(base case)이라고 부른다. 

B. 백트래킹(Backtracking)

재귀의 한 형태로써 백트래킹은 복수의 선택 조건이 주어진 상황에서 적합한 프로그래밍 방식이다. 하나의 선택을 결정하는데 적합한 프로그래밍 방법으로 자세한 내용은 이후에 다루기로 하자. 

C. 반복(iteration)

반복문과 조건문을 사용하면, 재귀적 방법과 비슷한 프로그램을 만들 수 있다. 대표적으로 while 문을 이용하면, 조건에 맞는 데이터를 얻을 때까지 명령을 반복 수행할 수 있다.

3. 재귀(recursion)와 반복(iteration)의 차이

재귀와 반복은 비슷하면서도 다른 특성을 가지고 있다. 프로그램에서 반복과 재귀의 차이를 알아보자. 

먼저, 종료 시점이다. 재귀적 방법은 종료 조건에 도달하면 프로그램 동작이 종료된다. 반면에, 반복문으로 프로그램을 짜게 되면, 지정된 데이터가 거짓 조건에 해당해야 프로그램이 종료된다. 

 

무한 루프 안에서 데이터의 할당이라는 측면에서 차이가 있다. 반복은 프로그램상의 메모리 할당 영역이 존재하지 않을 때까지 무한 루프 안의 명령을 수행하는 반면에 재귀 함수는 메모리 구조상에 여분의 영역(스택 영역)이 필요하며, 여분의 영역을 넘어가면 스택 오버플로우(stack overflow)가 발생한다. 

 

* 메모리 구조에 대한 내용은 다음의 내용을 참고하자.

프로그래밍을 위한 메모리 구조