정렬 된 이중 연결 목록 삽입 재귀

Question

데이터 구조와 재귀 개념이 생소했습니다. 왜이 개념에서 재귀를 사용할 수 있었는지 이해하기 위해 고심하고 있습니다. 나는이 포럼을이 포럼에서 발견했기 때문에 나는 이것의 개념을 정말로 이해할 수 없었다. 어떤 사람이 반복 단계를 설명 할 수 있다면 간단하게 2 1 3 4의 경우, 그것은 내 대신에 크게 평가 될 것입니다. https://www.hackerrank.com/challenges/insert-a-node-into-a-sorted-doubly-linked-list

Node SortedInsert(Node head,int data) { 
    Node n = new Node(); 
    n.data = data; 
    if (head == null) { 
     return n; 
    } 
    else if (data <= head.data) { 
     n.next = head; 
     head.prev = n; 
     return n; 
    } 
    else { 
     Node rest = SortedInsert(head.next, data); 
     head.next = rest; 
     rest.prev = head; 
     return head; 
    } 
} 

Answer 1

재귀가 : 재귀 함수는 자신을 호출 의미 여기

해커 순위에 대한 링크입니다. 이것은 여러 상태, 대개 많은 수의 상태를 저장하고이를 역순으로 검색해야하는 알고리즘의 상태 정보를 저장하는 간단한 방법으로 사용됩니다. (프로그램 객체를 저장하기 위해 Stack 객체를 사용하는 것과 같이,보다 전문적이고 메모리 문제가 적은 대체 기술이 있습니다.)

이 예제는 좋지 않지만 일반적인 재귀 소개입니다. 예, 재귀를 사용하여 연결된 목록을 반복 할 수 있지만 절대적으로 이유가 없습니다. 루프가 더 적절할 것입니다. 순전히 재귀가 어떻게 작동하는지 보여주기위한 것입니다. 그래서 "왜?"라는 질문에 대답하십시오. 그것은 단순히 개념을 배우고 나중에 실제로는 다른 알고리즘에서 사용할 수 있기 때문입니다.

재귀는 연결된 목록 대신 트리가있는 경우에 유용합니다. 각 노드는 여러 다른 노드를 가리 킵니다. 이 경우 링크 된 노드 중 하나를 탐색하여 다음 노드로 돌아가서 이동할 수 있도록 상태 (현재 노드와 마지막으로 호출 한 노드)를 저장해야합니다.

당신은 또한 "어떻게"물었습니다. 함수가 자신을 호출하면 모든 변수가 (프로그램 스택 상에) 저장되고 새로운 변수는 다음 반복을 위해 생성됩니다. 그런 다음 호출이 돌아 오면 호출 된 위치로 돌아가고 이전 변수 세트가로드됩니다. 이는 매번 변수의 동일한 사본이 매번 사용되는 "점프"또는 일종의 루프와 매우 다릅니다. 재귀를 사용하면 호출 할 때마다 모든 로컬 변수의 새로운 사본이 있습니다. 이는 변경되지 않는 예제의 "데이터"변수에서도 마찬가지입니다 (따라서 비효율적입니다).