재귀 함수
자기 자신을 호출하는 함수
하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법
python에서의 기본 재귀 구조는 아래와 같다.
실행결과는 어떻게 될까?
자기자신을 계속 호출하므로, 무한반복에 빠지며 지정된 재귀 깊이를 초과하여 에러가 발생한다.
그렇다면, 무한 루프에 빠지지 않게 하려면 어떻게 해야하는가?
당연하지만 그냥 나 자신을 계속 호출한다면 무한반복이 일어날 것이다. 이 무한한 반복을 우리가 원하는 만큼만 반복하고 중단시키는 것이 우리의 목표다.
우리가 기본적으로 아는 반복문에서와 마찬가지로 반복을 중단시킬 무언가가 필요하다. 즉, 반복을 중단시킬 조건과 그 조건을 체크하기 위한 값을 저장할 변수.
과정을 정리하면 아래와 같다.
- 매개변수를 하나 받음
- 재귀 호출이 일어날때마다 매개 변수의 값이 변하도록 설정해야 한다.
- 재귀 함수에서 매개변수의 값을 이용해 조건을 설정하고 일정조건을 만족하면 리턴하도록 설정
※ 매개변수 : 함수에 투입되는 변수
매개변수를 받고, 재귀 호출이 일어날 때마다 매개 변수의 값이 변하도록 설정해보자.
매개변수 k를 설정함.
함수를 호출할 때 5라는 인자를 주면 func(k)가 호출될 때 매개변수 k에 5라는 값이 담기게 됨.
함수안이 실행되며 다음 문장 func(k-1)이 실행되고, 재귀 호출이 일어남. 이때 다음 호출시 불릴 함수에 전달할 값을 k-1와 같이 변화시켜 준다. 그러면 다음 호출되는 함수 func의 매개변수 k에는 4 (5-1)이 담기게 된다.
이제 다시 한 번 실행해보자.
이유를 생각해보자.
우리가 원하는대로 매개변수의 값은 점점 작아지면서 호출되지만, 여전히 호출은 멈추지 않고 계속 된다.
이쯤하면 눈치를 차렸겠지만, 이쯤 하고 그만 호출해 라는 조건이 없기 때문에 열심히 계속 호출한다. 즉, 우리는 재귀 호출을 그만할 조건을 설정해야 한다.
위에서 본 것처럼 k는 점점 줄어들 것이다. 5에서 시작해서 매 호출이 일어날때마다 1씩 줄어든다. 그러다가 k가 0이되면 호출을 그만하고 이번 함수를 호출한 함수로 되돌아 가라고 설정해보자.
이제 실행해 보자.
무한 반복을 하지 않고, 적당한 횟수만을 반복하고 정상종료하였다.
함수의 호출을 따라 그려보며 생각해보자.
위에서 살펴본 것과 같이 func(5)에서 시작하며 k가 하나씩 줄며 계속 함수를 호출한다.
이때 매개변수 k의 값을 살펴보며 그 값이 0인지 아닌지를 판단한다. 0이 아니라면 if 문 내부는 무시되고 아래 문장이 실행된다. func(5)~func(1)까지 k가 0 이 아니므로 계속 호출을 진행하고 func(0)이 호출되면, if문을 만족하므로 if문 내부가 실행된다. return은 나를 호출한 곳으로 돌아가라 라는 의미이다. 그림에서 본 것과 같이 func(0)을 호출한 곳은 func(1)이다. 함수가 호출된 문장으로 돌아가고 다시 다음 문장을 실행하려고 하지만 함수의 마지막이므로 함수가 종료되고 함수 func(1)를 호출한 함수(func(2))로 돌아간다. 계속 리턴되다가, 처음 함수를 호출한 func(5) 문장까지 돌아가 main함수가 종료되며 프로그램이 정상종료하게 된다.
아주 간단한 내용이지만, 재귀를 어렵게 느끼는 사람들을 위해서 최대한 자세하게, 이해가능 하도록 설명하려고 노력해봤다!!
사실 재귀가 어려운 이유는 프로그램의 기본적 이론이 약하기 때문이라고 생각한다. 재귀를 이해하기 위해서는 함수, 매개변수, 호출, 조건문, 결과값 리턴 등등의 정확한 이해가 필요하다. 본인이 재귀가 어렵다면 방금 언급한 것들을 다시 공부해보는 것을 추천한다.