1. 팩토리얼을 계산하는 순환호출 함수 factorial에서 매개 변수로 5를 주었다면 최대 몇 개의
factorial 함수의 활성 레코드가 동시에 존재 할 수 있는가 ?
정답 5개
02. 순환 호출을 하였을 경우에 활성 레코드들이 저장되는 위치는 어디인가?
(1) 순환 호출 함수내부
(2) 변수
(3) 배열
(4) 스택
4번 스택
3. 다음 중 활성 레코드에 저장되지 않는 것은 무엇인가?
(1) 매개변수의 값
(2) 함수호출이 끝나고 복귀할 주소
(3) 지역변수
(4) 순환호출의 순차번호
4.하나의 함수가 호출할 수 있는 순환호출의 개수는?
(1) 1번
(2) 2번
(3) 스택이 허용하는 한도
(4) 무제한
-> 스택에서 허용하는 한도를 넘으면 StackOverFlower가 발생함.
즉 탈출루트가 없으면 무한 재귀함수가 발생
05. 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n){
if(n==1) return 0; // <-- return 0이면 0을 몇천만번 곱해도 답은 0임. 출력결과는 0이 나옴. 곱셈이기에
return n * recursive(n);
}
06. 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n){
printf("recursive(%d) \n",n); // <-- 탈출문이 존재하지 않음 . 무한재귀 호출
return n * recursive(n-1);
}
07.다음 함수를 sum(5)로 호출하였을 때 , 화면의 출력되는 내용과 함수의 반환 값을 구하라.
int sum(int n){
printf("%d \n",n);
if(n < 1) return 1;
else return (n + sum(n-1));
}
출력결과 노란색 형광팬 칠한 것.
08. 다음 함수를 recursive(5)로 호출 하였을 때 , 화면의 출력되는 내용과 함수의 반환값을 구하라.
int recursive(int n){
printf("%d \n",n);
if(n < 1 ) return 2;
else return (2 * recursive(n -1)+1);
}
[출력 결과]
5
4
3
2
1
0
95
09. 다음 함수를 recursive(10)로 호출하였을 때 , 화면에 출력되는 내용과 함수의 반환값을 구하라.
int recursive(int n){
printf("%d \n",n);
if(n < 1 ) return -1;
else return (recursive(n-3)+1);
}
[출력 결과]
10
7
4
1
-2
3
10. 다음 함수를 recursive(5)로 호출하였을 때 , 화면에 출력되는 결과를 써라.
int recursive(int n){
if(n != 1) recursive(n - 1);
printf("%d\n",n);
}
[출력 결과]
1
2
3
4
5
2
답이 2인 이유
이 재귀함수의 경우 return 값이 존재하지 않고 1이 아닐때 그냥 출력만 하라고 적혀있음.
그렇기 때문에 n이 1이 아닌 마지막 시점은 2가 됨.
그렇기 때문에 2가 리턴값으로 계속 넘어와 답이 2가됨.
11. 다음 함수에서 asterist(5)를 호출할 때 출력되는 *의 개수는?
void asterisk(int i){
if( i > 1 ) {
asterisk(i/2);
asterisk(i/2);
}
printf("*");
}
정답 : 7개
12. 다음과 같은 함수를 호출하고 "recursive" 문자열을 입력한 다음 , 엔터키를 눌렀다면
화면에 출력되는 것은?
unknown()
{
int ch;
if(ch == getchar() != '\n')
unknown();
putchar();
}
* getchar : 사용자가 키보드로 입력한 문자 혹은
문자열에서 한 글자를 읽어서 반환하는 함수.
* putchar : 문자를 모니터화면(콘솔)에 출력하는 함수.
13. 다음을 계산하는 순환적인 프로그램을 작성하시오.
1 + 2 + 3 + ... + n
int sum(int n){
if(n <= 1) return 1;
else return n + sum(n-1);
}
14. 다음을 계산하는 순환적인 프로그램을 작성하시오.
1 + 1 / 2 + 1 / 3 + .... + 1 / n
double division(double n){
if(n==0) return 0;
else return (1/n) + division(n-1);
}
15. 순환 호출되는 것을 이해하기 위하여 fib 함수를 다음과 같이 바꾸어서 실행하여 보라.
fib(6)을 호출할 때 화면에 출력되는 내용을 쓰시오.
총 25번을 돌아야 하는데.. 적다가 햇갈려서 실수낫나보다 이렇게 전위로 피보나치가 출력되는 걸 알면된다.
나도 실수했는데 귀찮아서.. 그냥 이런식으로 돌아간다고 생각하자.. 직접 해봐도 되고
16. 다음의 순환적인 프로그램을 반복 구조를 사용한 비순환적 프로그램으로 바꾸시오.
int sum(int n){
int result = 0;
for(int i=1; i<=n;i++){
result += i;
}
return result;
}
17. 이항계수를 계산하는 순환함수를 작성하시오. 또한 반복함수로도 작성하시오.
이항계수란?
이항 계수는 조합론에서 사용되는 개념으로 , 주어진 집에서 원하는 개수만큼 원소를 선택 하는
방법의 수를 나타낸다.
다시말해 n개의 원소 중에서 k개의 원소를 선택하는 경우의 수를 의미한다.
예를들어 5개의 원소 (A,B,C,D,E) 중에서 2개의 원소를 선택하는 경우
C(5,2)로 표기하며 다음과 같이 계산된다.
C(5,2) = 5! / (2! * 3!) = 10
!는 팩토리얼을 나타내며 , 5! = 120을 의미한다.
즉 5개의 원소중 2개의 원소를 선택할때의 경우의 수는 10개가 됨으로
이항계수 (5,2)의 경우의 수는 10이된다.
마찬가지로 C(8,2)을 할경우
8! / 5! * 2! 이됨으로
40,320/(2*720) = 28
경우의 수는 28개가 된다.
int binomial(int n,int y){
if(n == y || y == 0) return 1;
return binomial(n - 1 , y - 1) + binomial(n - 1 ,y);
}
순환적 코드로 작성 시
이런식으로 피보나치 수열과 비슷한 형태로 된다고 생각하면 된다 (화이트 보드는 신경 쓰지 말길 바람 나도 햇갈려서;)
즉 x == y랑 같으면 1을 더하거나 y == 0이면 1을 더함으로
총 경우의 수는 10개가 된다.
int repeat_Binomial(int n,int y){
int value1 = 1;
for(int i = n; i !=1;i--){
value1 = value1 * i;
}
int value2 = 1;
for(int i = n-y; i!=1;i--){
value2 = value2 * i;
}
int value3 = 1;
for(int i = y; i!=1;i--){
value3 = value3 * i;
}
return value1/(value2*value3);
}
단순 반복코드
19. 본문의 순환적인 피보나치 수열 프로그램과 반복적인 피보나치 수열 프로그램의 수행시간을 측정하여 비교하라. 어떤 결론을 내릴 수 있는가?
답:
순환 피보나치 수열은 많은 계산을 반복적으로 수행해서 수행시간이 많이 길어진다.
시간 복잡도 비교하면 반복함수는 O(n), 순환함수는 O(2^n) 이므로 반복이 더 효율적임
20 . 순환호출에서는 순환호출을 할때마다 문제의 크기가 작아져야 한다.
(1) 팩토리얼 계산 문제에서 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?
답: n의 값이 작아진다.
(2) 하노이의 탑에서 순환호출이 일어날 때마다 문제의 어떻게 작아지는가?
답: 하나의 원판을 이동시키고 나머지 원판에 대해서 순환호출이 일어나며 작아진다.
'C언어로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| [c언어로 쉽게 풀어쓴 자료구조] - 연습 문제 3장 정답 (0) | 2023.09.17 |
|---|