재귀는 함수가 자신을 호출할 수 있게 하여 반복 단계를 통해 복잡한 문제를 해결할 수 있도록 하는 컴퓨터 과학 및 수학의 기본 개념입니다. 재귀 함수의 실행을 이해하고 분석하는 데 일반적으로 사용되는 시각적 표현 중 하나는 재귀 트리입니다. 이 기사에서는 재귀 트리의 배경이 되는 이론과 그 구조, 재귀 알고리즘을 이해하는 데 있어 그 중요성을 살펴보겠습니다.

재귀 트리란 무엇입니까?

재귀 트리는 재귀 함수의 실행 흐름을 그래픽으로 표현한 것입니다. 재귀 호출의 시각적 분석을 제공하여 알고리즘이 분기되어 결국 기본 사례에 도달하는 과정을 보여줍니다. 트리 구조는 시간 복잡도를 분석하고 관련된 재귀 프로세스를 이해하는 데 도움이 됩니다.

리눅스에서 디렉토리 이름 바꾸기

트리 구조

재귀 트리의 각 노드는 특정 재귀 호출을 나타냅니다. 초기 호출은 상단에 표시되고 후속 호출은 그 아래로 분기됩니다. 트리는 아래쪽으로 자라며 계층 구조를 형성합니다. 각 노드의 분기 요소는 함수 내에서 이루어진 재귀 호출 수에 따라 달라집니다. 또한 트리의 깊이는 기본 사례에 도달하기 전의 재귀 호출 수에 해당합니다.

기본 케이스

기본 사례는 재귀 함수의 종료 조건 역할을 합니다. 재귀가 중지되고 함수가 값 반환을 시작하는 지점을 정의합니다. 재귀 트리에서 기본 사례를 나타내는 노드는 일반적으로 추가 재귀 호출이 발생하지 않으므로 리프 노드로 표시됩니다.

재귀 호출

재귀 트리의 하위 노드는 함수 내에서 이루어진 재귀 호출을 나타냅니다. 각 하위 노드는 별도의 재귀 호출에 해당하므로 새로운 하위 문제가 생성됩니다. 이러한 재귀 호출에 전달된 값이나 매개변수는 다를 수 있으며, 이로 인해 하위 문제의 특성이 달라질 수 있습니다.

실행 흐름:

재귀 트리를 순회하면 재귀 함수의 실행 흐름에 대한 통찰력을 얻을 수 있습니다. 루트 노드의 초기 호출부터 시작하여 분기를 따라 기본 사례를 만날 때까지 후속 호출에 도달합니다. 기본 사례에 도달하면 재귀 호출이 반환되기 시작하고 트리의 해당 노드가 반환된 값으로 표시됩니다. 순회는 전체 트리가 순회될 때까지 계속됩니다.

시간 복잡도 분석

재귀 트리는 재귀 알고리즘의 시간 복잡도를 분석하는 데 도움이 됩니다. 트리의 구조를 조사하여 재귀 호출 수와 각 수준에서 수행된 작업을 확인할 수 있습니다. 이 분석은 알고리즘의 전반적인 효율성을 이해하고 잠재적인 비효율성이나 최적화 기회를 식별하는 데 도움이 됩니다.

소개

• 숫자의 계승을 결정하는 프로그램을 생각해 보십시오. 이 함수는 숫자 N을 입력으로 사용하고 결과로 N의 계승을 반환합니다. 이 함수의 의사 코드는 다음과 같습니다.

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• 재귀는 이전에 언급한 함수로 예시됩니다. 숫자의 계승을 결정하는 함수를 호출합니다. 그런 다음 동일한 숫자의 더 작은 값이 주어지면 이 함수는 자신을 호출합니다. 이는 더 이상 함수 호출이 없는 기본 사례에 도달할 때까지 계속됩니다.
• 재귀는 결과가 동일한 문제의 작은 인스턴스 결과에 따라 달라질 때 복잡한 문제를 처리하기 위한 기술입니다.
• 함수에 대해 생각해 보면 기본 사례에 도달할 때까지 계속 자신을 호출하는 함수를 재귀적이라고 합니다.
• 모든 재귀 함수에는 기본 사례와 재귀 단계라는 두 가지 기본 구성 요소가 있습니다. 기본 사례에 도달하면 재귀 단계로의 이동을 중지합니다. 끝없는 재귀를 방지하려면 기본 사례를 적절하게 정의해야 하며 중요합니다. 무한 재귀의 정의는 기본 사례에 도달하지 않는 재귀입니다. 프로그램이 기본 케이스에 도달하지 못하면 스택 오버플로가 계속 발생합니다.

재귀 유형

일반적으로 재귀에는 두 가지 형태가 있습니다.

• 선형 재귀
• 트리 재귀
• 선형 재귀

선형 재귀

• 실행될 때마다 자신을 한 번만 호출하는 함수를 선형 재귀적이라고 합니다. 선형 재귀의 좋은 예는 계승 함수입니다. '선형 재귀'라는 이름은 선형 재귀 함수를 실행하는 데 선형적인 시간이 걸린다는 사실을 나타냅니다.
• 아래 의사 코드를 살펴보십시오.

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• doSomething(n) 함수를 보면 n이라는 매개변수를 받아들이고 동일한 프로시저를 더 낮은 값으로 한 번 더 호출하기 전에 몇 가지 계산을 수행합니다.
• doSomething() 메서드가 인수 값 n을 사용하여 호출될 때 T(n)이 계산을 완료하는 데 필요한 총 시간을 나타낸다고 가정해 보겠습니다. 이를 위해 회귀 관계 T(n) = T(n-1) + K를 공식화할 수도 있습니다. 여기서 K는 상수로 사용됩니다. 함수가 변수에 메모리를 할당 또는 할당 해제하거나 수학 연산을 수행하는 데 시간이 걸리기 때문에 상수 K가 포함되었습니다. 시간은 매우 미미하고 중요하지 않기 때문에 K를 사용하여 시간을 정의합니다.
• 이 재귀 프로그램의 시간 복잡도는 최악의 시나리오에서 doSomething() 메서드가 n 번 호출되므로 간단히 계산할 수 있습니다. 공식적으로 말하면 함수의 시간 복잡도는 O(N)입니다.

트리 재귀

• 재귀 사례에서 두 번 이상 재귀 호출을 수행하는 경우 이를 트리 재귀라고 합니다. 트리 재귀의 효과적인 예시는 피보나치 수열입니다. 트리 재귀 함수는 지수 시간으로 작동합니다. 시간적 복잡성이 선형적이지 않습니다.
• 아래 의사 코드를 살펴보세요.

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• 이 코드와 이전 코드의 유일한 차이점은 이 코드는 더 낮은 n 값을 사용하여 동일한 함수를 한 번 더 호출한다는 것입니다.
• 이 함수에 대한 회귀 관계를 T(n) = T(n-1) + T(n-2) + k라고 가정하겠습니다. K는 다시 한 번 상수로 사용됩니다.
• 더 작은 값으로 동일한 함수를 두 번 이상 호출하는 경우 이러한 종류의 재귀를 트리 재귀라고 합니다. 이제 흥미로운 점은 이 기능이 얼마나 시간을 소모하는가입니다.
• 동일한 함수에 대해 아래 재귀 트리를 기반으로 추측해 보세요.
  
• 특히 트리 재귀인 경우 재귀 함수를 직접 살펴봄으로써 시간 복잡도를 추정하는 것이 어렵다는 생각이 들 수도 있습니다. 재귀 트리 방법은 이러한 함수의 시간적 복잡성을 계산하는 여러 기술 중 하나입니다. 좀 더 자세히 살펴보겠습니다.

재귀 트리 방법이란 무엇입니까?

• T(N) = T(N/2) + N과 같은 반복 관계 또는 앞서 재귀 섹션에서 다루었던 두 가지 관계는 재귀 트리 접근 방식을 사용하여 해결됩니다. 이러한 반복 관계는 종종 문제를 해결하기 위해 분할 및 정복 전략을 사용합니다.
• 더 큰 문제가 더 작은 하위 문제로 분해될 때 생성되는 더 작은 하위 문제에 대한 답변을 통합하는 데는 시간이 걸립니다.
• 예를 들어 병합 정렬의 경우 반복 관계는 T(N) = 2 * T(N/2) + O(N)입니다. 결합된 크기 T(N/2)로 두 하위 문제에 대한 답을 결합하는 데 필요한 시간은 O(N)이며 이는 구현 수준에서도 마찬가지입니다.
• 예를 들어 이진 검색의 반복 관계는 T(N) = T(N/2) + 1이므로 이진 검색을 반복할 때마다 검색 공간이 절반으로 줄어드는 것을 알 수 있습니다. 결과가 결정되면 함수를 종료합니다. 반복 관계에는 일정한 시간 작업이므로 +1이 추가됩니다.
• 재발 관계 T(n) = 2T(n/2) + Kn을 고려해야 합니다. Kn은 n/2차원 하위 ​​문제에 대한 답을 결합하는 데 필요한 시간을 나타냅니다.
• 앞서 언급한 순환 관계에 대한 재귀 트리를 그려보겠습니다.

위의 재귀 트리를 연구하여 다음과 같은 몇 가지 결론을 내릴 수 있습니다.

1. 각 수준에서 문제의 규모는 노드의 가치를 결정하는 데 중요한 전부입니다. 이슈 크기는 레벨 0에서는 n, 레벨 1에서는 n/2, 레벨 2에서는 n/2 등입니다.

2. 일반적으로 트리의 높이는 log(n)과 동일하다고 정의합니다. 여기서 n은 문제의 크기이고 이 재귀 트리의 높이는 트리의 수준 수와 같습니다. 방금 설정한 것처럼 분할 정복 전략은 반복 관계에서 문제를 해결하는 데 사용되며 문제 크기 n에서 문제 크기 1로 이동하려면 단순히 log(n) 단계를 수행하면 되기 때문에 이는 사실입니다.

• 예를 들어 N = 16의 값을 생각해 보세요. 각 단계에서 N을 2로 나누는 것이 허용된다면 N = 1을 얻으려면 몇 단계가 필요합니까? 각 단계에서 2로 나누는 것을 고려하면 정답은 log(16) 밑수 2의 값인 4입니다.

로그(16) 밑수 2

이진 검색 트리에서 삭제

로그(2^4) 밑수 2

4 * log(2) 밑수 2, log(a) 밑수 a = 1이므로

따라서 4 * log(2) 밑수 2 = 4

3. 각 수준에서 반복의 두 번째 항은 루트로 간주됩니다.

이 전략의 이름에는 '나무'라는 단어가 등장하지만 이를 이해하기 위해 나무에 대한 전문가가 될 필요는 없습니다.

빠른 정렬 자바

재귀 관계를 해결하기 위해 재귀 트리를 사용하는 방법은 무엇입니까?

재귀 트리 기법에서 하위 문제의 비용은 하위 문제를 해결하는 데 필요한 시간입니다. 따라서 재귀 트리와 연결된 '비용'이라는 문구를 보면 이는 단순히 특정 하위 문제를 해결하는 데 필요한 시간을 나타냅니다.

몇 가지 예를 통해 이러한 모든 단계를 이해해 보겠습니다.

예

반복 관계를 고려하면,

티(n) = 2T(n/2) + K

해결책

주어진 반복 관계는 다음과 같은 속성을 보여줍니다.

문제 크기 n은 각각 크기 n/2인 두 개의 하위 문제로 나뉩니다. 이러한 하위 문제에 대한 솔루션을 결합하는 데 드는 비용은 K입니다.

n/2의 각 문제 크기는 각각 크기가 n/4인 두 개의 하위 문제로 나누어집니다.

마지막 수준에서는 하위 문제 크기가 1로 줄어듭니다. 즉, 마침내 기본 사례에 도달한 것입니다.

데이터베이스의 정규화

이 반복 관계를 해결하기 위한 단계를 따르겠습니다.

1단계: 재귀 트리 그리기

2단계: 나무 높이 계산

우리는 숫자를 2로 연속적으로 나누면 이 숫자가 1로 줄어들 때가 있다는 것을 알고 있기 때문에 문제 크기 N과 마찬가지로 K를 2로 나눈 후에 N이 1이 된다는 것을 의미합니다. n / 2^k) = 1

여기서 n / 2^k는 마지막 수준의 문제 크기이며 항상 1과 같습니다.

이제 우리는 log()를 양쪽에 취함으로써 위의 표현식으로부터 k의 값을 쉽게 계산할 수 있습니다. 아래는 좀 더 명확한 파생어입니다.

n = 2^k

• 로그(n) = 로그(2^k)
• 로그(n) = k * 로그(2)
• k = 로그(n) / 로그(2)
• k = log(n) 밑수 2

따라서 트리의 높이는 log(n) 밑이 2입니다.

3단계: 각 수준의 비용 계산

BFS 알고리즘

• 수준 0의 비용 = K, 두 개의 하위 문제가 병합됩니다.
• 수준 1의 비용 = K + K = 2*K, 두 개의 하위 문제가 두 번 병합됩니다.
• 수준 2의 비용 = K + K + K + K = 4*K, 두 개의 하위 문제가 4번 병합됩니다. 등등....

4단계: 각 수준의 노드 수 계산

먼저 마지막 수준의 노드 수를 결정해 보겠습니다. 재귀 트리에서 다음을 추론할 수 있습니다.

• 레벨 0에는 1(2^0)개의 노드가 있습니다.
• 레벨 1에는 2(2^1)개의 노드가 있습니다.
• 레벨 2에는 4(2^2)개의 노드가 있습니다.
• 레벨 3에는 8(2^3)개의 노드가 있습니다.

따라서 log(n) 레벨에는 2^(log(n)) 노드, 즉 n 노드가 있어야 합니다.

5단계: 모든 레벨의 비용을 합산합니다.

• 총 비용은 다음과 같이 쓸 수 있습니다.
• 총 비용 = 마지막 수준을 제외한 모든 수준의 비용 + 마지막 수준의 비용
• 총 비용 = 레벨 0 비용 + 레벨 1 비용 + 레벨 2 비용 +.... + 레벨-log(n) 비용 + 마지막 레벨 비용

마지막 수준의 비용은 기본 사례이고 마지막 수준에서 병합이 수행되지 않기 때문에 별도로 계산됩니다. 따라서 이 수준에서 단일 문제를 해결하는 데 드는 비용은 일정한 값입니다. O(1)로 하자.

값을 공식에 ​​대입해 보겠습니다.

• T(n) = K + 2*K + 4*K + .... + log(n)` 번 + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) 번)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) 번 + O(n)

위의 식을 자세히 살펴보면 기하수열(a, ar, ar^2, ar^3 ......무한시간)을 이루고 있습니다. GP의 합은 S(N) = a / (r - 1)로 제공됩니다. 여기에 첫 번째 항이 있고 r은 공비입니다.