여섯째, 재귀 및 역 추적 알고리즘

컴퓨터 분야에서는 많은 문제를 재귀 알고리즘으로 해결할 수 있다. 재귀에서 가장 일반적인 방법은 역추적이다. 우리가 문제를 상세히 분석할 때, 이런 문제는 본질적으로 나무라는 것을 알 수 있다.

재귀 알고리즘의 본질은 원래 문제를 더 작은 동일한 문제로 변환하고 해결하는 것입니다. 일반적으로 다음 두 가지 사항에 유의하십시오.

1, 재귀적으로 종료되는 조건. 재귀 알고리즘에서 가장 기본적이고 간단한 문제에 해당합니다.

2. 재귀적 프로세스. 재귀 프로세스는 원래 문제를 한 번에 한 단계씩 더 작은 동일한 문제로 밀어야 합니다. 작을수록 하위 문제를 쉽게 해결할 수 있습니다. 글을 쓸 때 재귀 공식을 찾을 수 있다. 이 과정에서 재귀 함수의 의미를 철저히 이해해야 한다. 이 함수의 입/출력이 무엇인지 분명히 하면 훨씬 더 명확해질 것이다.

이 재귀 공식으로 인해 재귀의 종료 조건이 우리가 알고 있는 f(0) 와 f( 1) 라는 것을 쉽게 알 수 있습니다. F(0) 과 f( 1) 를 사용하여 f(n) 까지 f(3) 를 계속 파생할 수 있습니다.

하지만 이제 우리는 재귀 알고리즘의 아이디어로만 이 문제를 해결합니다.

체인 테이블, 트리 및 그래프와 같은 일반적인 데이터 구조에는 자연스러운 재귀 구조가 있습니다. 체인 테이블은 선형 구조이기 때문에 일반적으로 직접 순환 순회를 통해 문제를 해결할 수 있지만 여기서는 LeetCode 위의 문제를 재귀적으로 해결합니다.

LeetCode 203 링크 목록 요소를 제거합니다.

해결: 연결된 목록의 구조는 한 노드가 이 짧은 연결된 목록을 연결하여 마지막 노드가 None 이 될 때까지 읽을 수 있도록 이해할 수 있습니다. 그러면 현재 재귀적 종료 조건은 None 을 가리키고 None 을 반환하는 것입니다.

재귀 알고리즘을 깊이 이해한 후, 우리는 역추적 방법을 배우기 시작했다. LeetCode 위의 몇 가지 질문을 통해 재귀와 역추적 응용에 대해 자세히 살펴보겠습니다.

지속적인 업데이트 ...

데이터 구조 및 알고리즘 시리즈 블로그:

첫째, 데이터 구조 및 알고리즘 개요

둘째, LeetCode 의 전형적인 주제 정리 및 분석

셋째, 링크 목록 및 leet 코드 문제

넷째, 스택 및 대기열 (Stack and Queue

동사 (verb 의 약어) 트리

여섯째, 재귀 및 역 추적 알고리즘

일곱. 동적 계획

여덟, 정렬 및 검색

아홉, 해시 테이블

참조 데이터

1,

2,

3,