:이 의도처럼 작동꼬리 재귀 방법 2의 제곱을 계산 I는 2의 거듭 제곱 계산 꼬리 재귀 함수 구현하기 위해 노력하고
let rec po2 x =
match x with
| 1 -> 1I
| _ -> po2 (x-1) * 2I
을,하지만 난 내 재귀 호출을 곱 이후 결과는 2입니다.이 코드는 꼬리 재귀가 아닙니다.
이 꼬리를 재귀 적으로 만드는 방법에 대한 아이디어가 있으십니까?
선형 누적 함수는 "accumulator"- "계산 된 누적 값"을 누적하는 thread-through 매개 변수를 사용하여 꼬리 재귀 함수로 바뀔 수 있습니다. 일반적으로 스택 메모리를 힙 메모리로 교환해야합니다 ("지금까지의"값인 어딘가에). "지금까지"값을 저장하지 않고 저장할 수있는 경우도 있습니다. 그것의 일부.
let rec po2Cached acc x =
match x with
| 0 -> acc
| x -> po2Cached (acc*2l) (x-1)
(I 생략 한 단순의 메모이 제이션 부분)
추신 : 귀하의 경우에, 당신이 정말로 저장 할 필요가 마지막 곱셈이 아니라 곱셈의 전체 역사의 결과입니다 이 기능은 부정적인 출력에 대해 잘못된 결과를 생성합니다.
그래서 기본적으로 계산을 매개 변수 목록으로 이동하여 아래에서 위쪽으로 반환 값을 위에서 아래로 구성합니까? –
@ LucaFülbier - 누산기로 재귀 함수를 생각해 볼 수있는 좋은 방법은 아직 보지 못했다면 그들을 무의미한 루프로 만든 함수 ('while true'와 같이)로 정신적으로 변환하는 것입니다. 새로운 값으로 함수를 다시 호출하는 조건은'let acc = acc * 2l; x = x - 1; continue '이며, tail-recursive 함수를 다시 호출하지 않고 값을 생성하는 일치 조건은'return (value)'과 같습니다. 루프를 종료하고 함수를 종료합니다. – rmunn
귀하의 질문은 실제로 메모 작성에 관한 것이 아니지만 실제로이 예제에서 아무것도 캐시하지 않았 음을 참고하는 것이 좋습니다. 또한 인덱스가 (부호없는) 정수가되고 캐시가 항상 전체 범위를 포함하는 경우 캐시를 목록으로보다 효율적으로 저장할 수 있습니다. – mweerden
내 원래 기능을 잘라내는 동안 내 부분은 잘랐다. 사실 나는 불필요하게 문제를 복잡하게하기 때문에 모든 메모 작성 부분을 제거 할 것입니다. –