프로그램 명: powerofx
x 의 y 거듭제곱을 구하는 문제이다.
2 10 을 입력 받으면 2 의 10 거듭제곱 1024 가 출력되어야 한다.
2^10 = 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2=1024
출력 결과는 정수 범위( 2^31 - 1)를 넘지 않는다.
입력 2 10 출력 1024
[소스코드 풀이]
지수(y)의 숫자 만큼 밑수(x)를 곱하기 때문에, y가 1이 될 때까지 재귀적으로 함수를 호출해서 밑수를 계속 곱해준다.
| [재귀] 계단 오르기 (0) | 2014.05.15 |
|---|---|
| [재귀] 유클리드 호제법 (0) | 2014.05.15 |
| [Doc.] 재귀 (recursion) (0) | 2014.05.15 |
재귀(Recursion)
수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다.
- Wiki, 위키 백과 -
특징
long factorial(int number)
{
...
factorial(number - 1); // 함수 내부에서 자기 자신의 함수를 호출 (재귀함수)
...
}
n!
계승 수식은 재귀적 특성을 갖음
↓
long factorial(int number)
{
if (number <= 1)
return 1;
else
return (number * fatorial (number -1));
}
피보나치 수
0 1 1 2 3 5 8 13 21 ...
int fibo(int n)
{
if (n==0) return 0;
else if (n==1) return 1;
else return return fibo(n-1) + fibo(n-2);
}
main()
{
printf("%d", fibo(4));
}
long fibo (int n)
{
int fn, fn1, fn2;
int i;
if (n <=1) return n;
else {
fn2 = 0;
fn1 = 1;
for (i=2; i<=n; i++) {
fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
}
}
팩토리얼 문제나 피보나치 수열 문제 말고도 재귀를 대표하는 문제들을 많이 있습니다. (ex. 하노이의 탑)
| [재귀] 계단 오르기 (0) | 2014.05.15 |
|---|---|
| [재귀] 유클리드 호제법 (0) | 2014.05.15 |
| [재귀] x의 y 거듭제곱 (0) | 2014.05.15 |
|
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 |
