데이터구조 6차시: Recursion을 이용한 피보나츠(Fibonacci) 수열계산과 하노이탑

Fibonacci 수열 계산하기.

Fibonacci 수열은 무엇인가?

대충 이름은 들어봐서 알 것이다.

숫자들을 늘어 놓은 것이니 수열일테고,

다만, 숫자들 사이에 특수한 관계가 있는 것인데,

어떤 숫자든 자기 앞의 두 개 숫자의 합과 같아야 한다.

이런 조건을 만족시키는 수열이 Fibonacci 수열이다.

잠깐,

Fibonacci 수열의 첫 번째와 두 번째 숫자는 모두 1이라는 것을

기억합시다.

Recursive함수를 이용하여 Fibonacci 수열 계산하기

Fibonacci 수열을 계산하는 것은,

recursion함수를 이용해서

구현하는 것이 

직관적이라서 쉽다.

line 4-14:

Fibonacci 숫자를 구하는 재귀함수이다.

이 때 인수 n의 의미는 "n 번째" 숫자이다.

그래서 

fibo(1)은 첫 번째 Fibonacci 숫자를 의미해서

'1'을 반환해야 한다.

fibo(2)는 두 번째 Fibonacci 숫자이니

'1'을 반환해야 한다.

fibo(3)은 세 번째 Fibonacci 숫자이니,

상식적으로 생각할 때, 

앞에앞에 숫자와 앞에 숫자를 더한 것이니

fibo(3) = fibo(2) + fibo(1)이 된다.

line 6-9:

첫 번째와 두 번째 Fibonacci 숫자인 경우를 처리하는 것으로,

1을 반환한다.

그래서,

이 부분은 재귀함수의 

탈출조건에 해당한다.

line 10-13:

fibo(n) = fibo(n-1) + fibo(n-2)를 구현한 것이다.

이 부분은,

자기 자신을 또 호출하고 있으니,

지속조건에 해당한다.

수행결과는 아래와 같이,

12번째 Fibonacci 숫자는 144임을 보여주고 있다.

Non-recursive방식으로 Fibonacci 수열 계산하기

Recursion함수를 사용하지 않고,

구현하는 non-recursive방법도

생각해 보자.

그리 어렵지는 않지만,

recursion함수 방법보다

더 손이 간다.

main함수는 전혀 변화가 없지만,

함수 fibo ( )가 바뀌었다.

자기자신을 호출하지 않는 형태로..

line 6-9:

첫 번째와 두 번째 Fibonacci 숫자를 처리하는 경우이고,

recursion경우와 똑같다.

line 10-23:

n번째 Fibonacci 숫자를 구하는데,

반복문을 사용한 것이다.

변수를 살펴보면,

beforebefore는 앞에앞에 숫자를 말하고,

before는 앞에 숫자를 의미하고,

me는 현재 숫자를 의미한다.

변수 i는 "몇 번째" 숫자를 구하고 있는지를 표시한다.

line 16-22:

Fibonacci 숫자를 계산하는 무식한 방법이다.

현재 숫자는 앞에앞에 숫자와 앞에 숫자를 더해서 구하고,

다음 번에 반복할 때는,

앞에앞에숫자는 앞에 숫자가 되고,

앞에숫자에는 현재 숫자가 되는 것이고,

이 과정을

원하는 n번째 숫자를 구할 때까지

반복하는 것이다.

하노이탑 (Tower of Hanoi)원반 옮기기

하노이탑 문제란 무엇인가? 

접시 옮기기다. 깨지 말고,,

위 그림에 보면 막대 A에 접시 5개가 있다.

규칙이 있다.

큰 접시위에 작은 접시.

하노이탑 문제는

접시 n개를 막대 C로 옮기는거다.

단, 제약조건은

1. 한 번에 하나씩만, 그러니, 5개를 한 번에 들어서 C에다가 꽂아 버리면 안 되는 것이다.

2. 큰 접시는 절대로 작은 접시 위에 있어서는 안되고,

3. 중간 막대 B를 이용해도 되는데, 1,2번 조건을 지키면서,,,

이게 가능해?!

당근, carrot,

가능하지.

3개를 어떻게 옮기는지 보여줄테다...

이걸 프로그램으로 구현할 수 있다고?!

carrot, too.

어떻게 구현하는지 보여줄테다....

그것도 recursion을 이용해서,,,

이게 실행이 된다고?!

carrot, three.

아래 출력결과를 봐봐.

이걸 따라서 한접시, 한접시 옮겨봐.

코드가 이해가 안되...ㅠㅠ

걱정하지말아요, 그대,

이걸 글로 쓰기는 너무 긴 이야기지만,

아래 동영상을

보면 쉽게 이해가 갈겁니다.

시인 릴케와 Recursion

Recursion을 제대로 이해한다는 것은 어렵다.

불가능하지는 않지만,,,

일단 이해하려고 무지 노력을 해보고,

안되면,

시인 '릴케'의 말을 위안삼자.

아래 동영상에서는

Recursion을 이용한 Fibonacci 수열계산이

어떻게 이루어지는지 "매우 상세히" 설명하고 있으니,

보시면 큰 도움이 됩니다.

그리고, 

하노이탑 알고리즘에 대해서 이해가 쉽게 될 수 있도록 설명하고 있습니다.