C언어로 쉽게 풀어쓴 자료구조 2장 연습문제 솔루션

소개글

C언어로 쉽게 풀어쓴 자료구조 3판 2장 솔루션입니다.
1~21

목차

없음

본문내용

1. 팩토리얼을 계산하는 순환호출 함수 factorial에서 매개 변수로 5을 주었다면 최대 몇 개의 factorial 함수의 활성 레코드가 동시에 존재할 수 있는가?
//활성 레코드 : 함수를 위한 시스템에서의 공간
factorial(5)을 호출하면 factorial(5)을 수행하는 도중에 factorial(4)를 호출하게 되고 factorial(4)는 다시 factorial(3)을 호출하게 된다. 이렇게 반복하여 factorial(1)까지 호출을 하게 되면 활성레코드는 동시에 최대 5개까지 존재할 수 있다.
2. 순환 호출을 하였을 경우에 활성 레코드 들이 저장되는 위치는 어디인가?
시스템 스택에 활성 레코드들이 쌓이게 되므로 답은 (4)번 스택이다.
3. 다음 중 활성 레코드에 저장되지 않는 것은 무엇인가.
함수의 호출에서 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역변수를 스택으로부터 할당 받는다. 따라서 (4)번의 순환호출의 순차번호는 저장되지 않는다.
4. 하나의 함수가 호출할 수 있는 순환호출의 개수는?
함수를 무한히 호출할 경우에는 오류가 발생하게 된다. 따라서 스택이 허용하는 한도에서 순환호출을 할 수 있다. 답(3)번

<중 략>

20. 순환호출에서는 순환호출을 할 때마다 문제의 크기가 작아져야 한다.
(1) 팩토리얼 계산 문제에서 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?
값을 반환할 때 n*factorial(n-1)을 순환호출 하면서 작아진다.
(2) 하노이 탑에서 순환호출이 일어날 때마다 문제의 어떻게 작아지는가?
n개의 원판이 쌓여 있을 때 위에 쌓여 있는 n-1개의 원판을 다른 곳으로 옮긴 다음 제일 밑에 있는 원판을 옮긴다. 옮긴 n-1개의 원판에서 마지막 원판을 뺀 나머지 원판들을 옮기면서 작아진다.

참고 자료

없음