이전 주제 보기 :: 다음 주제 보기 |
글쓴이 |
메시지 |
강지훈
가입: 2008년 9월 2일 올린 글: 291 위치: 302동 312-2호
|
올려짐: 2013년10월11일 14:37 주제: [HW4] HW4-1에서 트리를 이용한 프로그램이 끝나는지 확인할 때 |
|
|
다음과 같은 함수에 대해서는, 끝나는지 확인하지 않아도 좋습니다.
코드: | (define (tree-size tree)
(if (isleaf? tree) 1
(+ 1 (tree-size (leftsub tree)) (tree-size (rightsub tree))))) |
즉 위 함수에 한정해서는
코드: | (define (tree-size tree)
(printf "decreasing: ~s~n" ???)
(if (isleaf? tree) 1
(+ 1 (tree-size (leftsub tree)) (tree-size (rightsub tree))))) |
??? 부분을 알아낼 필요가 없습니다.
감사합니다. _________________ 강지훈
프로그래밍의 원리 조교
Jeehoon Kang
TA, Principles of Programming
강지훈 가 2013년11월13일 1:09에 수정함, 총 1 번 수정됨 |
|
위로 |
|
|
유재민
가입: 2013년 10월 2일 올린 글: 11
|
올려짐: 2013년10월13일 4:49 주제: 음 |
|
|
트리의 사이즈를 구하는 함수 뿐만 아니라, recursion의 다음 단계에서 사용하는 인자가 subtree밖에 없는 재귀함수에서는 끝나는 것을 보일 필요가 없다는 것인가요? 제 함수가 그런 식으로 짜여져서 실제로 구동할 때는 상위 노드에서부터 dfs 방식으로 노드들을 경유하거든요. |
|
위로 |
|
|
조성근
가입: 2009년 9월 14일 올린 글: 283
|
올려짐: 2013년10월14일 12:38 주제: |
|
|
숙제4-1에서 "재귀함수의 끝남"을 보이는 방법에 대해 추가 공지합니다. 이미 숙제를 제출하신 분들은 제출된 숙제를 그대로 두시고, 앞으로 숙제를 제출하시는 분들은 가급적 아래의 방법을 사용하시길 바랍니다. 이것은 추천사항입니다.
재귀함수가 끝남을 보이기 위해서 다음 세 가지를 보일 필요가 있습니다.
- 재귀함수의 인자에 대한 어떤 순서 정의.
- 1에서 정의한 순서에 의한 감소하는 체인이 임의의 인자에서 시작했을 때 항상 유한함.
- 모든 재귀 호출에 대해 인자가 감소함.
예) 아래와 같은 factorial 함수가 있을 때,
코드: | (define (fac n)
(if (eq? n 0) 1
(* n (fac (- n 1))))) |
- 정수 n에 대한 순서 ">>"의 정의.
n >> m iff n > m and m >= 0.
- 체인의 유한함.
Forall n >= 0: n >> n' >> ... >> 0 is finite.
- 인자의 감소.
n >> (- n 1)
다음과 같이 답안을 작성하시기 바랍니다.
코드: | (define (fac n)
(if (eq? n 0) 1
(* n (fac (- n 1)))))
; 1. n >> m iff n > m and m >= 0.
; 2. Forall n >= 0: n >> n' >> ... >> 0 is finite.
; 3. n >> (- n 1) |
(참고1) tree나 list의 size 표현을 위해서 |tree|, |list|를 사용하셔도 좋습니다.
(참고2) 이 숙제는 조교들이 직접 눈으로 채점할 것이니 형식에 크게 구애받지 않으셔도 좋습니다.
유재인 님,
유재인 씀: | 트리의 사이즈를 구하는 함수 뿐만 아니라, recursion의 다음 단계에서 사용하는 인자가 subtree밖에 없는 재귀함수에서는 끝나는 것을 보일 필요가 없다는 것인가요? |
아닙니다. 트리의 사이즈를 구하는 함수만 끝나는 것을 보일 필요가 없다는 것입니다. |
|
위로 |
|
|
|