[Algorithm] Recursion

이 글은 인프런에서 "영리한 프로그래밍을 위한 알고리즘 강좌"를 제 생각과 더불어 이해하기 쉬운 방식으로 정리한 글입니다.

Recursion(재귀, 순환)

def func(n):

	if n<0:
		return;
	else:
		print('hello World!')
		func(n-1)

n = 5
func(n)

hello World!
hello World!
hello World!
hello World!
hello World!
hello World!

Recursion은 단어 의미로 재귀 혹은 순환을 의미한다. 프로그래밍에서 Recursion은 자기 자신을 호출하는 함수를 의미한다. 재귀함수는 조건문을 구현하지 않으면 계속 반복하는 구조로 recursion에 빠지는 것을 방지하기 위한 Base case가 적어도 하나가 필요하고, base case로 수렴하기 위해 Recursive case도 필요하다. 

위 코드를 보고 설명하면, if 조건문에서 n<0인 조건을 통해서 재귀함수가 Recursion에 빠지지 않는 것을 알 수 있는데, 이 구간이 Base case가 된다. else구문에서 재귀함수로 자기 자신을 호출하는데 이때 인자를 n-1로 설정해서 base case에 수렴하기 위한 설정이 된다. 즉 이 부분이 Recursive case이다.

재귀함수는 개념은 이해하고 있지만 실제로 이 개념을 바탕으로 주어진 문제에 대해 어떻게 코드를 구현해야 하는지 모르는 경우가 많다. 일단 기본적인 재귀함수의 예제로 Factorial을 살펴보자.

def factorial(n):
	if n==0:
		return 1
	else:
		return n * factorial(n-1)

n = 4
print(factorial(n))

24

n! = 1 * 2 * 3 * ···· * n
for문(iteration)을 활용해서 팩토리얼을 구현하려고 하면, 저 공식 그대로 n의 값을 받아서 어떤 변수를 n까지 증가시키면 된다고 판단하고 코드를 작성한다. 그렇지만 재귀함수는 우리가 알고 있는 절차대로 연산을 수행하지 않는다는 것에서 어떻게 연산을 수행하는지 알 필요가 있다. 

재귀함수에서는 거꾸로 연산하는 것을 알 수 있다. 연산 방식을 수식으로 적으면 n! = n * (n-1) * (n-2) * ···· * (n-n)이 된다. 이처럼 연산 방식을 recursive한 형태로 바꿔보는 생각하는게 recursion을 구현할 때 더 좋은 방식으로 보인다.

 

Recursion vs Iteration

• 모든 순환함수와 반복문은 서로 변경이 가능
• 순환함수는 몇 경우에 따라 복잡한 알고리즘을 단순하고 알기 쉽게 표현이 가능
• 함수 호출에 따른 오버헤드가 발생(매개변수 전달, 액티베이션 프레임 생성)

 

문자열의 길이 계산

def str_len(string):
	if string == '' :
		return 0
	else:
		return 1+str_len(string[1:])

string = 'How do you write this code?'
print(str_len(string))

27

 

문자열의 길이 계산

def print_string(string):
	if len(string) == 0:
		return
	else:
		print(string[0])
		print_string(string[1:])

string = 'string'
print_string(string)

s
t
r
i
n
g

 

문자열 뒤집어 출력

def print_string(string):
	if len(string) == 0:
		return
	else:
		print_string(string[1:])
		print(string[0])
		

string = 'string'
print_string(string)

g
n
i
r
t
s

 

10진수 -> 2진수 변환

def print_binary(n):
	if n < 2:
		print(int(n));
	else:
		print_binary(n/2)
		print(int(n%2))
		

n = 5
print_binary(n)

1
0
1

 

Designing Recursion

재귀함수 설계는 위에서 언급했던 적어도 하나의 base case와 이것에 수렴하는 recursive case가 필요하다.

강의 내용에서 재귀함수를 표현하기를 암시적 매개변수가 아닌 명시적 매개변수로 변환하라고 했다. 코드로 설명하는게 이해가 빠를 것이다.

def sequencial_search(data_list, target):
	for index in range(len(data_list)):
		if data_list[index] == target:
			return index

	return -1	

range(len(data_list))에서 0~len(data_list)으로 반복하는데, 이 경우는 data_list에 data가 암묵적으로 data[0]부터 존재한다고 나타낸 것이다.

index의 시작점을 0이 아닌 어느 부분부터 시작해서 어디에서 끝낼지 명확하게 매개변수로 표현해주면 재귀함수의 형태를 가진다.

왼쪽에서 오른쪽으로 탐색

def sequencial_search(data_list, start, end, target):
	if start>end:
		return -1
	elif target == data_list[start]:
		return start
	else:
		return sequencial_search(data_list, start+1, end, target)
		

data_list = [4, 2, 1, 6, 5, 7, 3]
print(sequencial_search(data_list, 0, len(data_list)-1, 5))

4

위 코드에서 sequencial_search 함수의 매개변수를 보면 데이터 리스트, 시작점, 끝점, 목표값으로 구성되어 있다. 이렇게 명확하게 시작과 끝을 정의해주면 된다. 

오른쪽에서 왼쪽으로 탐색

def sequencial_search(data_list, start, end, target):
	if start>end:
		return -1
	elif target == data_list[end]:
		return end
	else:
		return sequencial_search(data_list, start, end-1, target)
		

data_list = [4, 2, 1, 6, 5, 7, 3]
print(sequencial_search(data_list, 0, len(data_list)-1, 5))

4

 

최댓값 구하기

def find_max(data_list, start, end):
	if start==end:
		return data_list[start]
	else:
		return max(data_list[start], find_max(data_list, start+1, end))
		

data_list = [4, 2, 1, 6, 5, 7, 3]
print(find_max(data_list, 0, len(data_list)-1))

7