이전 주제 보기 :: 다음 주제 보기 |
글쓴이 |
메시지 |
구자민
가입: 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로 만들 수 있는 것들까지 처리해 주려면 |
상당히 어려워 집니다. 적용 범위를 정하기조차 어렵습니다.
우선은 문제에 나와 있는 함수를 어떻게 처리할지 부터 고민하는 것이 좋을 듯 합니다. |
|
위로 |
|
|
|