본문 바로가기

재귀

프로그래밍/알고리즘 2021. 1. 23. DFS - 깊이 우선 탐색 (C#으로 길 찾기 구현) - Depth First Search의 약자 - 현재 정점(노드)에서 간선으로 연결된 정점중 가장 깊은 정점까지 탐색하고 목표 정점이 없으면 이전 정점으로 돌아가 간선으로 연결된 다른 정점으로 또다시 탐색한다. - 위 방법을 반복하면서 정점들을 순회하게 된다. - DFS와 대조되는 BFS (너비 우선 탐색)도 있다. - 일반적으로 재귀호출로 구현하는 방법과 스택으로 구현하는 방법이 있다. using System; using System.Collections.Generic; class Program { static void Main(string[] args) { MapController mapController = new MapController(); // 길 체크 플래그를 초기화해준다. mapContro..

프로그래밍/기본기ㆍ자료구조 2020. 4. 28. 재귀호출 재귀호출이란? 특정 조건을 만족할 때까지 자기 자신을 반복해서 호출하는 것. 일반적으로는 가독성이 좋아진다는 장점이 있다. 반복문으로 구현하면 복잡해지는 코드가 재귀호출로 구현 시 간략해질 수 있다. 스택 메모리에 쌓이고 그 스택메모리가 빌드나 제한된 메모리 이상으로 초과하면 오버플로우가발생한다. 스택에 함수가 호출된 주소가 저장되어 있기 때문에 호출 횟수가 많아지면 실행 속도가 느려지는 단점이있다. 퀵정렬이나 길찾기 알고리즘에 많이 사용되었고 A스타, XX, XX 등이 있다. 꼬리재귀 스택에 쌓지 않는 재귀호출. 코드상으로는 재귀함수지만 컴파일러가 반복문으로 최적화하여 반복문처럼 된다. 컴파일 옵션에서 꼬리재귀 최적화를 설정할 수 있다.(불가능한 환경도 있다) 리턴할..

이전 1 다음

티스토리툴바