데이터 구조의 재귀: 작동 방식, 유형 및 사용 시기
게시 됨: 2020-05-22데이터 구조에서 재귀의 정의부터 시작하겠습니다. 우리는 나중에 다양한 유형의 재귀와 재귀를 사용하여 여러 문제를 해결하는 방법에 대해 논의할 것입니다.
목차
재귀 란 무엇입니까?
간단히 말해서 재귀는 문제 해결이며, 경우에 따라 매우 특별하고 배타적인 속성을 가진 프로그래밍 기술입니다. 재귀에서 함수나 메서드는 문제를 해결하기 위해 자신을 호출할 수 있습니다. 재귀 과정은 문제를 자체적으로 더 작은 종류로 바꾸어 문제를 해결하는 것을 포함합니다.
함수가 자신을 호출하는 프로세스는 직접적으로나 간접적으로 발생할 수 있습니다. 이러한 호출의 차이로 인해 다양한 유형의 재귀가 발생합니다. 이에 대해서는 잠시 후에 설명하겠습니다. 재귀를 사용하여 해결할 수 있는 문제에는 그래프의 DFS, 하노이의 타워, 다양한 유형의 트리 탐색 등이 있습니다. 재귀 및 기타 데이터 과학 개념에 대해 알아보려면 IIIT-B의 데이터 과학 온라인 과정을 확인하십시오.
읽기: 13가지 흥미로운 데이터 구조 프로젝트 아이디어
재귀는 어떻게 작동합니까?
재귀의 개념은 문제가 하나 또는 더 작은 버전으로 표현된다면 훨씬 쉽고 더 짧은 시간에 해결될 수 있다는 아이디어에 기반을 두고 있습니다. 재귀를 중지하기 위해 기본 조건을 추가하는 것은 문제를 해결하기 위해 이 알고리즘을 사용하는 또 다른 중요한 부분입니다.
코딩 경험이 필요하지 않습니다. 360° 경력 지원. IIIT-B 및 upGrad에서 기계 학습 및 AI PG 디플로마.사람들은 종종 개체를 그 자체로 정의하는 것이 불가능하다고 믿습니다. 재귀는 그 이론이 틀렸음을 증명합니다. 그리고 이 기술이 올바른 방식으로 수행된다면 매우 강력한 결과를 얻을 수 있습니다. 몇 가지 예를 통해 재귀가 어떻게 작동하는지 봅시다. 문장이란? 그것은 접속사의 도움으로 함께 연결된 두 개 이상의 문장으로 정의할 수 있습니다. 마찬가지로 폴더는 파일 및 폴더를 저장하는 데 사용되는 저장 장치일 수 있습니다. 조상은 가계도에 있는 한 가족의 부모와 다른 가족 구성원의 조상이 될 수 있습니다.
재귀는 몇 가지 아주 간단한 단어를 사용하여 복잡한 상황을 정의하는 데 도움이 됩니다. 당신은 보통 조상을 어떻게 정의하겠습니까? 부모, 조부모 또는 증조부모. 이것은 계속될 수 있습니다. 마찬가지로 폴더를 정의하는 것은 어려운 작업일 수 있습니다. 파일 및 폴더가 고유한 권한을 가질 수 있는 일부 파일 및 폴더를 보유하는 모든 것이 될 수 있으며 이는 다시 계속될 수 있습니다. 이것이 재귀를 사용하면 상황을 평소보다 훨씬 쉽게 정의할 수 있습니다.
재귀는 또한 충분히 좋은 프로그래밍 기술입니다. 재귀 서브루틴은 자신을 직접 또는 간접적으로 호출하는 것으로 정의됩니다. 서브루틴을 직접 호출한다는 것은 서브루틴의 정의에 이미 정의된 서브루틴을 호출하는 호출문이 있다는 것을 의미합니다.
반면에 서브루틴의 간접 호출은 서브루틴이 다른 서브루틴을 호출한 다음 원래 서브루틴을 호출할 때 발생합니다. 재귀는 몇 줄의 코드를 사용하여 매우 복잡한 작업을 설명할 수 있습니다. 이제 우리가 이미 다뤘던 다양한 유형의 재귀에 대해 살펴보겠습니다.
더 읽어보기: 배워야 할 6가지 프로그래밍 언어
재귀의 유형
이미 언급했듯이 재귀에는 두 가지 유형만 있습니다. 그들이 서로 어떻게 다른지 봅시다. 직접 재귀는 원래 함수나 메서드 또는 서브루틴을 호출하는 단일 단계만 포함하므로 더 간단한 방법입니다. 반면 간접 재귀에는 여러 단계가 포함됩니다.
첫 번째 호출은 원래 메서드에서 두 번째 메서드에 대해 이루어지며, 두 번째 메서드는 원래 메서드를 호출합니다. 이 호출 체인에는 여러 메서드 또는 기능이 포함될 수 있습니다. 간단히 말해서 간접 재귀의 깊이에는 항상 편차가 있으며 이러한 깊이의 편차는 프로세스에 포함된 메서드의 수에 따라 달라집니다.

직접 재귀는 단독으로 단일 함수를 호출하는 데 사용할 수 있습니다. 반면에 간접 재귀는 다른 함수의 도움으로 둘 이상의 메서드나 함수를 호출하는 데 사용할 수 있으며 그것도 여러 번 사용할 수 있습니다. 간접 재귀는 간접 재귀가 오버헤드를 만들지 않는 반면 직접 재귀는 오버헤드를 만들지 않습니다.
재귀는 언제 사용됩니까?
재귀나 반복을 사용할 수 있는 상황이 있습니다. 그러나 항상 문제에 더 자연스럽게 맞는 것처럼 보이는 솔루션을 선택해야 합니다. 재귀는 데이터 추상화와 관련하여 항상 적합한 옵션입니다. 사람들은 종종 재귀 정의를 사용하여 데이터 및 관련 작업을 정의합니다.
그리고 재귀가 데이터에 대한 다양한 작업의 구현과 관련된 문제에 대한 대부분의 자연스러운 솔루션이라고 말하는 것은 잘못된 것이 아닙니다. 그러나 모든 문제에 대한 최상의 솔루션이 될 수 없는 재귀와 관련된 특정 사항이 있습니다. 이러한 상황에서는 반복적인 방법과 같은 대안이 가장 적합합니다.
재귀 구현은 많은 스택 공간을 사용하므로 종종 중복이 발생할 수 있습니다. 재귀를 사용할 때마다 해당 메서드의 새 인스턴스를 생성하는 메서드를 호출합니다. 이 새 인스턴스는 스택에 저장되고 반환 시 사용되는 다양한 매개변수와 변수를 전달합니다. 따라서 재귀는 다른 것보다 더 간단한 솔루션이지만 일반적으로 가장 실용적이지 않습니다.
또한 다른 문제에 대한 반복 또는 재귀를 선택하는 데 도움이 될 수 있는 미리 정의된 규칙 집합이 없습니다. 재귀를 사용하는 가장 큰 이점은 간결한 방법이라는 것입니다. 이렇게 하면 평소보다 쉽게 읽고 유지 관리할 수 있습니다. 그러나 재귀적 방법은 많은 저장 공간을 차지하고 구현하는 동안 많은 시간을 소비하기 때문에 우리가 사용할 수 있는 가장 효율적인 방법이 아닙니다.
몇 가지 사항을 염두에 두는 것은 문제에 대한 재귀를 선택하는 것이 올바른 방법인지 여부를 결정하는 데 도움이 될 수 있습니다. 해결하려는 문제가 재귀 용어로 언급되고 재귀 솔루션이 덜 복잡해 보인다면 재귀를 선택해야 합니다.
대부분의 경우 재귀는 사용하려는 알고리즘의 구현을 단순화한다는 것을 알아야 합니다. 이제 반복 및 재귀 사용과 관련된 복잡성이 주어진 문제에 대해 동일하다면 더 효율적일 가능성이 더 높기 때문에 반복을 사용해야 합니다.
또한 확인하십시오: 취업을 위한 23가지 최고의 컴퓨터 프로그래밍 과정
결론
그러나 결정을 내리는 것이 쉽지 않은 상황이 있을 수 있습니다. 효율성과 단순성 중에서 선택해야 합니다. 경험 많은 디자이너라면 언제 효율성을 더 중요하게 여겨야 하고 단순함이나 간결함을 선택해야 할 때를 정확히 알고 있을 것입니다.
데이터 구조, 데이터 과학에 대해 자세히 알고 싶으시면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 멘토링을 제공하는 IIIT-B & upGrad의 데이터 과학 경영자 PG 프로그램을 확인하십시오. 전문가, 업계 멘토와의 1:1 학습, 최고의 기업과의 400시간 이상의 학습 및 직업 지원.
재귀의 가장 일반적인 실제 응용 프로그램은 무엇입니까?
재귀는 함수가 문제를 해결하기 위해 간접적으로 또는 직접적으로 자신을 호출하는 프로세스입니다. 재귀 과정을 수행하는 함수를 재귀 함수라고 합니다. 재귀 알고리즘의 도움으로 꽤 쉽게 해결할 수 있는 특정 문제가 있습니다.
재귀의 가장 일반적인 실제 응용 프로그램은 Rs로 채워진 상자에 얼마나 많은 돈이 있는지 계산할 때입니다. 100노트. 메모가 너무 많으면 친구에게 전체 스택을 둘로 나누어 같은 작업을 하도록 요청할 수 있습니다. 둘 다 계산이 끝나면 총 금액을 얻기 위해 두 결과를 모두 더하면 됩니다.
재귀 함수가 가져야 하는 속성은 무엇입니까?
재귀 함수에는 무한 루프로 계속되는 기능이 있습니다. 무한 루프에 들어가는 것을 방지하기 위해 재귀 함수에 대해 정의해야 하는 두 가지 속성이 있습니다. 그들은:
1. 기본 기준 – 미리 정의된 기본 조건이 하나 있어야 합니다. 이 기본 기준이 충족될 때마다 함수는 자체 호출을 중지합니다.
2. 점진적 접근 - 재귀 호출은 점진적 접근으로 구성되어야 합니다. 함수에 대한 재귀 호출이 수행될 때마다 기본 조건 근처에 도달해야 합니다.
재귀의 장점과 단점은 무엇입니까?
재귀의 장점 중 일부는 재귀 함수에서 기본 조건과 재귀 케이스만 정의하면 된다는 것입니다. 이로 인해 반복 코드에 비해 코드가 매우 간단하고 짧으며 Tree Traversal 및 Graph와 같은 일부 문제는 본질적으로 재귀적입니다.
재귀의 가장 큰 단점은 모든 함수 호출이 기본 조건이 충족될 때까지 스택에 남아 있어야 하기 때문에 반복 프로그램에 비해 재귀 함수에 더 많은 공간 요구 사항이 있고 스택에 더 많은 시간 요구 사항이 있다는 것입니다. 각 함수 호출 후에 증가하고 최종 응답은 스택에서 모든 요소를 팝한 후에만 반환될 수 있습니다.