Clojure 학습 노트:10 아름다운 귀환

Clojure
Clojure 학습 노트:10 아름다운 귀환
귀속, 또는 함수의 귀속은 프로그램 설계 언어에서 함수 내부에서 함수 자체를 호출하는 용법을 가리킨다.
하나의 고전적인 예는 바로 곱셈의 계산이다.수학의 곱셈이 무슨 뜻인지 분석해 봅시다.간단하게 말하면 N의 곱하기는 1 * 2 * 3 ... * N의 값과 같다.만약 귀속을 사용하지 않는다면, 우리는 먼저 1에서 N까지의 수열을 만들어서 그것들을 곱할 수 있다.우리는 reduce 함수로 실현할 수 있다.

(defn factorial
    [number]
    (reduce * (range 1 (inc number)))) ;;   range  。

apply 함수로도 수행할 수 있습니다.

(defn factorial
    [number]
    (apply * (range 1 (inc number))))

apply 함수는 하나의 서열을 함수의 매개 변수로 펼칠 수 있다.

(apply * [1 2 3])
;;  
(* 1 2 3)

하지만 100의 곱셈을 계산하려 할 때 문제가 생긴다.왜 그랬을까?Clojure에서 정수 문자량[1]은 기본값int 유형이고 100의 곱하기는 int 유형이 표현할 수 있는 최대값보다 크기 때문이다.이 문제를 해결하기 위해 Clojure는 무한 정밀도를 지원할 수 있는 '대수' 글자의 양을 제공했다.너는 정수 글자의 양 뒤에 대문자 N을 붙이기만 하면 무한한 범위[2]를 지원할 수 있는'대정수'로 바꿀 수 있다.덧붙여 말하자면, 만약 소수 뒤에 대문자 M을 더하면, 그것을 무한 정밀도의 소수로 바꿀 수 있다.대수 유형과 일반 유형을 연산하면 결과는 자동으로 대수 유형으로 변한다.

(defn factorial
    [number]
    (reduce * (range 1N (inc number))))

=> (factorial 100) 
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000N

한참을 얘기했으나 이번 주제에 대해서는 언급하지 않았다.어떻게 귀속을 사용하여 곱셈 문제를 해결합니까?우선, 우리는 N의 곱셈이 사실 N-1의 곱셈의 값과 N을 곱하는 것을 관찰할 수 있다.만약 N-1의 곱셈 값을 얻어낼 수 있다면 N의 곱셈을 계산하는 것은 매우 간단하다.그럼 N-1의 곱셈은 얼마입니까?그것은 N-2의 곱하기 N-1과 같다.
사실 자세히 생각해 보면 N-1의 곱셈 값도 우리 이 곱셈 함수의'책임 범위'가 아닌가?만약 우리의 함수가 이미 완성된 것처럼 가장한다면, 우리는 우리의 곱셈 함수를 직접 호출하면 되지 않겠는가?이렇게 신기해요?네, 이렇게 신기해요.
코드가 또렷해 보입니다.

(defn factorial-recursive
    [number]
    (* number (factorial-recursive (dec number)))) ;;   N-1  

완벽해 보여요.하지만 만약 네가 정말 이렇게 한다면 분분 시스템은 파업할 것이다.왜 그랬을까?사실 함수 안에서 우리가 자신을 호출할 때 이 함수를 다시 집행한 것과 같다. 시스템은 현재의 상황을 기록하고 신세계로 모험을 간다. 그러나 이 신세계 함수 안에서 또 새로운 함수를 호출하여 자자손손이 무궁무진하여 멈출 수가 없다.그래서 마지막에 시스템 자원이 다 소모되면 붕괴된다.어떡하지?우리는 그것을 멈추게 할 방법을 생각해야 한다.어떻게 멈춰요?우리는 1의 곱셈 값이 1이라는 것을 알고 있다. 1을 계산할 때 1이라는 값을 바로 되돌릴 수 있다.

(defn factorial-recursive
    [number]
    (if (= 1 number)
      1N
      (* number (factorial-recursive (dec number)))))

이렇게 층층이 1로 호출되면 멈추고 층층이 되돌아와 결과를 얻는다.그래서'귀속'은 마지막에'귀속'을 해야 한다.
우리는 귀착되는 요점을 정리해 보았다.

함수 내에서 함수 자신을 실행해야 하는 곳을 찾아라

종료 조건을 찾아 무한 귀속을 피한다

귀환에 대한 '헐뜯기' 를 많이 들을 수 있다. 예를 들어 귀환 효율이 매우 느리고, 귀환이 창고의 넘침을 일으키기 쉽다는 등이다.사실 그들이 말한 것도 틀린 편은 아니지만, 전부 옳은 편도 아니다.조그마한 수단만 하면 귀속의 속도와 공간 점용이 비귀속 형식에 필적할 수 있고 때로는 비귀속 형식보다 더 빠르고 더 좋을 때도 있다!이런 수단을 미귀환 최적화라고 한다.무엇이 미귀환 최적화라고 합니까?우선 우리는 미귀환이 무엇인지 알아야 한다.글씨체로 볼 때 꼬리 귀환은 꼬리에서 귀환을 하는 것이다. 이 꼬리의 뜻은 함수의 마지막 줄(즉 함수 귀환 값의 위치)을 가리킨다.마지막 줄에서 자신을 호출하여 귀속시킨다. 시스템은 원래 호출된 상황을 기록해야 하기 때문에 호출이 끝난 후에 돌아오는 길을 찾아 아래의 코드를 집행할 수 있다. 그러나 우리는 마지막 줄에서 귀속을 진행하기 때문에 아래에 이미 코드가 없어서 시스템도 어떤 기록을 저장하지 않고 공간을 차지하지 않는다.그러나 우리의 곱셈 함수, 마지막 줄은 귀속을 집행해야 할 뿐만 아니라 하나의 숫자를 곱해야 한다. 시스템은 그 숫자를 보류해야 귀환할 때 곱셈을 할 수 있다. 어떻게 해야만 그 숫자를 보존할 수 있을 뿐만 아니라 마지막 줄도 귀환만 호출할 수 있겠는가?답은: 필요한 데이터를 매개 변수에 저장하여 매개 변수의 형식으로 다음 귀속에 전달한다.우리는 꼬리 귀속 형식의 곱셈 함수를 살펴보자.

(defn factorial-tail-recursive
    [number result]
    (if (= 1 number)
        result
        (factorial-recursive (dec number) (* (bigint result) number)))) ;;   bigint   N  ， 

=> (factorial-tail-recursive 4 1)
24N

마지막 줄은 확실히 귀속 호출만 있을 뿐인데, 이 인자가 많다는 것은 무슨 뜻입니까?사실 그것은 한 걸음 한 걸음의 결과를 보존하는 데 쓰인다. 여기서 우리는 곱셈의 교환율을 이용했고, 어떤 숫자에 1을 곱하면 그 자체의 두 가지 성질과 같다.이 함수를 사용할 때 두 번째 매개 변수는 1이어야 한다.매번 귀환할 때마다number를 이 숫자에 곱하는데, 사실은 거꾸로 한 번 곱한 것과 같다.마지막으로 종지된 위치를 되돌려 이 결과로 돌아가면 된다.
이렇게 하면 최적화된 거 아니에요?죄송합니다. 아직 마지막 단계가 남았습니다.우리는 귀속 함수의 위치를 recur, 즉 귀속의 영문recursive의 줄임말로 바꾸어야 한다.

(defn factorial-tail-recursive
    [number result]
    (if (= 1 number)
      result
      (recur (dec number) (* (bigint result) number))))

이렇게 하면 혈액 가득한 버전으로 창고가 넘치지 않고 무한 정밀도를 가지며 곱하기 귀속 함수가 완성된다.
왜 하나recur를 만들어야 합니까?Clojure는 강제로 recur 끝에 두어야 한다고 요구하지 않았습니다. recur 다른 곳에 두면 바로 귀속됩니다. 귀속이 끝난 후에 다음 코드를 계속 실행하지 않습니다.이렇게 하면 더욱 많은 유연성을 제공할 수 있다.
귀환은 함수 세계에서 매우 흔히 볼 수 있는데 표현이 뚜렷하고 코드가 세련될 뿐만 아니라 꼬리 귀환 최적화를 이용하여 귀환 형식도 높은 효율을 가지게 할 수 있다.그러나 꼬리 귀속은 당신이 합리적인 수단으로 정보를 매개 변수의 형식으로 다음 귀속에 전달할 수 있도록 요구한다. 이것은 귀속을 작성하는 어려움을 증가시켰다.만약 네가 범상치 않은 지능도 없고 튼튼한 수학 기초도 없다면 예를 많이 보고 코드를 많이 써라.코드의 양이 높아져야만 너에게 예쁜 귀환을 쓸 수 있는 충분한 경험을 얻을 수 있다.
참고 블로그: zx-dennis, zx-dennis,.
p.s.: 본문 첫머리의 인용도 하나의'귀속'인용이다.(영감은 귀환에서 나온다?)
코드에 있는 값을 직접 죽인다.Clojure는 정수, 문자열, 집합 등 많은 데이터 형식의 글씨체를 제공합니다.↩
사실상 범위가 당신의 메모리 크기에 제한되어 있음을 나타낸다.↩