[알고리즘] 재귀함수

 

재귀 함수는 함수 안에 자기를 다시 호출하는 함수이다.

알고리즘 문제 중 어떤 패턴이 반복적으로 나오거나, 같은 문제를 여러 번 풀어야 하는 상황이 생길 때

쓰이는 방법이다.

 

재귀 함수를 만드는 방법은 간단하다.

 

 

def infinity:
	print("재귀함수가 뭐냐면은...")
    infinity()

 

함수 안에 다시 자신의 함수를 호출하면 된다.

근데 위의 예시는 계속 자신의 함수를 무한정 호출하게 되므로

스택오버플로우 오류가 일어난다.

 

 

def function(k):
	if k <= 0 : return	# Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다
    else :			#  Recursive case : recursion을 반복하다보면 결국 Base case로 수렴해야 한다.
    	print("재귀함수가 뭐냐면은...")
        function(k - 1)
        
function(10)

 

스택오버플로우가 일어나지 않게 하려면

재귀 함수 내에 재귀 함수를 벗어나는 Base case라는 조건문이 있어야 한다.

 

마치 무한 반복문을 피하기 위해 조건문을 적는 것과 똑같다.

  

그러면 재귀 함수의 대표적인 사용 사례인 팩토리얼 알고리즘을 보자

 

 

 팩토리얼은 1부터 어떤 양의 정수 N까지의 정수를 모두 곱한 것을 의미한다.

예로 들면

 

3! 은 3 * 2 * 1 = 6

4! 은 4 * 3 * 2 * 1 = 24

 

그래서 40-32/2 = 24 = 4! 이므로 4!라고 대답한 초등학생의 답도 맞는다는 것이다.

 

여기서 

 

3! 은 3 * 2 * 1 = 6

4! 은 4 * 3 * 2 * 1 = 24

 

팩토리얼을 구하는 과정을 보면

Factorial(n) = n * Factorial(n - 1)

Factorial(n - 1) = (n - 1) * Factorial(n - 2)

...

Factorial(1) = 1

라는 구조가 보일 것이다.

4! 를 예로 들면 

 

Factorial(4) = 4 * Factorial(3)

Factorial(3) = 3 * Factorial(2)

Factorial(2) = 2 * Factorial(1)

Factorial(1) = 1

 

이래도 잘 이해가 안 가시면

하나씩 풀어보면 된다.

 

Factorial(4) = 4 * Factorial(3)

Factorial(4) = 4 * 3 * Factorial(2)

Factorial(4) = 4 * 3 * 2 * Factorial(1)

Factorial(4) = 4 * 3 * 2 * 1

 

이것을 재귀 함수 코드로 나타내면 다음과 같다

 

 

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

print(factorial(4))		# 24 출력

 

코드가 어떻게 동작하는지 어렵다면 디버깅을 꼭 해보길 바란다.

 

 

 

 

재귀 함수와 관련된 알고리즘 문제를 하나 풀어보자

 

 

 

numbers = [1, 1, 1, 1, 1] 
target_number = 3
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
	# 구현해보자
	return 
print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number))	# 5가 나와야한다

 

예시가 number는 [1,1,1,1,1], target_number는 3으로 헷갈릴 수가 있어

number = [2,3,1], target_number = 0으로 생각해보고 다시 풀어보자

일단 2,3,1을 연산해서 나올 수 있는 모든 경우의 수를 생각해보자

 

 

1. +2 +3 +1 = 6

2. +2 +3 -1 = 4 

3. +2 -3 +1 = 0 # 타겟!
4. +2 -3 -1 = -2 

5. -2 +3 +1 = 2 

6. -2 +3 -1 = 0 # 타겟!
7. -2 -3 +1 = -4
8. -2 -3 -1 = -7

 

이 경우의 수에서 반복되는 패턴을 찾아야 한다.

 

여기서 각 경우의 수에 +-연산자만 확인하자

 

1. +++

2. ++-

3. +-+

4. +--

5. -++

6. -+-

7. --+

8. ---

 

패턴이 보이나요?

정확히 말하자면 

 

N의 길이의 배열에서 더하거나 뺀 모든 경우의 수는
N - 1의 길이의 배열에서 마지막 원소를 더하거나 뺀 경우의 수를
추가하시면 된다.

 

이게 무슨 말이냐면

[2,3]을 배치하는 모든 경우의 수는

맨 마지막 원소인 1을 더하나 빼냐에 따라서 [2,3,1]의 경우의 수를 구할 수 있다는 것이다.

 

즉 계속 문제를 잘게 쪼개는 것이다.

더 이상 쪼개지지 못하는 크기로 잘게 쪼개 놓은 다음

그 문제들을 하나씩 풀어서 붙이는 것이다.

 

다시 [2, 3] 을 배치하는 모든 경우의 수는 다음과 같다.

 

 

1. +2 +3
2. +2 -3
3. -2 +3
4. -2 -3

 

여기서 1을 더하느냐 빼냐에 따라 경우의 수가 다음과 같이 생긴다.

 

1. +2 +3 → +1 = +2 +3 +1
            → -1 = +2 +3 -1
2. +2 -3 → +1 = +2 -3 +1
           → -1 = +2 +3 -1
3. -2 +3 → +1 = -2 +3 +1
            → -1 = -2 +3 -1
4. -2 -3  → +1 = -2 -3 +1
            → -1 = -2 -3 -1

 

하나씩 원소를 추가할 때마다

새로 추가된 원소를 더하고 빼는 경우의 수를 추가하면 된다.

 

 

numbers = [1, 1, 1, 1, 1]
target_number = 3
result_count = 0

# N의 길이의 배열에서 더하거나 뺀 모든 경우의 수는
# N - 1의 길이의 배열에서 마지막 원소를 더하거나 뺀 경우의 수를
# 추가하시면 됩니다.

def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(array):
        if current_sum == target:
            global result_count
            result_count += 1
        return

    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum + array[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1, current_sum - array[current_index])

get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
print(result_count)

 

정답 코드는 다음과 같다.

 

 

위의 코드는 get_count_of_ways_to_target_by_doing_plus_or_minus 함수 안에 (이하 get_count로 명명)

get_count를 다음 요소와 + 한 상태와 -1 한 상태로 다시 불러오는 것이다.

current_index가 배열의 길이와 똑같다면 끝까지 더하고 뺀 것이니

그때 나온 current_sum이 target가 똑같다면 count를 세주는 코드이다.

 

나는 계속 recursive case에 자기 함수를 한 번밖에 호출 못한다는 생각 때문에 못 풀었던 것 같았다.

 

재귀 함수는 자신의 함수 안에 여러 번 호출할 수 있다는 것도 중요한 것 같다.