22.3. Рекурсия без локальных переменных | Популярный Linux

Опубликовано 18.06.2023 автором rootblog.ru
Опубликовано Bash в Ср, 23/12/2009 — 21:04

Функции допускают выполнять рекурсивный вызов даже без использования локальных переменных.

Пример 22-13. Ханойские Башни

  1. #! /bin/bash
  2. #
  3. # Ханойские Башни
  4. # Bash script
  5. # Copyright (C) 2000 Amit Singh. All Rights Reserved.
  6. # <a href=»http://hanoi.kernelthread.com
  7. #
  8. #» title=»http://hanoi.kernelthread.com
  9. #
  10. #»>http://hanoi.kernelthread.com
  11. #
  12. #</a> Тестировался под bash 2.05b.0(13)-release
  13. #
  14. #  Используется в «Advanced Bash Scripting Guide»
  15. #+ с разрешения автора.
  16. #  С небольшими изменениями, внесенными автором документа.
  17. #=================================================================#
  18. #  Ханойские Башни — это древняя математическая головоломка.
  19. #  Дается три вертикальных стержня.
  20. #  На первый нанизан набор колец.
  21. #  Эти кольца представляют собой плоские диски с дыркой по-середине,
  22. #+ так что они могут свободно скользить по стержню.
  23. #  Кольца имеют различный диаметр, и изначально расположены на первом стержне
  24. #+ в порядке убывания их диаметров.
  25. #  Наименьшее кольцо расположено сверху, наиболшее — внизу.
  26. #
  27. #  Суть задачи заключается в том, чтобы перенести кольца с первого
  28. #+ стержня на последний так, чтобы порядок следования колец не изменился.
  29. #  Кольца можно перемещать со стержня на стержень только по одному за раз.
  30. #  Можно помещать кольца обратно на тот же самый стержень.
  31. #  При перемещении нельзя класть больший диск на меньший.
  32. #
  33. #  Для небольшого количества колец требутся некоторое количество перемещений.
  34. #+ Каждое дополнительное кольцо
  35. #+ увеличивает необходимое количество перемещений примерно в два раза,
  36. #+ при этом «стратегия» перемещения усложняется все больше и больше.
  37. #
  38. #  За дополнительной информацией обращайтесь на <a href=»http://hanoi.kernelthread.com.
  39. #
  40. #
  41. #» title=»http://hanoi.kernelthread.com.
  42. #
  43. #
  44. #»>http://hanoi.kernelthread.com.
  45. #
  46. #
  47. #</a>         …                   …                    …
  48. #         | |                   | |                    | |
  49. #        _|_|_                  | |                    | |
  50. #       |_____|                 | |                    | |
  51. #      |_______|                | |                    | |
  52. #     |_________|               | |                    | |
  53. #    |___________|              | |                    | |
  54. #   |             |             | |                    | |
  55. # .—————————————————————.
  56. # |**************************************************************|
  57. #          #1                   #2                      #3
  58. #
  59. #=================================================================#
  60. E_NOPARAM=66  # Сценарий запущен без параметров.
  61. E_BADPARAM=67 # Неверное число колец.
  62. Moves=        # Глобальная переменная, хранит число перемещений.
  63.               # Добавлено в оригинальный сценарий.
  64. dohanoi() {   # Рекурсивная функция.
  65.     case $1 in
  66.     0)
  67.         ;;
  68.     *)
  69.         dohanoi «$(($1-1))» $2 $4 $3
  70.         echo move $2 «—>» $3
  71.               let «Moves += 1»  # Добавлено в оригинальный сценарий.
  72.         dohanoi «$(($1-1))» $4 $3 $2
  73.         ;;
  74.     esac
  75. }
  76. case $# in
  77. 1)
  78.     case $(($1>0)) in     # Как минимум должен быть хотя бы один диск.
  79.     1)
  80.         dohanoi $1 1 3 2
  81.         echo «Всего перемещений = $Moves«
  82.         exit 0;
  83.         ;;
  84.     *)
  85.         echo «$0: Неверное число колец»;
  86.         exit $E_BADPARAM;
  87.         ;;
  88.     esac
  89.     ;;
  90. *)
  91.     echo «Порядок использования: $0 N»
  92.     echo »       Где \»N\» — это число колец.»
  93.     exit $E_NOPARAM;
  94.     ;;
  95. esac
  96. # Упражнения:
  97. # ———
  98. # 1) Будут ли исполнены дополнительные команды, если разместить их ниже этой строки?
  99. #    Почему нет? (Это так просто!)
  100. # 2) Объясните — как работает функция «dohanoi».
  101. #    (А вот это уже сложнее)

Запись опубликована в рубрике Без рубрики. Добавьте в закладки постоянную ссылку.