반복문 안에 들어가는 재귀호출의 분석요령을 알고싶습니다.

  • gksqls2476
    gksqls2476

    알고리즘 문제 해결 전략이라는 책을 공부하면서,
    재귀호출이 이곳 저곳에서 굉장히 많이 나왔습니다.
    근데 여태껏 봐왔던 프로그램은 한 재귀함수 안에 많아야 재귀호출이 두세번 정도
    나오는 프로그램이 전부였었는데 책을 공부하다보니깐
    완전탐색, 분할정복, 동적계획법등의 알고리즘 소스에 거의 대부분 반복문안에 재귀호출이
    들어가 있는 경우가 상당히 많았습니다.
    재귀의 수가 적으면 재귀나무를 그려서 분석을 해보겠는데, 너무 많아서 손으로 하기도
    조금 벅찹니다. 신분 상 컴퓨터를 저녁에 밖에 못써서 그전엔 손으로 코딩하고 분석 해야하는데
    반복문 안에 재귀호출이 들어가는 재귀함수를 잘 분석하는 요령이 있을까요?
    새삼 재귀호출의 어려움을 깨닫습니다.


    5년 전
2개의 댓글이 있습니다.
  • hrst
    hrst

    recursion을 분석할때, 실제 숫자를 입력받은 게 아니라 n이라는 변수를 받았다고 생각하면 이해가 쉬울 거에요.

    예를 들면 fibonacci 수열을 계산하는 함수 f(n)이 있다고 한다면, f(n)에서 f(n-1)과 f(n-2)를 뻗어나가는 트리 형식으로 그림을 그릴 수가 있겠죠. f(n-1)에서는 다시 f(n-1-1)과 f(n-1-2)를 이어 그리고, 이걸 반복하시면 결국 f(n-1-1-1...-1) = f(1)에 도달할 수 있으니까요. 다시 말해 가능한 한 일반항을 써서 코드를 분석하시는 것도 한 방법일 것 같습니다.


    5년 전 link
  • gksqls2476
    gksqls2476

    ID: BOGGLE 같은 문제에서 브루트 포스를 이용할때 반복안에 재귀가 너무 힘듭니다. ㅠㅠㅠ


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.