Вступ
Хвостова рекурсія
Коли ми застосовуємо рекурсію до перелічуваних колекцій, таких як масиви, бітові рядки чи рядки тексту (англ. string), часто постають дві проблеми:
- скільки памʼяті потрібно, щоб зберегти ланцюжок рекурсивних викликів функції
- як ефективно побудувати рішення
Щоб упоратися з цими проблемами, можна використати акумулятор.
Акумулятор - це змінна, яку передають додатково до даних. Його використовують, щоб передавати поточний стан виконання функції від одного виклику до іншого, доки не буде досягнуто базового випадку. У базовому випадку акумулятор використовують, щоб повернути остаточне значення рекурсивного виклику функції.
Ініціалізувати акумулятори має автор функції, а не її користувач. Щоб цього досягти, оголосимо дві функції: публічну, яка приймає лише потрібні дані як аргументи й ініціалізує акумулятор, і приватну, яка також приймає акумулятор. В 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)
Використання акумулятора дає змогу перетворити рекурсивні функції на хвостово-рекурсивні. Функція є хвостово-рекурсивною, якщо останнє, що вона виконує, - це виклик самої себе.
Вказівки
У нашій лабораторії досліджень ДНК ми вже перепробували різні способи стиснення даних досліджень, щоб заощадити місце для зберігання. Один із колег пропонує перетворити дані ДНК на двійкове подання:
| Нуклеїнова кислота |
Код |
| пробіл |
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. Закодувати charlist із ДНК
Реалізуйте encode/1, яка приймає charlist із нуклеїновими кислотами та пропусками і повертає bitstring закодованих даних.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Декодувати bitstring із ДНК
Реалізуйте decode/1, яка приймає bitstring із нуклеїновими кислотами та пропусками і повертає декодовані дані як charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Навчальна вправа
