소개
꼬리 호출 재귀
리스트, 비트스트링, 문자열처럼 열거 가능한 값들을 재귀로 순회할 때는 흔히 두 가지가 걱정돼요.
- 재귀 함수 호출의 흔적을 담아 두는 데 메모리가 얼마나 필요한지
- 해답을 효율적으로 만들어 내는 방법
이런 걱정거리를 해결하기 위해 _누산기_를 사용할 수 있어요.
누산기는 데이터와 함께 덧붙여 전달되는 변수예요. 함수 실행의 현재 상태를 호출이 이어질 때마다 다음 호출로 넘겨주는 데 쓰이고, 기저 사례에 도달하면 그 누산기로 재귀 호출의 최종 값을 반환해요.
누산기는 함수를 사용하는 사람이 아니라 함수를 작성하는 사람이 초기화해야 해요. 그러려면 함수를 두 개 선언해요. 필요한 데이터만 인자로 받아서 누산기를 초기화하는 공개 함수 하나와, 누산기도 함께 받는 비공개 함수 하나예요. Elixir에서는 비공개 함수 이름 앞에 do_를 붙이는 것이 흔한 패턴이에요.
# Count the length of a list without an accumulator
def count([]), do: 0
def count([_head | tail]), do: 1 + count(tail)
# Count the length of a list with an accumulator
def count(list), do: do_count(list, 0)
defp do_count([], count), do: count
defp do_count([_head | tail], count), do: do_count(tail, count + 1)
누산기를 사용하면 재귀 함수를 꼬리 재귀 함수로 바꿀 수 있어요. 함수에서 _마지막_으로 실행되는 것이 자기 자신을 호출하는 것이라면, 그 함수는 꼬리 재귀 함수예요.
지침
DNA 연구실에서 저장 공간을 절약하려고 연구 데이터를 압축하는 여러 방법을 연구해 왔어요. 그러던 중 한 동료가 DNA 데이터를 이진 표현으로 변환하자고 제안해요.
| 핵산 |
코드 |
| 공백 |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
이렇게 하면 필요한 데이터 저장 비용이 절반으로 줄어들 수도 있지만, 그 대신 사람이 읽기는 어려워져요. 이 점을 곱씹어 보다가, 절약 효과를 측정해 보려고 데이터를 인코딩하고 디코딩하는 모듈을 작성하기로 해요.
1. 핵산을 이진 값으로 인코딩하기
encode_nucleotide/1 함수를 구현해요. 핵산의 코드 포인트를 받아 인코딩된 코드의 정수 값을 반환해요.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. 이진 값을 핵산으로 디코딩하기
decode_nucleotide/1 함수를 구현해요. 인코딩된 코드의 정수 값을 받아 핵산의 코드 포인트를 반환해요.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. DNA charlist 인코딩하기
encode/1 함수를 구현해요. 핵산과 공백을 나타내는 charlist를 받아 인코딩된 데이터의 bitstring을 반환해요.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. DNA bitstring 디코딩하기
decode/1 함수를 구현해요. 핵산과 공백을 나타내는 bitstring을 받아 디코딩된 데이터를 charlist로 반환해요.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
학습 연습 문제
