-
스택에는 위와 같이 factorial(5)부터 factorial(1)까지 쌓이게 되며, 이후 fac(1)부터 1을 반환하면서 스택에서 제거 된다.활성레코드 fac(1) fac(2) fac(2) fac(3) fac(3) fac(3) fac(4) fac(4) fac(4) fac(4) fac(5) fac(5) fac(5) fac(5) fac(5)
∴ 최대 5개의 활성 레코드가 동시에 존재할 수 있다.
-
(4)번
-
(4)번
-
(3)번
-
함수를 순환호출하는 부분에서 문제의 크기 n이 줄어들지 않아, 똑같은 크기 재귀호출만을 계속 반복하게 된다.
-
순환호출을 멈추는 조건이 명시되지 않아, 순환이 멈추지 않게 된다.
-
s(5)
= prt(5), 5+s(4) = 16
= prt(4), 4+s(3) = 11
= prt(3), 3+s(2) = 7
= prt(2), 2+s(1) = 4
= prt(1), 1+s(0) = 2
= prt(0), return 1
∴ 5, ..., 0까지 출력되며, 반환값은 16이다.
-
r(5)
= prt(5), 2×rec(4)+1
= prt(4), 2×rec(3)+1
= prt(3), 2×rec(2)+1
= prt(2), 2×rec(1)+1
= prt(1), 2×rec(0)+1
= prt(0), return 2
∴ 5, ..., 0까지 출력되며, 반환값은 16이다.
-
r(10)
= prt(10), r(7)+1
= prt(7), r(4)+1
= prt(4), r(1)+1
= prt(1), r(-2)+1
= prt(-2), return -1
∴ 10, ..., -2까지 출력되며, 반환값은 3이다.
-
r(5)
= r(4), prt(5)
= r(3), prt(4)
= r(2), prt(3)
= r(1), prt(2)
= prt(1)
∴ 1, ..., 5까지 출력된다.
-
a(5)
= a(2), a(2), prt(※)
= a(1), a(1), prt(※), a(1), a(1), prt(※),
= prt(※), prt(※), prt(※), prt(※)
∴ asterisk는 7번 출력된다
-
반대로 출력되어, evisrucer 가 출력된다.
sum (int n) {
if (n<=1)
return 1;
else
return n+sum(n-1);
}double sum(int n) {
if (n==1)
return 1;
else
return 1.0/n + sum(n-1);
} - 생략
int sum(int n) {
int s = 0;
for(int i=1;i<=n;i++)
s+=i;
return s;
} 순환)
int bin(int n, int k) {
if ((k==0)||(n==k))
return 1;
else
return bin(n-1, k-1) + bin(n-1, k);
} 반복)
int bin(int n, int k) {
int mul1=1, nul2=1;
for(;k>=1;k--, n--) {
mul1 *=n;
mul2 *=k;
}
return mul1/mul2;
} - (a)
A(3, 2) → 29
= A(2, A(3, 1)) → 29
= A(2, A(3,0)) → 13
= A(2, 1) → 5
= A(1, A(2,0)) → 5
= A(1, 1) → 3
= A(0, A(1,0)) → 3
= A(0, 1) → 2
각각을 풀어서 해결하면 다음과 같다. 따라서 A(3, 2) = 29 이다.
또한 A(2, i)일때 규칙성으로 인해 그 값은 3+2×i 이다.
따라서 A(2, 3) = 9 이다.
(b)
int A(int m, int n) {
if (m==0)
return (n+1);
if (n==0)
return A(m-1, 1);
return A(m-1, A(m, n-1));
} (c)
int A(int m, int n) {
while (m) {
if (n==0)
n = 1;
else
n = A(m, n-1);
m-=1
}
return (n+1);
} - 순환: O(2ⁿ), 반복: O(n)으로 반복이 더 효율적이다
- (1) n의 값이 줄어든다
(2) 옮겨야 되는 원판의 수가 줄어든다.
- 생략
