꼬리 재발은 정확히 어떻게 작동하는가?

IT이야기

꼬리 재발은 정확히 어떻게 작동하는가?

cyworld 2022. 5. 10. 22:26

꼬리 재발은 정확히 어떻게 작동하는가?

나는 꼬리의 재귀가 어떻게 작동하는지 그리고 꼬리와 일반적인 재귀 사이의 차이를 거의 이해한다.왜 반송 주소를 기억하는데 스택이 필요하지 않은지 이해가 안 가.

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

꼬리 재귀함수에서 함수 자체를 부르고 나면 할 일이 없지만 나에게는 말이 되지 않는다.

컴파일러는 단순히 이것을 변환할 수 있다.

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

다음과 같은 것으로:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

당신은 왜 "반품주소를 기억하는데 스택이 필요하지 않냐"고 묻는다.

나는 이것을 돌려보고 싶다.그것은 반송 주소를 기억하기 위해 스택을 사용한다.꼬리가 재발하는 기능은 스택에 자체 반송 주소가 있고, 호출된 기능으로 점프하면 이를 자체 반송 주소로 취급한다는 것이 요령이다.

구체적으로, 테일 콜 최적화 없이:

f: ...
   CALL g
   RET
g:
   ...
   RET

이 경우, 언제g스택은 다음과 같이 보일 것이다.

   SP ->  Return address of "g"
          Return address of "f"

반면에, 테일 콜 최적화를 통해:

f: ...
   JUMP g
g:
   ...
   RET

이 경우, 언제g스택은 다음과 같이 보일 것이다.

   SP ->  Return address of "f"

분명히, 언제g다시 돌아오면, 그것은 그 장소로 돌아갈 것이다.f부름을 받았다.

편집: 위의 예에서는 한 함수가 다른 함수를 호출하는 경우를 사용한다.그 메커니즘은 함수가 스스로 호출할 때 동일하다.

여기 재귀 함수의 작동 방식을 보여주는 간단한 예가 있다.

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

꼬리 재귀는 단순한 재귀함수로, 기능 끝에서 재발이 이루어지므로 상향에서는 어떤 코드도 수행되지 않으며, 이는 대부분의 고급 프로그래밍 언어 컴파일러들이 꼬리 재귀 최적화라고 알려진 것을 할 수 있도록 도와주며, 꼬리 재귀모듈로 알려진 보다 복잡한 최적화도 가지고 있다.

재귀함수는 스스로 부르는 함수다.

프로그래머가 최소한의 코드를 사용하여 효율적인 프로그램을 작성할 수 있도록 한다.

제대로 쓰지 않으면 무한 루프 등 예상치 못한 결과를 초래할 수 있다는 단점이 있다.

단순 재귀 기능과 테일 재귀 기능을 모두 설명하겠다.

단순 재귀 함수를 작성하려면

가장 먼저 고려해야 할 점은 if 루프인 루프에서 언제 나오기로 결정하느냐 하는 것이다.
두 번째는 우리가 우리 자신의 기능이라면 어떤 과정을 해야 하는가이다.

주어진 예에서:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

위의 예시로부터

if(n <=1)
     return 1;

루프를 언제 종료할지 결정하는 요인

else 
     return n * fact(n-1);

실제 처리 여부

쉬운 이해를 위해 그 과제를 하나씩 풀어보자.

내가 달리면 내부에서 어떤 일이 일어나는지 봅시다.fact(4)

n=4 대체

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If루프가 고장나서 로 간다.else반복해서 돌아오게 하다.4 * fact(3)

스택 메모리에는4 * fact(3)

n=3 대체

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If루프가 고장나서 로 간다.else고리를 틀다

그래서 그것은 돌아온다.3 * fact(2)

우리가 ``4 * 사실 (3)"이라고 불렀던 것을 기억하라.

에 대한 출력.fact(3) = 3 * fact(2)

지금까지 그 스택은4 * fact(3) = 4 * 3 * fact(2)

스택 메모리에는4 * 3 * fact(2)

n=2 대체

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If루프가 고장나서 로 간다.else고리를 틀다

그래서 그것은 돌아온다.2 * fact(1)

우리가 전화했던 거 기억나?4 * 3 * fact(2)

에 대한 출력.fact(2) = 2 * fact(1)

지금까지 그 스택은4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

스택 메모리에는4 * 3 * 2 * fact(1)

n=1 대체

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If루프가 참이다

그래서 그것은 돌아온다.1

우리가 전화했던 거 기억나?4 * 3 * 2 * fact(1)

에 대한 출력.fact(1) = 1

지금까지 그 스택은4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

마지막으로, 사실(4) = 4 * 3 * 2 * 1 = 24

꼬리 재발은

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

n=4 대체

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If루프가 고장나서 로 간다.else반복해서 돌아오게 하다.fact(3, 4)

스택 메모리에는fact(3, 4)

n=3 대체

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If루프가 고장나서 로 간다.else고리를 틀다

그래서 그것은 돌아온다.fact(2, 12)

스택 메모리에는fact(2, 12)

n=2 대체

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If루프가 고장나서 로 간다.else고리를 틀다

그래서 그것은 돌아온다.fact(1, 24)

스택 메모리에는fact(1, 24)

n=1 대체

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If루프가 참이다

그래서 그것은 돌아온다.running_total

에 대한 출력.running_total = 24

마지막으로, 사실(4,1) = 24

꼬리 재귀는 보통 컴파일러에 의해 루프로 변환될 수 있으며, 특히 축전지를 사용할 경우 더욱 그러하다.

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

같은 것으로 편찬할 수 있을 것이다.

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}

재귀 함수에 존재해야 하는 두 가지 요소가 있다.

재귀 호출
반환 값 수를 유지하는 위치.

"일반적인" 재귀 함수는 (2) 스택 프레임에 유지된다.

정규 재귀 함수의 반환 값은 다음과 같은 두 가지 유형의 값으로 구성된다.

기타 반환 값
소유 함수 계산 결과

예를 들어보자.

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

f(5) 프레임은 예를 들어 자체 연산(5)과 f(4)의 값을 "저장"한다.요인(5)을 호출할 경우 스택 호출이 접히기 직전에 다음을 수행하십시오.

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

각 스택은 내가 언급한 값 외에 함수의 전체 범위를 저장한다는 점에 유의하십시오.따라서 재귀함수 f의 메모리 사용량은 O(x)이며, 여기서 x는 내가 해야 하는 재귀 호출의 수입니다.따라서 요인(1) 또는 요인(2)을 계산하기 위해 1kb의 RAM이 필요한 경우 요인(100)을 계산하기 위해 ~100k가 필요하다.

Tail Repursive 함수는 인수에 (2)를 삽입한다.

꼬리 재귀에서, 나는 매개변수를 사용하여 각 재귀 프레임의 부분 계산 결과를 다음 계산으로 전달한다.요인 예인 Tail Reprecursive를 봅시다.

int factorial (int n) {
    int helper(int num, int accumulated)
        {
            if num == 0 return accumulated
            else return helper(num - 1, accumulated*num)
        }
    return helper(n, 1)    
}

요인(4)의 프레임을 살펴봅시다.

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

차이점이 보이십니까?"정기적" 재귀 호출에서 반환 함수는 재귀적으로 최종 값을 구성한다. Tail Reutersion(테일 재귀)에서는 베이스 케이스만 참조한다(마지막으로 평가된 경우).우리는 축전지를 오래된 값을 추적하는 주장이라고 부른다.

재귀 템플릿

정기적인 재귀 함수는 다음과 같다.

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Tail 재귀로 변환하기 위해 다음 절차를 따르십시오.

축전지를 운반하는 도우미 기능 소개
어큐뮬레이터가 베이스 케이스에 설정된 상태에서 메인 기능 내부에서 도우미 기능을 실행한다.

보기:

type tail(n):
    type helper(n, accumulator):
        if n == base case
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

차이점이 보이십니까?

테일 콜 최적화

Tail Call 스택의 Non-Terminal-Case 스택에 어떤 상태도 저장되지 않기 때문에, 그것들은 그렇게 중요하지 않다.일부 언어/인터프리터는 이전 스택을 새 스택으로 대체한다.따라서, 통화 수를 제한하는 스택 프레임이 없는 경우, Tail Calls는 이러한 경우, 전화 건수처럼 행동한다.

그것을 최적화하는 것은 당신의 컴파일러에게 달려있다.

나의 대답은 추측에 가깝다. 왜냐하면 재귀는 내부 구현과 관련된 것이기 때문이다.

꼬리 재귀에서는 같은 기능의 끝에서 재귀함수를 부른다.컴파일러는 다음과 같은 방법으로 최적화할 수 있다.

진행 중인 기능이 종료되도록 두십시오(즉, 사용된 스택을 호출함).
함수에 대한 인수로 사용할 변수를 임시 저장소에 저장
이 후 임시 저장된 인수를 사용하여 함수를 다시 호출하십시오.

보시다시피 동일 기능의 다음 반복 이전에 본래의 기능을 정리하고 있기 때문에 실제로 스택을 「사용」하고 있는 것은 아니다.

그러나 나는 기능 내부에 소멸자가 존재한다면 이 최적화는 적용되지 않을 수 있다고 믿는다.

컴파일러는 충분히 지능적이어서 꼬리 재발에 대해 이해할 수 있다.재귀 호출에서 돌아오는 동안, 보류 중인 작업이 없고 재귀 호출이 꼬리 재귀 범주에 해당하는 마지막 문장이 되는 경우.컴파일러는 기본적으로 꼬리 재귀 최적화를 수행하여 스택 구현을 제거한다.아래 코드를 고려하십시오.

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

최적화를 수행한 후, 위의 코드는 아래 코드로 변환된다.

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

이것은 컴파일러가 Tail Repursion Optimization을 하는 방법이다.

참조URL: https://stackoverflow.com/questions/15518882/how-exactly-does-tail-recursion-work

'IT이야기' 카테고리의 다른 글

Java에서 Long을 바이트[]로 변환한 후 다시 변환하는 방법 (0)	2022.05.10
Vue js 각 개별 요소의 클래스 전환 (0)	2022.05.10
JS에서 api 클래스를 작성하고 Vuex에 전화하여 상태를 변경하는 방법 (0)	2022.05.10
HTTP 응답 본문을 문자열로 가져오는 방법 (0)	2022.05.10
Java에서 파일 to 바이트[] (0)	2022.05.10

현재글꼬리 재발은 정확히 어떻게 작동하는가?

각종 프로그래밍 정보를 다루는 블로그입니다.

관광, 축제, 놀거리, c#, spring3, 볼거리, 가족나들이, 경기, 유치원, 연극, 펜션, 여행, 공연, javascript, 숙박, 뮤지컬, 행사, Java, jQuery, 주말나들이,

Today :
Yesterday :

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

cyworld

꼬리 재발은 정확히 어떻게 작동하는가?

꼬리 재발은 정확히 어떻게 작동하는가?

재귀 함수에 존재해야 하는 두 가지 요소가 있다.

"일반적인" 재귀 함수는 (2) 스택 프레임에 유지된다.

Tail Repursive 함수는 인수에 (2)를 삽입한다.

재귀 템플릿

테일 콜 최적화

'IT이야기' 카테고리의 다른 글

'IT이야기'의 다른글

티스토리툴바

꼬리 재발은 정확히 어떻게 작동하는가?

꼬리 재발은 정확히 어떻게 작동하는가?

재귀 함수에 존재해야 하는 두 가지 요소가 있다.

"일반적인" 재귀 함수는 (2) 스택 프레임에 유지된다.

Tail Repursive 함수는 인수에 (2)를 삽입한다.

재귀 템플릿

테일 콜 최적화

'IT이야기' 카테고리의 다른 글

'IT이야기'의 다른글

관련글

티스토리툴바