게시판 인덱스

 
 FAQFAQ   검색검색   멤버리스트멤버리스트   사용자 그룹사용자 그룹   사용자 등록하기사용자 등록하기 
 개인 정보개인 정보   비공개 메시지를 확인하려면 로그인하십시오비공개 메시지를 확인하려면 로그인하십시오   로그인로그인 

재귀함수가 끝나는 것인지 확인하는 것에 대한 질문입니다.

 
글 쓰기   답변 달기     게시판 인덱스 -> 4190.210 Principles of Programming (Fall 2013)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
김성학



가입: 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년10월15일 23:39    주제: 인용과 함께 답변

https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=3946&sid=f633f4831dcff6ff3a4fe2a03260504a
위로
사용자 정보 보기 비밀 메시지 보내기
김성학



가입: 2013년 9월 4일
올린 글: 26

올리기올려짐: 2013년10월15일 23:54    주제: 인용과 함께 답변

경인 고마워!! Razz
위로
사용자 정보 보기 비밀 메시지 보내기
이전 글 표시:   
글 쓰기   답변 달기     게시판 인덱스 -> 4190.210 Principles of Programming (Fall 2013) 시간대: GMT + 9 시간(한국)
페이지 11

 
건너뛰기:  
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다


Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay