Published 2023. 1. 17. 23:44

재귀용법 (recursive call, 재귀호출)

lecture

728x90

재귀용법이란

함수 안에서 동일한 함수를 호출하는 형태

여러 알고리즘 작성시 사용되므로 우리 모두가 익숙해야져야합니다.

또한, 팩토리얼을 구하는 알고리즘을 재귀호출을 활용해서 알고리즘 작성을 할것인데 같이 보면 좋을거같습니다.

5! = 5 x 4 x 3 x 2 x 1
6! = 6 x 5 x 3 x 2 x 1 = 6 x 5! = 6 x 5 x 4!
n! = n x (n-1) x (n-2) x (n-3)! = n x (n-1)!

위와 같이 보이는것을 코드로 작성을 하게된다면

public static int factorialFunc2(int n) {
		if(n<=1) {
			return 1;
		}
		return factorialFunc2(n-1);
	}

이런식으로 작성이 됩니다.

좀 더 쉽게 설명하기 위해서 그림으로 한번 보도록하겠습니다.

재귀 유형

넓은 의미에서 재귀는 직접 재귀와 간접 재귀의 두 가지 유형이 있습니다.

직접 재귀
간접 재귀

int testfunc(int num) {
  if (num == 0)
    return 0;
  else
    return (testfunc(num - 1));
}

직접 재귀에서는 계승 예제에서 본 것처럼 함수가 자체 내부에서 자신을 호출합니다. 재귀의 가장 일반적인 형태입니다.

메소드가 자신을 호출할 때 자신을 호출하는 것을 중지하는 어떤 조건을 만나야 합니다. 메서드가 이러한 경우를 만나지 않고 반복해서 자신을 호출하면 절대 종료되지 않습니다. 이것을 무한 재귀 라고 합니다. 이로 인해 응용 프로그램이 비정상적으로 종료됩니다.

무제한 재귀를 방지하려면 메서드가 자신을 호출하지 않는 기본 조건이 하나 이상 있어야 합니다. 또한 메서드에 전달된 값이 결국 이 조건을 충족해야 합니다. 이런 일이 발생하면 제한된 재귀 가 있다고 말합니다 .

간접 재귀

간접 재귀에서 하나의 메서드(예: 메서드 A)는 다른 메서드 B를 호출한 다음 메서드 A를 호출합니다. 여기에는 결국 순환 호출 시퀀스를 생성하는 둘 이상의 메서드가 포함됩니다.

int testfunc1(int num) {
  if (num == 0)
    return 0;
  else
    return (testfunc2(num - 1));
}

int testfunc2(int num2) { 
     return testfunc1(num2 - 1); 
}

HEAD 대 TAIL 재귀

헤드 재귀

헤드 재귀에서 재귀 호출이 발생하면 함수의 다른 처리 전에 발생합니다(함수 맨 위 또는 헤드에서 발생한다고 생각하십시오).

public void head(int n)
{
    if(n == 0)
        return;
    else
        head(n-1);
        
    System.out.println(n);
}

꼬리 재귀

헤드 재귀와 반대입니다. 처리는 재귀 호출 전에 발생합니다. 꼬리 재귀는 루프와 비슷합니다. 이 메서드는 다음 재귀 호출로 이동하기 전에 모든 문을 실행합니다.

public void tail(int n)
{ 
    if(n == 1) 
        return; 
    else
        System.out.println(n);

    tail(n-1);
}

일반적으로 꼬리 재귀는 항상 머리 재귀보다 낫습니다 . 둘 다 시간 복잡도와 보조 공간이 같더라도 꼬리 재귀가 함수 스택의 메모리 측면에서 우위를 차지합니다.

헤드 재귀는 사후 재귀 코드 문이 실행될 때까지 함수 스택 메모리에서 대기하여 전체 결과에 대기 시간이 발생하는 반면 테일 재귀는 함수 스택 오버 실행에서 종료됩니다.

스택을 사용한 재귀

스택은 서로 위에 쌓인 일련의 물리적 항목에 비유되는 LIFO(후입선출) 데이터 구조입니다. 이 구조를 사용하면 스택 맨 위에서 항목을 쉽게 제거할 수 있으며 스택의 더 깊은 항목에 도달하려면 다른 여러 항목을 먼저 제거해야 할 수 있습니다.

스택에서 푸시 및 팝 작업은 스택의 맨 위라고 하는 구조의 한쪽 끝에서만 발생합니다. 모든 푸시 작업은 스택에 새 스택 프레임을 생성합니다.

함수형 프로그래밍에서 스택 프레임에는 단일 메서드 호출의 상태가 포함됩니다. 코드가 메서드를 호출할 때마다 JVM은 전역 스택에 새 프레임을 만들고 푸시합니다. 메서드에서 반환된 후 해당 스택 프레임이 팝되고 삭제됩니다.

재귀를 사용하는 동안 각 재귀 함수 호출 f(n)은 n의 모든 값이 이전 계산에서 격리되어야 하기 때문에 스택 프레임으로 저장됩니다. 기본 조건에 도달하기 위한 재귀 함수 호출만큼 많은 스택 프레임이 있습니다.

사용 가능한 스택 크기가 유한한 경우에 유의하십시오. 호출이 너무 많으면 사용 가능한 공간이 채워지고 StackOverflowError 가 발생 합니다.

트리를 사용한 재귀

스택과 마찬가지로 트리도 재귀 데이터 유형입니다. 트리는 또한 필요할 때 응용 프로그램에서 검색할 수 있는 노드에 정보를 저장합니다.

트리를 순회하는 가장 일반적인 세 가지 방법은 순차, 선순 및 후순으로 알려져 있습니다. 검색 순서를 구현하는 가장 효율적인 기술은 재귀를 사용하는 것입니다.

예를 들어 특정 데이터 조각에 대한 이진 검색 트리 검색은 매우 간단합니다. 트리의 루트에서 시작하여 검색 중인 데이터 요소와 비교합니다. 우리가 보고 있는 노드에 해당 데이터가 포함되어 있으면 완료된 것입니다. 그렇지 않으면 검색 요소가 현재 노드보다 작은지 큰지 결정합니다. 현재 노드보다 작으면 노드의 왼쪽 자식으로 이동합니다. 현재 노드보다 크면 노드의 오른쪽 자식으로 이동합니다. 그런 다음 필요에 따라 반복합니다.

결국 재귀적으로 '하위 트리'가 노드에 불과한 지점에 도달합니다. 이 시점에서 기본 조건에 도달하면 결과를 찾았습니다. 더 큰 문제의 하위 문제를 해결하는 것으로 재귀를 어떻게 정의했는지 기억하십시오. 이진 검색은 그 이론의 또 다른 사용 사례입니다.

SEARCH(x, Y)
  if(Y.root != null)
      if(Y.root.data == x)
          return r
      else if(Y.root.data > x)
          return SEARCH(x, Y.root.left)
      else
          return SEARCH(x, Y.root.right)

재귀와 반복의 차이점

일반적으로 위에서 논의한 각 문제는 반복 또는 재귀를 사용하여 해결할 수 있습니다. 이상적인 솔루션은 해결하려는 문제와 코드가 실행되는 환경에 따라 크게 달라집니다.

재귀는 종종 보다 추상적인 문제를 해결하기 위해 선호되는 도구이며 반복은 보다 낮은 수준의 코드에 선호됩니다. 반복은 더 나은 런타임 성능을 제공할 수 있지만 재귀는 프로그래머로서의 생산성을 향상시킬 수 있습니다.

잘못 이해하기 쉽고 기존 재귀 솔루션을 이해하기가 더 어려울 수 있습니다. 재귀와 그 대안 중에서 선택할 때 느린 실행 시간과 스택 오버플로 문제에 대해 매우 주의하십시오.

두 접근 방식을 빠르게 비교해 보겠습니다.

요인/속성	Recursive	LOOP
기초적인	재귀는 자체 코드 내에서 함수 자체를 호출하는 프로세스입니다.	반복에서 루프는 조건이 거짓이 될 때까지 명령 집합을 반복적으로 실행하는 데 사용됩니다.
통사론	재귀에는 기본 조건 이라는 종료 조건이 있습니다 .	반복에는 초기화, 조건, 변수의 증가/감소가 포함됩니다.
성능	반복보다 느립니다.	재귀보다 빠릅니다.
적용 가능	문제는 부분적으로 해결될 수 있으며 나머지 문제는 동일한 형태로 해결됩니다.	문제는 한 번에 하나씩 완료되는 일련의 단계로 변환됩니다.
시간 복잡도	시간 복잡도가 높습니다.	상대적으로 시간 복잡도가 낮습니다. 루프에서 반복 횟수를 찾아 시간 복잡도를 계산할 수 있습니다.
스택	특정 유형의 재귀에서 스택을 업데이트하고 유지해야 합니다.	스택을 사용하지 않습니다.
메모리	TCO가 적용되지 않으면 반복에 비해 더 많은 메모리를 사용합니다.	재귀에 비해 적은 메모리를 사용합니다.

재귀 알고리즘은 문제를 우리가 이미 답을 알고 있거나 동일한 알고리즘을 각 조각에 적용한 다음 결과를 결합하여 해결할 수 있는 더 작은 조각으로 나눕니다.

재귀는 프로그래밍에서 유용한 도구이지만 재귀의 간단한 구현은 종종 실제 문제에 유용하지 않습니다. 기능적 인터페이스, 람다 식 및 무한 스트림은 이러한 경우 재귀를 실현할 수 있도록 마무리 호출 최적화를 설계하는 데 도움이 될 수 있습니다.

재귀 용법을 잘 알아 두시면 고급 알고리즘에 접급하실때 중요하게 쓰입니다. ^^

그럼 화이팅!!