Оригинальный текст: Working with Functions: Towers of Hanoi by Dave Taylor
Перевод: собственный, вольный с исправлениями.
В этой статье я бы хотел вернуться к основам создания shell-скриптов и рассмотреть работу с функциями. Многие не пользуются ими при написании простых сценариев, так как скрипты часто представляют собой обычную последовательность команд, заключённую в исполняемый файл.
Однако если одни и те же строчки повторяются в программе несколько раз, то использование функций приобретает смысл. Согласно философии структурного программирования, так можно значительно упростить процесс создания и сопровождения сценария.
Синтаксис объявления функции в bash-скрипте выглядит следующим образом:
ИмяФункции{ список команд для исполнения }
Вызвать функцию можно в главном цикле программы или другой функции по имени:
echo "До вызова" ИмяФункции echo "После вызова"
Обращение к передаваемым аргументам происходит так же, как и к аргументам командной строки в основном коде программы: $1, $2, $3 и т.д. Это значит, что в теле функции я бы мог написать:
if [ -n "$1 " ] ; then echo "В функцию было передано $1 в качестве первого аргумента." fi
Узнать число аргументов, переданных в функцию, можно с помощью переменной $#. Тогда предыдущий пример примет вид:
if [ $# -gt 0 ] ; then echo "В функцию было передано $# аргументов." fi
Главное ограничение, которое возникает при использовании функций в shell-скриптах – они могут возвращать только целое число от 0 до 127. При этом, обычно на практике используются только два значения: 0 – при возникновении ошибок и 1 – при удачном завершении. Многие при написании сценариев полностью отказываются от возвращаемого значения и применяют глобальные переменные. Так можно получать из функции даже строки, чего нельзя сделать стандартным способом.
В таких мощных языках как С++, Ruby или Java использовать глобальные переменные в функциях – пример плохого стиля программирования. Однако в этом случае нет другого выхода.
Ханойская башня
Чтобы сделать эту заметку интересней, я рассмотрю работу функций в shell-скриптах на примере классической задачи, которая решается с помощью рекурсии. Программа будет называться ханойская башня и вы наверняка сталкивались с похожими детскими игрушками.
Существует набор дисков разного диаметра и три штырька. Цель – переместить все диски с одного крайней шпильки на другой, при этом нельзя положить больший диск на меньший. Если пронумеровать штырьки как 0, 1, и 2, то простейший способ решить эту задачу с одним диском – переложить его с 0 на 2. Если рассматривать вариант с двумя дисками, то необходимо переложить меньший с 0 на 1, затем диск большего диаметра с 0 на 2, и закончить ходом с 1 на 2.
Алгоритм для N дисков можно выразить с помощью простого shell-сценария:
#!/bin/sh read –ep "Ханойская башня. Сколько в ней дисков? " disks for (( x=1; x < ( 1 << $disks ); x++ )) ; do i=$((($x & $x - 1 ) % 3)) j=$(((($x | $x - 1 ) + 1 ) % 3)) echo "Перемещение с башни $i на $j" done
После запуска исполняемого файла будет показано пошаговое решение:
Получается, что решение для N дисков состоит из 2^N – 1 шаг. Для 20 дисков потребуется 1_048_577 перемещений.
Рекурсия в функциях shell-скриптов в Linux
Смысл предыдущего примера – познакомить с постановкой задачи и показать, насколько элегантно она может решаться с помощью рекурсии.
Основной алгоритм работы программы состоит из трёх шагов:
- Перемещаем верхние диски с исходной позиции на временную.
- Перемещаем самый большой диск с исходной позиции на целевую.
- Перемещаем верхние диски с временной позиции на исходную.
В интернете можно найти много наглядных примеров, которые бы демонстрировали принцип работы этого алгоритма. Посмотрим же на мою реализацию:
#!/bin/sh moves=0 hanoi(){ if [ $1 -gt 0 ] ; then hanoi "$(($1 - 1))" $2 $4 $3 echo “Перемещение $2 --> $3” moves=$(($moves + 1)) hanoi "$(($1 - 1))" $4 $3 $2 fi } read –ep "Ханойская башня. Сколько в ней дисков? " disks hanoi $disks 1 2 3 echo "Для решения потребовалось $moves перемещений."
Для начала работы рекурсивной функции необходимо передать четыре аргумента:
hanoi $disks 1 2 3
Это количество дисков и обозначения шпилек, которые будут использоваться. Результат выполнения скрипта для 4 дисков и трёх пронумерованных башен:
Понадобилось 15 шагов для решения задачи. Кроме того, для запуска рекурсивной функции можно использовать строки для именования позиций:
hanoi $disks "Исходная" "Временная" "Целевая"
Это сделает немного понятней процесс исполнения скрипта. Пример для трёх дисков:
Конечно, вам может никогда не потребоваться на практике использовать рекурсию в своих скриптах. Обычные функции часто эффективней и легче для понимания, но всегда стоит рассматривать и рекурсивный вариант решения задачи.
