[Python / 알고리즘] 재귀용법 이해와 쓰임.

*전체적인 내용은 6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016 에 기반했습니다.

 

 

 

개요

 오늘은 하노이의 탑 알고리즘에 대해 이해해보기 위해 재귀 용법(Recursive Function) 을 먼저 알아보겠습니다.

 

 

 

재귀용법이란?

•  알고리즘적으론, 문제에 대한 해법을 나눠서 해결, 줄여서 해결(divide-and-conquer,decrease-and-conquer)하는 방법.

  • 문제를 단순화해서 해결한다.

•  의미론적(Sementically)으론 자기 자신을 다시 호출하는 기능.

  • 프로그래밍에 있어, 무한정 재귀를 돌리는게 목적이 아님

    • 1개 또는 여러개의 base case에 대해 해결할 수 있어야 한다.

    • base case를 해결할 수 있으며, 어떠한 input에 대해서 문제를 해결할 수 있어야 한다.

-> 재귀용법은 기술적으론 자기 자신을 자신의 함수 내에서 호출하는 것입니다. 기능적인 부분 보다 알고리즘적인 부분을 더 유심히 생각해야 합니다. 위의 두 부분다 의미있습니다. 결국 기술적으론 아래의 의미론적인 부분을 충족시켜야하고, 왜 사용하냐고 묻는 것에는 알고리즘 적인 답변, 문제를 단순화해서 더 손쉽게 해결하기 위한 것이라고 답할 수 있어야 하기 때문입니다. 

 

 

 

재귀용법 이해1: 곱하기 $a*n$

$a*n$은 a를 n번 만큼 더하는 것과 같습니다.

 

 

루프 방식

def mult_iter(a, n):
	result = 0 #결과 값을 0으로 설정합니다.
    while n > 0: #n == 0이 되는 시점에 멈춥니다. -> n번만큼 루프가 돌아갑니다.
    	result += a #a를 result에 더합니다. -> a*n이 됩니다.
        n -= 1 #n을 줄입니다.
    return result

 일반적인 while loop 방식입니다. for loop 방식을 사용할 수도 있겠죠.

 

 

재귀방식

 

재귀 단계(Recursive Step)

문제를 어떻게 간략화된 방식으로 바꿀 수 있을지 생각한다.

 

$a*n = \underbrace{(a + a + a + a + ... + a)}$

                                                $n$

$= a + \underbrace{(a + a + a + a + ... + a)}$

                                       $n-1$

$= a + a*(n-1)$

 

베이스 케이스(Base case)

 문제를 줄여나가며 바로 풀 수 있는 가장 간단한 경우.

 이 알고리즘에선 n == 1인 경우

def mult(a,n):
	if n == 1: # base case
		return a
	else: # recursive step, a + a*(n-1) 과 같은 구조 
		return a + mult(a, n-1)

 

 

 

재귀용법 이해2: 팩토리얼 $n!$

팩토리얼의 정의는 다음과 같습니다.

 

$n! = n*(n-1)*(n-2)*(n-1)*...*1$

 

 

베이스 케이스

가장 간단한 경우 (보통 n =1 인 경우가 많은 것 같습니다.)

$n = 1  \rightarrow 1$

 

$n!$을 간략히 한다면?

->재귀 용법에서 간략히의 의미는 $a_n = f(a_{n-1}) + \alpha$ 을 만들라는 뜻으로 보입니다.

 

$n! = n*(n-1)!$

-> 재귀 패턴이 보입니다.

 

 

코딩 및 결과

def fact(n):
    if n == 1: # base case
        return 1
    else: #recursive step
        return n*fact(n-1)
print(fact(4))

 

재귀 관계

$print(\underbrace{fact(4)})$
$return(4*\underbrace{fact(3)})$
  $return(4*3*\underbrace{fact(2)})$
    $return(4*3*2*\underbrace{fact(1)})$
                        $return(4*3*2*1)$

위와같은 구조입니다.

 

 

 

요약

• 재귀용법의 정의는 두가지 측면에서 할 수 있음.

  • 알고리즘 : 큰 문제를 작게 줄이거나 나눠서 해결하는 방법

  • 의미론적 : 자기 자신을 다시 호출하는 방식

    • base case와 어떤 입력값에 대해서 해결 할 수 있어야 함.

• 재귀코드 만들기

  • $a_n = f(a_{n-1}) + \alpha$ 으로 식 정리하기

  • base case($n=0 또는 n =1$ 기타 경우 따라 적합한 경우)에 대해 입증됨을 보임.

 

 

 

다음 글에선

귀납적 추론을 통한 재귀용법 증명

 

 

 

참고자료

---

Lecture 6: Recursion and Dictionaries