데이터구조 5차시: Recursion을 이용한 거듭제곱 계산

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번 일어나야 된다.

이게 문제점이다.

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

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

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

어떻게 할 수 있을까? 

아래 동영상을 보면, 

그 해답을 알 수 있다.

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

위에서 설명한 내용에 대해 

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