재귀함수(Recursion)

알고리즘/알고리즘 이론 정리

재귀함수(Recursion)

jxhxxn_ 2023. 4. 11. 10:47

동적 계획법(DP)와 비교해 함께 공부하면 좋다.

재귀함수의 정의

함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다.

재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 도출한다.

➕분할 정복(Divide and Conquer) 방식의 하나로 재귀함수를 활용한다.

문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘을 분할 정복 알고리즘이라고 한다.

재귀함수를 활용해 Top-Down(하향식 접근)해결 방식을 사용하는 특징이 있다.

재귀함수를 구현하는 두가지 방법

1. 재귀함수를 호출하는 부분을 상단에 두고 표현할 수 있다.

# if문에서 보이는 것과 같이 일정한 조건을 만족하지 않으면
# 계속해서 자기 자신의 함수로 되돌리는 코드를 볼 수 있디
def function(입력)
		if 입력 > 일정값: #입력이 일정 값 이상이면
				return function(입력 - 1) #괄호 안의 값을 이용해 함수를 재호출 한다.
																#입력보다 작은 값 #()안은 예시일 뿐 패턴은 여러가지이다.
		else: #종료조건
				return 일정값, 입력값, 또는 특정값 #재귀 호출 종료
																		#헤당 값을 리턴한다.

재귀함수로 표현하는 팩토리얼

def factorial(n):
		if n > 1: #n값이 1 보다 크면
				return n * factorial(n - 1) #n값을 곱하고 n-1 값으로 factorial을 재호출 한다.

		else: #n값이 1이라면
				return #리턴한다

#출력
for n in range(3)
		print(factorial(n))

#입력 n=3 이라고 한다면
#결과
# 0 
# 1 
# 2 
# 6

2. 재귀함수가 돌아가는 부분은 아래에 삽입해 표현 할 수 있다.

def function(입력):
		if 입력 <= 일정값: #입력이 일정 값 보다 작으면
				return 일정값, 입력값, 또는 특정값 #재귀 호출 종료 
																		 #해당 값을 리턴한다.
		function(입력보다 작은 값) #해당 값으로 재귀 재호출 한다.
		return 결과값

재귀함수로 표현하는 팩토리얼

def factorial(n) 
		if n > 1: #n값이 1보다 크다면
			return n * factorial(n-1) #n값에 n-1값으로 재호출한 factorial 값을 곱한다 

		return n 

#출력
for n in range(3)
		print(factorial(n))
#입력 n=3이라고 한다면
#결과
# 0
# 1
# 2
# 6

개인적으로 보기 편하다는 이유로 1번의 방식을 선호한다.

재귀함수 동작과정

다음과 같은 함수가 있다고 가정하자.

def recur(n): #시작
	if n == 0: #종료 조건
		return #끝
	recur(n-1) #종료 조건에 부합하지 않는다면 괄호 안의 값으로 다시 함수를 실행한다.

recur 함수는 n을 인자로 입력받는다.

def recur(3): #시작
	if n == 0: #종료 조건
		return #끝
	recur(n-1) #종료 조건에 부합하지 않는다면 괄호 안의 값으로 다시 함수를 실행한다.

함수가 실행되고, 3 이라는 수를 인자로 받았다. 종료 조건에 부합하지 않으므로 recur(n-1)을 호출해 다시 함수를 실행한다.

def recur(2): #시작
	if n == 0: #종료 조건
		return #끝
	recur(n-1) #종료 조건에 부합하지 않는다면 괄호 안의 값으로 다시 함수를 실행한다.

n의 값이 2로 다시 함수를 실행 했으나 2 또한 0이 아니므로 종료 조건에 부합하지 않는다. 따라서 위와 같이 recur(n-1)을 호출해 다시 함수를 실행한다.

def recur(1): #시작
	if n == 0: #종료 조건
		return #끝
	recur(n-1) #종료 조건에 부합하지 않는다면 괄호 안의 값으로 다시 함수를 실행한다.

n의 값이 1인 recure 함수를 실행 했으나 종료 조건에 부합하지 않아 한번 더 recur(n-1)을 호출해 다시 함수를 실행한다.

def recur(0): #시작
	if n == 0: #종료 조건
		return #끝
	recur(n-1) #종료 조건에 부합하지 않는다면 괄호 안의 값으로 다시 함수를 실행한다.

n==0으로 recur 함수 종료 조건에 부합했다. recur(0)은 return을 만난 즉시 종료되어 자신을 호출한 recur(1)로 돌아간다. recur(n-1) 아래로는 더 이상 실행 할 코드가 없기에 recur(1)은 그 즉시 종료된다.

recur(2)와 recur(3)또한 마찬가지이다.

이 처럼 재귀함수는 자기 자신을 호출해 실행하고 복제된 모든 함수가 종료될 때까지 끝나지 않는다.

리턴 이후?

예시로 든 함수에선 아무것도 리턴하지 않았지만, 만약 return n 이라고 한다면 몇을 리턴해야 하는가?

리턴 한 후 복사본이 종료되면 재귀를 호출한 전 단계 재귀로 돌아가는데 예시로 든 함수에선 recur(0)에서 종료되었다 그렇다면 recur(1)로 돌아가는데 이를 리턴해야 하는가?

def recur(n): #시작
	if n == 0: #종료 조건
		return #끝
	recur(n-1) #종료 조건에 부합하지 않는다면 괄호 안의 값으로 다시 함수를 실행한다.
	print(n)
	#return

재귀함수는 recur(n-1)을 만난 즉시 실행된다.

위의 동작과정들에서 설명했듯 recur(3) → recur(2) → recur(1) → recur(0) 에서 return을 만나 recur(0)이 종료되고 recur(1)로 돌아간다.

recur(0)을 호출했던 recur(n-1) → recur(1-1) 밑에 print(n)이 있기에 recur(1)의 n 인 1을 호출한다.

print(n) 밑에 return이 생략되어 있다. c언어에서 main문을 쓸 때 마지막 return(0)을 안써도 문제가 되지 않는 것 처럼 파이썬 또한 문제가 되지 않는다.

결론은 종료조건을 호출한 함수로 돌아간 후 그 값을 출력한다.

재귀는 종료 조건을 만나야 종료가 되기 때문에 무조건 명시해야 한다.

그렇지 않으면 무한으로 실행되고 스택 오버플로우가 터진다.

재귀에 리턴 값이 있다면?

아래는 위에서 든 예이다.

def recur(n): 
	if n == 0: 
		return 
	recur(n-1)

리턴 값이 없는 경우였다.

다음은 리턴 값이 있는 예이다.

def recur(n): 
	if n == 0: 
		return n
	recur(n-1)

위의 예를 살짝 바꾸어 보았다.

print(n)과 마찬가지로 n을 리턴 하는 것이기 때문에 리턴 값은 3이다.

하지만 위의 동작과정 처럼 recur(0)의 값인 0을 최종적으로 리턴해야한다면 다음과 같이 써야한다.

def recur(n): 
	if n == 0: 
		return n
	return recur(n-1)

위에는 print(n)과 마찬가지로 n을 리턴 하는 것이였지만 앞에 return을 붙여줌으로써 호출된 재귀가 리턴한 값을 리턴하면 되는 것이다.

이 것을 가장 잘 표현한 예시가 피보나치수열 구하기 인데 아래에서 살펴 보겠다.

피보나치 수열

첫 번째 항의 값이 0이고 두 번째 항의 값이 1일 때, 이후의 항들은 이전의 두 항을 더한 값으로 이루어지는 수열을 말한다.

예)

def fibo(n):
		if n <= 1: #n이 1과 같거나 작다면
				return n #n 리턴
		return fibo(n-1) + fibo(n-2) #괄호 안의 값으로 재호출 한다.
																#피보나치 수는 점화식으로 나타낼 수 있다
																#f(n) = f(n-1) + f(n-2)

#결과 출력
print(fibo(6))

#결과
#5

→ 위 코드 동작과정을 그림으로 나타냈다.

재귀함수로 피보나치 수열의 코드를 작성했을 때, f(n)함수에서 n이 커지면 커질수록 수행시간이 기하급수적으로 늘어나는 즉, 시간 복잡도가 엄청 커지는 문제 점이 생긴다.

위 그림에서도 f(2)가 두번이나 호출되는 것을 확인 할 수 있는데 n이 커지면 부분적으로 중복되는걸 더 많이 확인 할 수 있을 것이다.

피보나치 수열의 시간 복잡도는 O(2**N)인데, 그 예로 f(30)을 계산하기 위해 약 10억번의 연산을 수행해야하는 비효율적인 일이 생긴다.

따라서 DP(동적계획법)으로 풀이를 한다면 더 효율적으로 문제를 해결 할 수 있다.

[참조]

https://data-marketing-bk.tistory.com/27 # 팩토리얼을 이용한 재귀함수
https://veggie-garden.tistory.com/44 #백준 17478 이용한 재귀함수 설명
https://terms.naver.com/entry.naver?docId=1164771&cid=40942&categoryId=32209 #피보나치 수열의 정의 https://velog.io/@kimdukbae/다이나믹-프로그래밍-Dynamic-Programming #재귀함수로 푼 피보나치 수열의 문제점