О структурном программировании

Многие в комментариях к посту об операторе goto высказывали одно и то же мнение, которое звучит примерно так: «За n лет написания программ мне ни разу не понадобился goto, и использовать его в будущем я тоже не собираюсь». И они абсолютно правы, уже давно доказана теорема о структурировании, в которой говорится, что любая простая программа функционально эквивалентна структурированной программе составленной с использованием функций и предикатов исходной программы, а также с использованием дополнительного счетчика. Доказательством является алгоритм составления той самой структурированной программы:

1. пронумеровать все узлы схемы, при этом порядок обхода произвольный;
2. пронумеровать все дуги схемы следующим образом: выходной дуге схемы припишем номер 0, всем остальным дугам присвоим номер вершины, в которую данная дуга входит;
3. для каждого функционального узла исходной программы, имеющего номер i и выходную дугу j, составить новую простую последовательную программу Gi с номером входной дуги i
   
4. для каждого предикатного узла с номером i составить новую простую программу
   
5. построить программу типа while do с do-частью в виде структры, проверяющей значения L.

Итак, если однажды вы напишите что-то вроде этого (программа из поста о goto):

if (p1)
{
	f1;
	goto L3;
}
L1:
if (p2)
{
L2:
	f2;
L3:
	f3;
	goto L1;
}
else if (p3)
{
	f4;
	goto L2;
}
f5;

То лучше перепишите этот код. Ведь не зря один умный человек сказал: «Пишите код так, как будто сопровождать его будет склонный к насилию психопат, который знает, где вы живете». Если учесть что большинство программистов недолюбливают goto, то это более чем актуально.

Воспользуемся теоремой и преобразуем этот код в соответствии с принципами структурного программирования. Сначала составим блок-схему этого алгоритма и пронумеруем блоки и дуги в соответствии с теоремой.



Теперь построим цикл while do с заменой предикатных и функциональных блоков.



Получилась схема структурированной программы, но в ней слишком много лишнего. Преобразуем её в соответствии со следующим алгоритмом:
Для каждого j>0 пытаемся заменить все присваивания L=j соответствующей подпрограммой Gj(в том числе и для L=1). Если L больше никогда не будет присвоено значение j можно убрать проверку L=j (вместе с соответствующей ей веткой выполнения) из структуры программы.



С помощью этой схемы можно легко написать код, соответствующий принципам структурного программирования.

if p1:
    f1
    f3
l = 3
while l > 0:
    if p2:
        f2
        f3
    elif p3:
        f4
        f2
        f3
    else:
        f5
        l = 0;

Или совсем избавиться от флага как это сделал eigrad здесь.

Так же можно было написать рекурсивный код предварительно преобразовав блок-схему программы в так называемую Е-схему.



Код:

def F1():
    if p2:
        F2()
    elif p3:
        f4
        F2()
    else:
        f5

def F2():
    f2
    F3()

def F3():
    f3
    F1()

if p1:
    f1
    F3()
else:
    F1()

Если учесть, что при реальном программировании функции именуются в соответствии с выполняемыми ими действиями, этот код так же становится более читаемым, чем код с использованием goto.

При написании топика использовалась методичка НГТУ «Информатика. Теория и практика структурного программирования.» Т.А.Шапошниковой.

P.S. Спасибо funca за его вопросы и исправления.