게시판 인덱스

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

tail recursive에 대한 질문입니다.

 
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.310 Programming Languages (Fall 2007)
이전 주제 보기 :: 다음 주제 보기  
글쓴이 메시지
구자민



가입: 2007년 9월 21일
올린 글: 14

올리기올려짐: 2007년11월3일 12:38    주제: tail recursive에 대한 질문입니다. 인용과 함께 답변

https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=708

작년 홈페이지의 tail recursive에 대한 글입니다.

위 글을 보면,
코드:
let x := 0
in
   let procedure rtest(x) =
      let result := 0
      in
         if ( x = 0 )
            then
               result := 1
            else
               result := call rtest(x-1)
         end;
         result
      end
   in
      read x;
      write call rtest(x)
   end
end

도 tail-recursive라고 되어 있습니다. 물론 의미상으로는 tail recursive 입니다만, ASSIGN이 들어가기 때문에 tail recursive 형식이 아니라고 말할 수 있을 것 같습니다.

작년의 K-에는 아마 if문이 무조건 unit을 리턴하도록 되어 있었던 것 같습니다. (밑의 댓글을 통한 추측입니다.) 그래서 위와 같은 형식을 허용했던 것 같은데, 이번에는 if 등 대부분의 함수가 return 값을 제공합니다. 그러면 위와 같은 형태를 tail recursive라고 정의할 필요는 없을 것 같습니다.

만약 위와 같은 형태도 tail recursive라고 한다면, ASSIGN은 예외라는 단서가 필요하고, 그 뒤의 값까지 살펴봐야 되는 상황이 생길 것 같습니다. 이는 보통recursive를 tail recursive로 변형시켜야 되는, 좀 더 어려운 문제가 될 거 같습니다.

요약하면,
이번의 'tail recursive'문제는, 순수하게 'return CALLV(...)' 또는 'return CALLR(...)' 를 수행하는 함수에 대해서만 처리하면 되는 걸까요?
위로
사용자 정보 보기 비밀 메시지 보내기
남기웅



가입: 2007년 10월 10일
올린 글: 17

올리기올려짐: 2007년11월4일 11:51    주제: 인용과 함께 답변

저도 참 궁금합니다만...
코드 자체가 tail-recursive 인 것은 간단하게 처리할 수 있지만,
코드를 약간 변형시킴으로써 tail-recursive로 만들 수 있는 것들까지 처리해 주려면 상당히 어려워 보이네요. 실제 자바나 C의 컴파일러에서 이런 형태의 최적화를 한다는 것을 본 것 같은데...
대단히 가치있고 도전해 볼 만한 과제인 것 같은데, 일반적인 해법을 찾을 엄두가 안나네요.
위로
사용자 정보 보기 비밀 메시지 보내기 이메일 보내기
정영범



가입: 2005년 9월 5일
올린 글: 167

올리기올려짐: 2007년11월5일 12:31    주제: 인용과 함께 답변

인용:
코드를 약간 변형시킴으로써 tail-recursive로 만들 수 있는 것들까지 처리해 주려면

상당히 어려워 집니다. Rolling Eyes 적용 범위를 정하기조차 어렵습니다.

우선은 문제에 나와 있는 함수를 어떻게 처리할지 부터 고민하는 것이 좋을 듯 합니다.
위로
사용자 정보 보기 비밀 메시지 보내기 이메일 보내기 글 올린이의 웹사이트 방문
이전 글 표시:   
이 게시판은 잠겼으므로 글을 올리거나, 답변을 하거나 수정을 할 수 없습니다   이 주제는 잠겼으므로 답변을 하거나 수정을 할 수 없습니다     게시판 인덱스 -> 4190.310 Programming Languages (Fall 2007) 시간대: GMT + 9 시간(한국)
페이지 11

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


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