…aut discede

Декомпозиция

Буквально слово «декомпозиция» означает «разделение на части». В программировании это означает разделение программы на более простые подпрограммы, а те, в свою очередь, – на еще более простые, пока с одной стороны не окажутся простейшие действия сложения, умножения и вычитания, которые исполнитель способен выполнять без дальнейшего объяснения, а с другой – Deep Blue 1) или Mars One 2).

Подпрограмма

В самом простом случае, подпрограмма – это несколько действий вместо одного.

ЕСЛИ условие ТО
  НАЧАЛО
    действие 1
    действие 2
    действие 3
  КОНЕЦ
ИНАЧЕ
  другое действие
  

Процедура

Для именованных подпрограмм используется термин «процедура». Если мы дадим имя подпрограмме, то тем самым обогатим язык исполнителя новой командой, как если бы она изначально была частью языка исполнителя.

ПРОЦЕДУРА другое действие ЭТО
НАЧАЛО
    действие 42
    действие 16
    действие 28
КОНЕЦ

Функция

В программировании функция имеет схожий смысл со своим математическим аналогом. «Звездочка» (знак *) используется для обозначения арифметической операции умножения

ФУНКЦИЯ квадрат (аргумент) ЭТО
НАЧАЛО
  ВЕРНУТЬ аргумент * аргумент
КОНЕЦ

Функция отличается от процедуры двумя особенностями – она получает аргумент и возвращает результат выполнения.

ЕСЛИ квадрат(2) = 4 ТО
  все в порядке
ИНАЧЕ
  мы в другой вселенной

Рекурсия

«Чтобы понять рекурсию, надо сначала понять рекурсию». 3)

Рекурсивным называется алгоритм, который обращается к самому себе. Факториал натурального числа есть произведение всех стоящих перед натуральных чисел 4). Обобщенная формула факториала N! = (N - 1)! * N.

ФУНКЦИЯ факториал (число) ЭТО
НАЧАЛО
  ЕСЛИ число > 0 ТО
    ВЕРНУТЬ число * факториал (число - 1)
  ИНАЧЕ
    ВЕРНУТЬ 1
КОНЕЦ

Это и есть рекурсия. Обратите внимание – это важно! – на условие выхода (0! = 1). Без него рекурсия ушла бы в бесконечность и алгоритм никогда бы не завершился. При написании рекурсивных алгоритмов всегда надо задавать правильное условие выхода.

Фракталы, задача о Ханойских Башнях - тоже рекурсивные задачи. Существует мнение, что все рекурсивные задачи можно решить и другими способами, но - зачем?!

«Итерация свойственна человеку, рекурсия - божественна». 5)
1)
Deep Blue — шахматный суперкомпьютер IBM, который победил в матче против чемпиона мира по шахматам Гарри Каспарова.
2)
Проект колонизации Марса.
3)
Программистский фольклор.
4)
Например, 5! = 1 * 2 * 3 * 4 * 5
5)
Лоренс Питер Дойч.