소프트웨어 개구리

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로 옮기는거다.

단, 제약조건은

이게 가능해?!

당근, carrot,

가능하지.

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

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

carrot, too.

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

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

이게 실행이 된다고?!

carrot, three.

아래 출력결과를 봐봐.

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

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

걱정하지말아요, 그대,

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

아래 동영상을

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

시인 릴케와 Recursion

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

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

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

안되면,

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

아래 동영상에서는

Recursion을 이용한 Fibonacci 수열계산이

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

보시면 큰 도움이 됩니다.

그리고, 

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

Recursion을 이용한 거듭제곱의 계산

재귀함수를 이용해서

거듭제곱을 계산하는 프로그램을 작성해보자.

거듭제곱

이게 무엇인가?

아래와 같은 것을 말한다. 길게 설명할 필요는 없을 것 같다.

우리 말로는 2는 밑, 3은 지수라고 했던 것 같은데,

영어로는 base와 exponent이다.

우리 말로는 '2의 3승' 이라고 읽는데,

영어로는 'two to the third power' 혹은 

간단히 'two to the three'라고 읽는다.

Non-recursive로 거듭제곱 계산하기

거듭제곱을 계산하는 C언어 프로그램을 작성해보자.

for-loop 반복문을 사용하면 아주 쉽게 구현할 수 있다.

Non-recursive 함수로 구현하기

위에서는 main함수 안에서 구현했는데,

별도의 함수로 만들면 활용성이 높다.

그래서,

아래와 같이 구현해 본다.

line 6-15: 

지수승을 계산해서 반환하는 함수 calcPower함수를 정의했다.

두 개의 인수를 받는다.

base와 exponent.

지수승 계산은 단순히 반복문을 이용해서 한다.

Recursive함수로 거듭제곱 계산하기

함수 calcPower( )를 recursion함수로 만들면 된다.

아래와 같이....

line 6:

함수 calcPower의 반환형, 인수에는 변함이 없다.

line 8-11:

recursion함수의 탈출 조건에 해당하는 부분이다.

exponent가 1이 되면, 더 이상 진행하지 않고,

base를 반환하고 끝낸다.

어떤 숫자이든 1승은 자기 자신이므로.

line 12-15:

recursion함수의 지속 조건에 해당하는 부분이다.

base 값에 

을 곱해주기 위해서

자기자신을 호출한다.

단, calcPower(based, exponent-1)을 호출해서,,

Recursive함수기반의 거듭제곱 계산을 개선해보자

개선하려면 문제점이 무엇인지 알아야 한다.

문제점은,

을 예로 들어보자.

이것을 계산하기 위해서는 자기자신 호출이 1000번 일어나야 된다.

이게 문제점이다.

너무 많이 자기자신을 호출한다는 것이다.

호출되는 횟수를 줄일 수는 없을까?

이게 문제점이요, 개선포인트이다.

어떻게 할 수 있을까? 

아래 동영상을 보면, 

그 해답을 알 수 있다.

엄청나게 개선시킬 수 있는 방법이 있다,,

위에서 설명한 내용에 대해 

보다 자상하게, 또박또박 얘기해 주는 동영상입니다.

Recursion: 재귀함수, 순환함수

Recursion함수의 개념

recursion함수는 묘한 매력이 있다.

이걸 사용해서 프로그램을 짜면,

엄청나게 짧게 짜더라도, 놀라운 일을 후딱 해치우기 때문이다.

그런데,

이해하기는 쉽지 않다.

Recursion 함수를 정의하자면 

함수가 내부에서 자기 자신을 호출하는 것이다.

보통은 함수가 다른 함수를 호출하거나,

일을 끝내면 return하는 것이 도리이거늘,

recursion함수는 자기 자신을 호출한다.

헐...

그러면, 이건 도대체 뭘 의미하는가?

혹시,,

이런 경험있으세요,,

밤 늦은 시간에 지친 몸을 이끌고

엘리베이터에 탔다.

혼자였다.

옆에 붙은 거울을 보는데,

그 반대쪽에도 거울이 붙어 있다.

그러면 이런 일이 벌어진다. 거울 속에 내가 있고, 그 안에 내가 있고, 그 속에 내가 또 있다.

이게 끝이 아닌다. 그 속에 내가 있는데, 그 안에 있는 너는 뭐냐? 너지 뭐냐....

Recursion함수는 엘리베이터 거울에 비친 내모습 같은 것이다.

다만,

엘리베이터 거울은 무한대이지만,

recursion함수는 유한하게 만들 수 있다.

물론

무한한 recursion함수도 만들 수 있지만,

컴퓨터 메모리의 한계로 어느 정도 하다보면 프로그램이 종료된다.

Factorial 계산

이건 뭐지, 

n이 놀라고 있는 표정이지,,,

이걸 계산하는 프로그램을 작성해보자.

recursion없이...반복문으로 짜면

실행결과는 잘 나온다.

Recursion을 이용한 factorial 계산

반복문으로 짰던 것을

이제

굳이 recursion을 이용해서 짜보자.

그나마 factorial 예제가 recursion을 이해하기가 쉽다.

함수 int fact(int n)은 재귀함수이다.

재귀함수는 두 부분으로 이뤄어 진다.

하나는 탈출 파트,

다른 하나는 지속 파트,

지속 파트에서는 자기 자신을 호출한다.

탈출 파트에서는 자기 자신을 더이상 호출하지 않는다.

위 프로그램이 어떻게 동작하는지 자세히

알고 싶으시죠.. 

아래 동영상을 보시면 손그림을 그려가면서

자세히 설명해 주고 있습니다.

위에서 설명한 내용을 동영상으로 보고 싶으면,,,