데이터구조 4차시: Recursion

Recursion: 재귀함수, 순환함수

Recursion함수의 개념

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

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

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

그런데,

이해하기는 쉽지 않다.

Recursion 함수를 정의하자면 

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

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

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

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

헐...

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

혹시,,

이런 경험있으세요,,

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

엘리베이터에 탔다.

혼자였다.

옆에 붙은 거울을 보는데,

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

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

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

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

다만,

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

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

물론

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

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

Factorial 계산

이건 뭐지, 

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

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

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

실행결과는 잘 나온다.

Recursion을 이용한 factorial 계산

반복문으로 짰던 것을

이제

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

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

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

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

하나는 탈출 파트,

다른 하나는 지속 파트,

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

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

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

알고 싶으시죠.. 

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

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

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