데이터 구조-재귀 기초

일부 컴퓨터 프로그래밍 언어는 모듈 또는 함수가 자체 호출을 허용합니다. 이 기술을 재귀라고합니다. 재귀에서 함수α 자신을 직접 호출하거나 함수를 호출합니다. β 차례로 원래 함수를 호출합니다. α. 함수α 재귀 함수라고합니다.

Example − 자신을 호출하는 함수.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example − 다른 함수를 호출하고 다시 호출하는 함수.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

속성

재귀 함수는 루프처럼 무한대로 갈 수 있습니다. 재귀 함수의 무한 실행을 피하기 위해 재귀 함수가 가져야하는 두 가지 속성이 있습니다.

Base criteria −이 조건이 충족되면 함수가 자신을 재귀 적으로 호출하는 것을 중지하는 기본 기준 또는 조건이 하나 이상 있어야합니다.
Progressive approach − 재귀 호출은 재귀 호출이 이루어질 때마다 기본 기준에 더 가까워 지도록 진행되어야합니다.

이행

많은 프로그래밍 언어는 다음을 통해 재귀를 구현합니다. stacks. 일반적으로 함수 (caller)는 다른 함수 (callee) 또는 자체적으로 호출자 인 경우 호출자 함수는 실행 제어를 호출자에게 전달합니다. 이 전송 프로세스에는 호출자에서 수신자에게 전달되는 일부 데이터가 포함될 수도 있습니다.

이는 호출자 함수가 일시적으로 실행을 일시 중단하고 나중에 실행 제어가 호출 수신자 함수에서 반환 될 때 다시 시작해야 함을 의미합니다. 여기서 호출자 함수는 자체적으로 보류 된 실행 지점에서 정확히 시작해야합니다. 또한 작업중인 것과 똑같은 데이터 값이 필요합니다. 이를 위해 호출자 함수에 대해 활성화 레코드 (또는 스택 프레임)가 생성됩니다.

이 활성화 레코드는 지역 변수, 형식 매개 변수, 반환 주소 및 호출자 함수에 전달 된 모든 정보에 대한 정보를 유지합니다.

재귀 분석

반복으로 동일한 작업을 수행 할 수 있기 때문에 재귀를 사용하는 이유를 논할 수 있습니다. 첫 번째 이유는 재귀가 프로그램을 더 읽기 쉽게 만들고 최신의 향상된 CPU 시스템으로 인해 재귀가 반복보다 더 효율적이기 때문입니다.

시간 복잡성

반복의 경우 시간 복잡성을 계산하기 위해 반복 횟수를 사용합니다. 마찬가지로 재귀의 경우 모든 것이 일정하다고 가정하고 재귀 호출이 수행되는 횟수를 알아 내려고합니다. 함수에 대한 호출은 Ο (1)이므로 재귀 호출이 수행 된 횟수 (n)는 재귀 함수 Ο (n)을 만듭니다.

공간 복잡성

공간 복잡성은 모듈을 실행하는 데 필요한 추가 공간의 양으로 계산됩니다. 반복의 경우 컴파일러에는 추가 공간이 거의 필요하지 않습니다. 컴파일러는 반복에 사용되는 변수 값을 계속 업데이트합니다. 그러나 재귀의 경우 시스템은 재귀 호출이 이루어질 때마다 활성화 레코드를 저장해야합니다. 따라서 재귀 함수의 공간 복잡도는 반복 함수의 공간 복잡도보다 높아질 수 있다고 생각됩니다.