>

최근에 나는 두 곳의 다른 곳에서 "학교에서의 재귀에 대해 배웠지 만 그 이후로 그것을 사용하지 않았거나 그 필요성을 느꼈다"는 내용의 주석을 보았습니다. (재귀는 특정 그룹의 프로그래머들 사이에서 "책 학습"의 대표적인 예인 것 같습니다.)

자바와 루비와 같은 명령형 언어에서는 일반적으로 반복 오버플로를 피하고 부분적으로 스택 오버플로의 위험이 있기 때문에 재귀를 피하는 것이 사실입니다. 익숙합니다.

이제는 엄밀히 말하면 그러한 언어에서는 "필요한"재귀 사용이 없다는 것을 알고 있습니다. 아무리 복잡한 일이 있어도 항상 재귀를 반복으로 대체 할 수 있습니다. 여기서 "필요"하여 다음에 대해 이야기하고 있습니다.

귀하가 재귀를 사용했던 반복 (명확성, 효율성 또는 다른 이유로)보다 재귀가 훨씬 더 나은 언어에서 특정 코드의 예를 생각할 수 있습니까? 반복으로 변환하면 큰 손실이 있었을 것입니다 ?

재귀 적으로 걷는 나무는 답에서 여러 번 언급되었습니다. 라이브러리 정의 반복자를 사용하는 것보다 재귀를 더 좋게 만든 특정 용도에 대해 정확히 무엇입니까?

[1] : 예, 이것도 객체 지향 언어라는 것을 알고 있습니다. 그러나이 질문과 직접 ​​관련이 없습니다.

  • 답변 # 1

    "필요한"재귀 사용은 없습니다. 모든 재귀 알고리즘을 반복 알고리즘으로 변환 할 수 있습니다. 필요한 스택을 기억하는 것 같지만 내 머리 꼭대기에서 정확한 구성을 기억할 수는 없습니다.

    실제로 말해서, 만약 당신이 다음과 같은 것들에 대해 재귀를 사용하지 않는다면 (비록 명령적인 언어에서도) 약간 화를냅니다 :

    <올>

    트리 순회

    그래프

    Lexing/Parsing

    정렬

  • 답변 # 2

    예를 들어 어떤 종류의 나무 구조라도 걸을 때

    재귀 강하 파서를 사용하여 문법 파싱

    DOM 트리 걷기 (예 : 파싱 된 HTML 또는 XML)

    또한 객체 멤버의 toString ()을 호출하는 모든 toString () 메서드도 재귀적인 것으로 간주 될 수 있습니다. 모든 객체 직렬화 알고리즘은 재귀 적입니다.

  • 답변 # 3

    제 작업에서 재귀는 알고리즘에 거의 사용되지 않습니다. 계승 등과 같은 것은 간단한 루프를 사용하여 훨씬 더 읽기 쉽고 효율적으로 해결됩니다. 그것이 표시되면 일반적으로 재귀 적 인 일부 데이터를 처리하기 때문입니다. 예를 들어, 트리 구조의 노드는 재귀 적으로 처리 될 수 있습니다.

    예를 들어, 이진 트리의 노드를 이동하는 프로그램을 작성하는 경우 하나의 노드를 처리하고 각 하위 노드를 처리하기 위해 자체를 호출하는 함수를 작성할 수 있습니다. 이것은 각 하위 노드에 대해 서로 다른 모든 상태를 유지하려고 시도하는 것보다 효과적입니다.

  • 답변 # 4

    가장 잘 알려진 예는 아마도 C.A.R에서 개발 한 퀵 정렬 알고리즘 일 것입니다. Hoare.

    또 다른 예는 파일을 찾기 위해 디렉토리 트리를 탐색하는 것입니다.

  • 답변 # 5

    제 생각에 재귀 알고리즘은 데이터 구조도 재귀적일 때 자연스럽게 적합합니다.

    def traverse(node, function):
        function(this)
        for each childnode in children:
            traverse(childnode, function)
    
    

    반복적으로 쓰고 싶은 이유를 알 수 없습니다.

  • 이전 하위 모듈로 git 저장소의 이름을 바꾸려면 어떻게해야합니까?
  • 다음 c++ - gdb로 행동 이해하기