[파이썬 자료구조] 02. 재귀와 수학적 귀납법

1. 재귀(recursion)

 어떤 문제나 함수 등이 자신과 성격이 똑같지만 크기가 더 작은 문제를 하나 이상 포함하고 있는 구조

=자기호출

 

2. 수열

1) 등차수열

a_{n}=a_{n-1}+4, a_{1}=5

 

위 수열을 알고리즘으로 구현해 보자. 

 

seq(n):
	if (n = 1)
    	return 5
    else
    	return seq(n-1) + 4

 

알고리즘 seq(n)은 seq(n-1) 호출, seq(n-1)은 seq(n-2) 호출...

seq(1)은 5를 리턴

이후 역순으로 진행

seq(2)는 seq(1)의 리턴 값을 받아 4를 더해 리턴...

 

-재귀 알고리즘은 반복해서 호출하다가 언젠가 끝나야 하는데 이를 경계 조건이라고 한다. 

-위 예제에서는 if(n=1)이 경계 조건

 

2) 피보나치 수열

f_{n}=f_{n-1}+f_{n-2}, f_{1}=f_{2}=1

 

fib(n):
	if (n=1 or n=2)
    	return 1
    else
    	return fib(n-1) + fib(n-2)

재귀 ver.

fib_fast(n):
	f[1] <- f[2] <- 1  #"f[2] <- 1"과 f[1] <-1"을 한꺼번에 적어놓은 것
    for i <-3 to n
    	f[i] <- f[i-1] + f[i-2]
        return f[n]

비재귀 ver.

 

3) 하노이 탑

# 기둥 a에 있는 n개의 원반을 기둥 c를 보조 기둥으로 사용해 기둥 b로 옮긴다. 
move(n, a, b, c):
	if(n>0)
    	move(n-1, a, c, b)
        a에 있는 원반을 b로 옮긴다
        move(n-1, c, b, a)

 

(i) 맨 아래 원반을 제외한 나머지 n-1개의 원반을 기둥 c로 옮긴다. 

(ii) a에 남은 원반 1개를 b로 옮긴다.

(iii) c로 옮겨둔 n-1개의 원반을 b로 옮긴다. 

 

4) 선택 정렬

selectionSort(A[], n):
	for last <- n-1 downto 1
    	A[0...last] 중 가장 큰 수 A[k]를 찾는다
        A[k] <-> A[last] <-A[k]와 A[last]의 값을 교환한다.

selectionSort(A[], n): #배열 A[0...n-1]를 정렬한다. 
	if(n>1)
    	A[0...last] 중 가장 큰 수 A[k]를 찾는다
        A[k] <-> A[last] #A[k]와 A[last]의 값을 교환한다. 
        selectionSort(A, n-1) #배열 A[0...n-2]를 정렬한다.

 

5) 중위, 전위, 후위 표현법

-중위 표현법(Infix Expression): A+B와 같이 연산자가 피연산자 사이에 높이는 수식

<infix> = <변수> | <infix><연산자><infix>
<연산자> = + | - | * | /
<변수> = A | B | ... | Z

-전위 표현법(Prefix Expression): 연산자를 앞에

<prefix> = <변수> | <연산자><prefix><prefix>
<연산자> = + | - | * | /
<변수> = A | B | ... | Z

-후위 표현법(Postfix Expression): 연산자를 뒤에

<postfix> = <변수> | <postfix><postfix><연산자>
<연산자> = + | - | * | /
<변수> = A | B | ... | Z

=> <postfix> 안에 <postfix>가 2개 포함되어 있다. 즉,  <postfix>는 재귀적이다!

 

6) 깊이 우선 탐색(Depth-First Search)

# 노드 x에서 이를 수 있는 모든 노드 찾기
# 모든 노드 v에 대해 v.visited는 false로 초기화됨
DFS(X):
	x.visited <-true
    x에서 화살표로 연결된 모든 노드 y 각각에 대하여
    	if (y.visited = false) DFS(y)

 

3. 재귀와 수학적 귀납법

1) 모든 재귀 알고리즘은 명시적 또는 묵시적으로 다음 세 가지 구성 요소를 갖추어야 한다. 

 ① 경계 조건(Base Condition)(또는 종료 조건): 재귀 호출이 반복되다 궁극적으로 끝나는 조건

 ② 재귀 호출

 ③ 관계: 닮음꼴 작은 문제(들)와 본 문제 간의 관계를 나타내는 부분

 

경계 조건은 수학적 귀납법의 베이스 케이스와 대응되고, 재귀 호출은 귀납적 가정과 대응되고, 관계는 자신보다 작은 문제에 대해 귀납적 가정을 하고 나면 자신이 맞다는 것을 보이는 과정과 대응된다. 

 

📒쉽게 배우는 자료구조 with 파이썬 연습문제 풀이

01. 

def seq(n):
	if n == 1:
    	return 0
    else:
    	return 5 * seq(n - 1) + 3

 

02. 

n회

 

03.

9회

 

04. 

31회

 

재귀적으로 보면, move(n)은 2번 move(n-1) 호출 + 1번의 실제 원반 이동

점화식은 다음과 같다. 

T(n)=2T(n-1)+1

따라서 2^n-1회 호출되므로

답은 2^5-1 31회이다.

 

05. 

move 함수 호출 횟수와 실제 원반 이동 횟수는 같다. 

 

06. 

무한 루프가 발생하여 스택 오버플로우를 야기할 수 있다. 

 

07. 

n회

 

08. 

정수의 문자열 표현