Recursive 함수를 stack 을 사용하지 않고 푸는 방법이 있을까요?
글쓴이: Yoons / 작성시간: 수, 2007/09/12 - 5:03오후
Ackermann 함수를 잠시 보게 되었는데..
Recursive function 의 대표적인 예... 로 예제로 나온걸 보았습니다.
non-recursive function 을 짜는 방법을 고민하던 중에..
주변에서 stack 을 대신하여 다중 for문을 이용하여 푸는 방법이 있다고 하던데..
과연 그런 방법이 있을까요..?
// 뱀다리..
뿐 아니라 array 를 이용하는 방법, 등등..
주변에서는 말만 많더군요.. 쳇..;;
그리고 Ackermann 을 알고픈 분은 wiki 에서 찾으시면... (영문)
다양한 언어의 Ackermann 과 C based non-recursive Ackermann 을 볼 수도 있더군요..
Forums:
recursion을 계속하면
recursion을 계속하면 함수를 계속 호출하게되고 당연히 스택에 계속 쌓입니다...
이런걸 벗어나기위해서 for문으로 대치하는 거를 말씀하시는듯합니다.
recursion은 결국 반복해서 함수를 호출하는걸로 단순하게 생각할수 있고 '반복'이란거에 포커스를 맞추면 당연히 loop문으로 대치할수 있습니다
재귀호출시의 종료 조건을 반복문의 종료조건으로 두고 계산하시면 되겠죠 배열은 아마 for문의 계산결과를 배열에 저장하는걸 말하는건 아닐지.. 싶습니다만..
결론은 재귀호출은 반복문으로 변경 가능합니다..
스택은 계산값 저장을 위한건지 아니면 함수호출시 소모되는 스택을 말씀하시는건지 모르겠습니다. 저도 말만하고 끝난거같긴하지만 이해 안가시면 간단한 재귀 문을 반복문으로 변경해 보시면 아실듯 합니다
//뱀다리...
써넣고보니 이미 찾아보신 부분의 코드들에서 다 구현되어 있을법합니다만.....;; 물론 제가 찾아본것은 Ackermann function만입니다만.. 위키피디아에서요..
기존의 연산값을 가져와야하는부분이야 배열에 저장하시면 되겠구요.. 몇번째 값을 가져오실것 아니라면 그냥 바로 이전결과만 저장하면 되지 않나요..
저는 왠만하면 추천하지 않습니다.
상품으로서의 code에서는 recursion 제거가 필요하다고 주장하시는 분들도 있지만
그 code는 너무 비직관적이 되기 마련입니다.
또한 stack 동장을 배열같은데다가 수동으로 작업을 해줘야 할 가능성이 큽니다.
확실히 성능은 좋아질 지도 모릅니다.
저도 예전에 8 Queen 이나 하노이의 탑을 반복으로 풀어본 적이 있는데요.
수동의 stack 동작과 함께 loop을 쓰는 것에 compiler 최적화를 하면 재귀호출의 두배정도의 성능이 나오더군요.
(입출력은 제외한 경우입니다.)
하지만 가장 큰 문제는 함수 내에서 재귀호출이 몇번 호출되느냐에 따라 stack 동작의 구체적 방식이
달라지기 때문에 정형화된 recursion -> loop with array 가 없다는 것입니다.
혹시 아시는 분 있다면 저도 꼭 부탁드립니다.
이 문제는 저도 한 때 굉장히 고심했던 문제입니다.
단지 stack 동작을
단지 stack 동작을 emulation하기 위한 용도로 배열을 사용한다면 그 성능은 재귀 호출과 별반 다를 바 없을 테고, 말씀하신대로 stack을 흉내내기도 까다로울 수 있죠. Ackermann 함수 등이 문제되는 이유는 재귀가 두 갈래 이상이어서 했던 계산을 또 하는 바람에 원래 필요한 계산 시간보다 (worst case) exponential배로 큰 시간이 든다는 점입니다. 따라서 배열을 hash map 등으로 구현하여 윗분이 언급한 것처럼 이전 계산값을 저장하는 것이 맞겠죠. Ackermann 함수처럼 side effect가 없고 최종 값을 얻기만 하면 된다면 일반화하긴 쉬울텐데요.
F(n) = G ( F(n-a), F(n-b), F(n-c), ...)와 같은 재귀 형식을 iteration을 이용하여 구현한다면 (F의 인자는 자연수, a, b, c 등도 자연수)HashMap memo; // 어떤 v에 대해 F(v)가 미리 계산되어 있으면 memo[v] = F(v) 이다. 초기값 memo[1], memo[2] 등 몇개는 미리 저장되어 있다.
F(n) =
1. memo[n]이 존재하면 끝
2. memo[p]는 존재하나 memo[p+1]이 아직 계산되지 않은 1~n 사이의 수 p를 찾는다.
3. memo[p+1]부터 memo[n]까지 loop을 돌며 계산한다. 이때 p+1~n 사이의 수 i에 대해 memo[i] = G (memo[i-a], memo[i-b], memo[i-c], ..)로 계산하면 된다.
call stack 을 이용하지
call stack 을 이용하지 않고, 사용자가 stack 을 만들어 사용함으로 recursive call 을 없앨 수 있습니다.
stdcall 의 경우 함수가 호출되게 되면, arguments 와 pc 가 call stack 에 쌓이게 됩니다. 또한 지역 변수 또한 stack 에 쌓이게 되는데, call stack 을 사용하지 않고, 꼭 필요한 정보만을 자신이 관리하는 (효율적인) stack 에 쌓게 되면 조금 더 가벼운 구현이 가능하겠죠. 단 아주 잘짜야 할겁니다. ;) 요새 컴파일러들 굉장히 똑똑하거든요.
인자가 적다면 (2개이하) fastcall 을 사용할 경우 call stack 을 사용하지 않게 되서, recursive call 이 상당히 빠르게 구현될 수 있습니다. 함수의 내부 변수가 많다면 register 의 일부가 stack 에 백업되게 될테니 이런 부분에선 non-recursion call 을 사용하는게 조금 유리할 지 모르겠네요. (caller save 일 경우야 모든 레지스터가 백업되겠지만, callee-save 라면 일부 레지스터 만을 백업하겠죠. 단 -O0 옵션이라면 변수를 레지스터로 매핑하지 않으므로 딴세상 이야기)
뭐 결국 원리를 알고, 문제점과 자신이 사용하는 툴(언어?)들이 지원하는 규약들을 상세하게 알고 있다면 non-recursive call 을 사용하는것이나 recursive call 을 사용하는 것이나 다 충분히 빠르고 효율적으로 만들 수 있습니다.
--
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
오랫동안 꿈을 그리는 사람은 그 꿈을 닮아간다...
http://mytears.org ~(~_~)~
나 한줄기 바람처럼..
Memoization으로
Memoization으로 recursion을 없앨 수 있다면
dynamic programming으로 해결 가능하겠지요.
하지만 일반적인 방법은 없을 것 같습니다. -_-a
되는 문제가 있고, 안되는 문제가 있겠지요.
댓글 달기