[12주차] 재귀호출

4월 8일 자 학습 내용 정리입니다.

 

 

✅ 재귀호출

재귀호출(recursive call)은 함수가 자기 자신을 호출하는 것이다.

이러한 재귀 호출은 자기가 자신을 계속해서 호출하므로, 끝없이 반복되게 된다.

따라서 함수 내에 재귀 호출을 중단하도록 조건이 변경될 명령문을 반드시 포함해야 한다.

 

재귀호출의 예로는 팩토리얼이 있다.

팩토리얼(factorial)은 n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 

이를 코드로 구현하면 다음과 같다.

 

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

 

Factorial 함수의 구현에는 재귀호출이 포함되어있다.

n = 5 일 때, Factorial 함수의 호출 과정은 아래와 같다.

 

 

출처 : https://blog.penjee.com/recursion-animated-gifs-cs/

 

 

✅ 수학적 귀납법과 재귀호출

수학적 귀납법은 명제 P(n)을 다음과 같이 증명하는 방법이다.

1.  N = 1일 때 성립함을 보인다.
2. P(k)가 성립한다고 가정할 때 P(k+1)이 성립함을 보인다.
3. 따라서 모든 자연수 n에 대하여 P(n)이 성립한다.

수학적 귀납법은 재귀적 증명법이다.
위의 증명 방법에서 알 수 있듯 하나의 명제를 증명하기 위해 똑같은 증명 방법을 사용한다.

 

재귀호출은 재귀적 계산법이다.
수학적 귀납법이 명제를 대상으로 한다면 재귀호출은 값을 대상으로 하는 것이다.
이 차이만 제외하면 둘은 거의 비슷하다고 볼 수 있다.

 

따라서 재귀호출을 이해할 때 수학적 귀납법을 사용하는 것이 편리하다.
모든 n에 대해 동작이 어떻게 이루어지는지 이해하는 것이 아니라 값을 확실히 알 수 있는 것(예를 들어 N=1일 때 명제가 성립함과 같은 것)을 두고 그 값과 n의 사이에 있는 값들에 대해서는 제대로 구해진다고 생각하면 된다.

 

결론적으로 재귀함수를 디자인하는 방법은 아래와 같다.

1.  함수의 정의를 명확히 한다.
2. 기저조건(Base condition)에서 함수가 제대로 동작하게 작성한다.
3. 함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다.

 

 

✅ 퀵 정렬

퀵 정렬(Quick Sort)은 재귀 호출을 이용한 대표적인 정렬이다.

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

이때 기준을 피벗(Pivot)이라고 한다.

보통의 경우 피벗은 리스트의 첫 번째 데이터로 설정한다.

 

피벗을 설정한 뒤에는 피벗을 기준으로 값을 비교한다.

피벗보다 작은 값들은 피벗의 왼쪽에, 피벗보다 큰 값들은 피벗의 오른쪽에 오도록 리스트를 둘로 나눈다.

이 과정이 끝났다면 분할된 리스트에 대해 재귀적으로 위 과정을 반복한다.

 

def QuickSort(data):
  if len(data) <= 1:
      return data
  
  pivot = data[0]
  
  left = list(filter(lambda x: x < pivot, data))
  right = list(filter(lambda x: x > pivot, data))
  
  return QuickSort(left) + [pivot] + QuickSort(right)

 

재귀호출이 한 번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지기 때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

 

🔍 참조

재귀호출 http://www.tcpschool.com/c/c_function_recursive 

팩토리얼 https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9  

퀵정렬 https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC