(이코테 w/ Python) DFS & BFS 재귀함수 (Recursive Function)

재귀함수(Recursive Function)란?

자기 자신을 다시 호출하는 함수를 의미한다. 

재귀함수는 실질적인 dfs를 실질적으로 구현하고자 할 때 자주 사용하는 방법이다. 

 

단순한 형태의 재귀 함수의 예제를 살펴보자.

‘재귀 함수를 호출합니다.’ 라는 문자열을 무한히 출력하고자 할 때

어느 정도 출력하다가 최대 재귀 깊이 초과 메세지가 출력된다.

 

재귀 함수의 종료 조건

재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.

의도적으로 무한 루프를 이용하는 것이 아니라면 반드시 종료 조건을 명시하여 프로그램이 정해진 값을 반환할 수 있도록 만들어야 한다.

종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있으므로 오류 발생 가능성이 있다. 

종료 조건을 포함한 재귀 함수 예제

if i == 100:

이와 같이 재귀함수 시작부분에 종료조건을 명시해서 특정한 조건을 만족한다면 함수가 종료될 수 있도록 만들 수 있다.

전달받은 i 매개변수 값이 100인 경우에 종료될 수 있도록 조건을 명시하고 있다.

 

resursive_function(i+1)

i+1로 다음 재귀변수를 호출하도록 만들면 재귀함수가 호출되는 과정에서 매개변수 i값이 차례대로 증가하기 때문에 총 99번 만큼 재귀함수가 호출된 뒤에 100번째 재귀함수는 바로 종료될 수 있도록 만든다.

 

재귀함수는 마치 스택에 데이터를 넣었다가 꺼내는 것과 마찬가지로 각각 함수에 대한 정보가 실제 스택 프레임에 담기게 되어서 차례대로 호출이 되었다가 가장 마지막에 호출된 함수부터 차례대로 종료가 되어 첫 번째 호출했던 함수까지 종료하게 되는 것이다.

 

 

팩토리얼 구현 예제

FYI) 수학적으로 0!과 1!의 값은 1이다.

 

반복적으로 구현하고자 한다면 

result 값에 1을 넣어준 뒤에

1부터 n까지의 값 전부 다 result에 곱해주는 방식을 이용하였다. 

1부터 n까지 곱해진 결과 값이 반환된다.

 

재귀적으로 구현하고자 할 때 재귀함수를 이용한다.

return n * factorial_recursive(n-1)

n!를 호출하면 자기 자신 n에다 자기 자신보다 1 작은 만큼의 !를 호출한 값을 곱한 결과를 반환한다는 뜻이다.

예를 들어, 5!를 호출하게 되면 (5 * 4)!이 되는 것이고 4!은 재귀적으로 함수가 실행되어 (4*3)! 값이 반환된다. 

 

1!이 호출된 시점에서 1! 값은 1이기 때문에 1을 반환한다 (return 1)

 

 

최대공약수 계산 (유클리드 호제법)

두개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다. 

(최대공약수란 두개의 자연수가 있을 때 두 자연수의 공통된 약수 중에서 가장 큰 값을 의미한다.)

 

유클리드 호제법이란 

• 두 자연수 A, B에 대하여 (A>B) A를  B로 나눈 나머지를 R이라고 하자. 
• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.

유클리드 호제법의 아이디어를 그대로 재귀함수로 작성할 수 있다. 

예시: 192와 162의 최대공약수를 구해보자. (GCD(192, 162))

단계	A	B
1	192	162
2	162	30
3	30	12
4	12	6

192와 162의 최대공약수는 192를 162로 나눈 나머지인 30을 구한 뒤에 

162와 30의 최대공약수와 같은 값을 갖는다는 것을 알 수 있다.

그래서 192와 162의 최대공약수의 식을 더 낮은 값의 형태인 162와 30의 최대공약수를 구하는 문제로 바꾼 것이다.

 

162와 30의 최대공약수는 30과 12의 최대공약수와 같다. 12와 6의 최대공약수와 같은 것을 알 수 있다.

즉, 192와 162의 최대공약수는 12와 6의 최대공약수와 같음을 알 수 있다. 

 

더 작은 수를 이용해 식을 간단하게 바꾸는 형태가 반복적이며 동일한 형태를 갖고있기 때문에 재귀함수를 이용해서 코드로 옮길 수 있다. 

 

12는 6의 배수이기 때문에 6을 최대공약수라고 말할 수 있다. 

그러므로 192와 162의 최대공약수는 6이다. 

 

유클리드 호제법 예시 코드

if a % b == 0

a를 b로 나눈 나머지 값이 0이라면 (a가 b의 배수라면) b를 반환할 수 있도록 하고

else:
	...

그렇지 않다면 b와 a를 b로 나눈 나머지의 최대공약수를 반환할 수 있도록 한다.

 

 

재귀함수 사용 시 유의사항

재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다. 

단, 다른 사람이 이해하기 어려운 형태의 코드가 될 수 있다. 

 

모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.

재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우가 있다.

컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 그래서 스택을 사용할 때 구현상 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다.