이전 주제 보기 :: 다음 주제 보기 |
글쓴이 |
메시지 |
김성학
가입: 2013년 9월 4일 올린 글: 26
|
올려짐: 2013년10월15일 18:19 주제: 재귀함수가 끝나는 것인지 확인하는 것에 대한 질문입니다. |
|
|
어떤 단어 str이 tree에 존재하는지를 확인하기 위한 함수 intree를 다음과 같이 작성하였습니다.
코드: | (define (intree? str tree) ; string * tree -> bool
(cond [(isleaf? tree) (equal? str (leafstr tree))]
[(istree? tree) (or (intree? str (leftsub tree)) (intree? str (rightsub tree)))])
) |
이 함수가 끝나는 것인지를 확인하기 위해 (printf "decreasing: ~s~n" (tree-size tree))를 삽입하였는데요,
한 번 전체 함수가 실행될 때 호출되는 (intree? str (leftsub tree))와 (intree? str (rightsub tree))의 (tree-size tree))가 감소하는 것은 명확함에도 불구하고
두 번 재귀하는 바람에 decreasing하는지 화면으로 확인하기가 어렵습니다ㅜ
recursion 횟수의 유한함은 따로 증명할 수 있을 것 같은데, 이런 경우 재귀함수가 끝나는 것으로 인정이 될까요?
항상 수고하십니다! |
|
위로 |
|
|
박준모2
가입: 2013년 10월 14일 올린 글: 8
|
올려짐: 2013년10월15일 20:40 주제: |
|
|
dfs하는 작업에서는 줄어드는지 검사할 필요가 없는걸로 알고있어요 |
|
위로 |
|
|
김성학
가입: 2013년 9월 4일 올린 글: 26
|
올려짐: 2013년10월15일 20:59 주제: |
|
|
조교님께서 끈적이에
인용: | 유재인 님,
유재인 씀:
트리의 사이즈를 구하는 함수 뿐만 아니라, recursion의 다음 단계에서 사용하는 인자가 subtree밖에 없는 재귀함수에서는 끝나는 것을 보일 필요가 없다는 것인가요?
아닙니다. 트리의 사이즈를 구하는 함수만 끝나는 것을 보일 필요가 없다는 것입니다. |
라고 쓰신 것으로 보아 그렇지 않은 것 같아요..?! |
|
위로 |
|
|
유경인
가입: 2013년 9월 9일 올린 글: 29
|
|
위로 |
|
|
김성학
가입: 2013년 9월 4일 올린 글: 26
|
올려짐: 2013년10월15일 23:54 주제: |
|
|
경인 고마워!! |
|
위로 |
|
|
|