재귀함수(Recursive function)

재귀함수: 함수 내부에서 자신의 함수를 반복적으로 호출하는 함수

 

재귀함수는 반복적으로 호출하기에 반드시 함수 내에는 반복을 탈출(exit)은 조건이 필수이며, 반복적으로 변수를 조금씩 변경하여 연산을 수행하는 알고리즘에서 이용됩니다. 

 

카운트

1에서 n까지 정수를 카운트(count)하는 과정을 살펴보면 변수의 값을 반복적으로 1씩 증가하고 이를 출력합니다.

 

실습 숫자 카운트 예시

# (1) 재귀함수 정의 : 1~n 카운트
def Counter(n) :
	if n == 0 :
    	return 0	# 종료 조건
    else :
    	Counter(n-1)	# 재귀호출

# (2) 함수 호출
print('n=0 : ', Counter(0))

n=0 :  0

# (1) 재귀함수 정의

매개변수 n을 갖는 Counter() 함수는 종료조건 'n==0'을 포함하고 있습니다. 실인수 0으로 함수를 호출하면 재귀호출 없이 곧바로 종료 조건에 의해서 함수는 종료되며 실인수가 1 이상이면 재귀호출이 발생합니다.

 

# (2) 함수 호출

실인수 0으로 재귀함수를 호출하면 종료 조건에 의해서 0이 반환되고 출력됩니다.

 

누적합

카운트한 값을 누적하여 반환하는 경우에도 재귀함수를 적용하여 문제를 해결할 수 있습니다.

 

실습 1~n 정수 누적합 예시

# (1) 재귀함수 정의: 1~n 누적합(1+2+3+4+5=15)
def Adder(n):
	if n == 1:	# 종료 조건
    	return 1
    else:
    	result = n + Adder(n-1)	# 재귀호출
        
        print(n, end = ' ')	# (4) 스택 영역	2 3 4 5
        return result

2 3 4 5

# (2) 함수 호출1
print('n=1:', Adder(1))

n=1: 1

# (3) 함수 호출2
print('\nn=5:', Adder(5))

n=5: 15

# (1) 재귀함수 정의

매개변수 n을 갖는 Adder() 함수는 종료조건 'n==1'을 포함하고 있습니다. 실인수 1로 함수를 호출하면 재귀호출없이 곧바로 종료 조건에 의해서 함수는 종료됩니다.

 

# (2) 함수 호출1

실인수 1로 재귀함수를 호출하면 종료 조건에 의해서 1이 반환되고, 출력됩니다.

 

# (3) 함수 호출 2

실인수 5로 재귀함수를 호출하는 과정을 단계로 알아봅니다.

 

단계 1: 실인수 5로 재귀함수를 호출하면 종료 조건이 거짓이므로 else 영역의 재귀호출이 발생합니다. 이때 최초로 넘어온 실인수 n=5는 스택(stack) 영역에 저장됩니다.

단계 2: 재귀호출은 (n-1) 수식에 의해서 Counter(4) 형식으로 자신의 함수를 호출합니다. 이때 n=4가 스택에 저장됩니다.

단계 3: 두 번째 재귀호출은 (n-1) 수식에 의해서 Counter(3) 형식으로 자신의 함수를 호출합니다. 이때 n=3이 스택에 저장됩니다.

단계 4: 세 번째 재귀호출은 (n-1) 수식에 의해서 Counter(2) 형식으로 자신의 함수를 호출합니다. 이때 n=2가 스택에 저장됩니다.

단계 5: 네 번째 재귀호출은 (n-1) 수식에 의해서 n=1이 되기에 종료 조건(n==1)이 참(True)이 됩니다. 재귀호출 과정에서 종료 조건이 참이면 return 1의 값이 재귀호출 부분으로 반환되고, 스택 영역의 값을 역순으로 꺼내서 (pop) 'result = n + Adder(n-1)' 문장으로 누적합이 계산됩니다.