흔한1인
20
2021-11-25 19:47:49
2
108

재귀 비재귀 변환에 대해


안녕하세요, 요즘 재귀함수에 푹 빠져사는 초심자입니다. 슬슬 재귀에 익숙해지고, 간단한 재귀함수는 스택이나 for문을 이용해서 비재귀로 변환하는법도 대략은 알겠는데, 이게 재귀함수가 조금만 복잡해져도(예 : 하노이의 탑) 재귀로는 쉽게 구현하겠는데, 이걸 비재귀로 바꾸려니 정말 답답하고 안풀리네요... 

혹시라도 이런 복잡한 재귀함수를 쉽게 비재귀로 바꾸는 법이 있을까요? 그 전에, 복잡한 재귀함수를 비재귀함수로 바꾸는 작업이 중요하고 꼭 필요한, 즉 알고리즘 문제해결을 위해 제가 필연적으로 익숙해져야 할 작업이기는 한가요? 제가 너무 쓸데없는것에 노력을 쏟고 있는 거라면, 고수님들 조언 듣고 빠르게 다음 공부를 하려고 질문드립니다.. 많은 조언 부탁드려요.

0
  • 답변 2

  • Dierslair
    5k
    2021-11-25 19:53:48

    알고리즘 저도 개뿔 잘 모르는데요 코틀린 공부하면서 'tailrec' 이라는 키워드(재귀 함수를 비재귀 함수로 컴파일러가 알아서 바꿔줌)가 있어 잠깐 본 결과 '스택도 자체로 메모리를 차지하기 때문에 재귀를 while, for 로 변환해서 해결하는 것은 성능 향상에 도움이 된다.' 이런 설명이 있더라구요. 재귀는 사람 기준으로 문제를 해결하는데 도움이 되지만 너무 깊은 재귀 호출은 성능을 악화시킨다는 문맥인 것 같네요.

    아마도 그런 관점에서 재귀를 비재귀로 바꾸는 연습을 하는것은 작성자님 코드 스킬 향상에 도움이 되리라 생각합니다.

  • monotonicity
    235
    2021-11-25 21:24:49

    재귀 함수도 결국 스택을 이용하는것이기 때문에 비재귀로 구현할때도 똑같이 스택 자료구조를 쓰면 됩니다. 재귀 함수 콜 -> 스택에 추가, 재귀 함수 리턴 -> 스택을 팝 이런식으로요. 물론 이런 과정이 의미가 있냐라고 물으신다면 없다고 봅니다. 그냥 메모리가 쓰이는 공간이 스택에서 힙으로 바뀐것이기 때문에..

    한번쯤은 해볼만한 연습문제이지만 딱 그 정도라고 생각합니다. 

  • 로그인을 하시면 답변을 등록할 수 있습니다.