Здесь приведен перечень рекомендуемого программного обеспечения, которым должны быть оснащены компьютеры курсантов для эффективного обучения. Всё, что здесь перечислено и рекомендовано, по возможности, должно быть установлено и проверено дома заранее во-избежание возможных недоразумений.

Итак, по-порядку:

1. XAMPP, самая популярная среда разработки для Web — Apache+MariaDB+PHP+Perl+инструменты ;
2. FTP-клиент — FileZilla ;
3. Среда для разработки front-end — WebStorm ;
4. Среда для разработки back-end — PHPStorm ;
5. Клиент для работы с различными протоколами — Putty ;
6. Распределённая система контроля версий — Git ;
7. Редактор кода (дело вкуса — кому какой нравится, а лучше поставить все три):
   1. Notepad++ ;
   2. Sublime Text ;
   3. Atom .
8. Графический редактор — PainNet ;
9. Измеритель цвета пикселей — ColorPic ;
10. Экранная линейка — Ruler .
11. Менеджер БД MYSQL — dbForce Studio Express ;
12. Редактор звуковых файлов — Audasity ;
13. Браузеры для тестирования своих приложений:
    1. Firefox Quantum ;
    2. Google Chrome ;
    3. Opera ;
    4. Microsoft Edge ;
    5. 360 Safety Browser .

P.S.

1. Обязательно заведите себе аккаунты на Яндексе и Github, если их ещё нет. Возможно, будем пользовать API Яндекса, а систему контроля версий будем пользовать однозначно.
2. Во время проведения занятий все учебные материалы будут выкладываться на наш Github.

PhpStorm — это профессиональная кросс-платформенная среда разработки от компании [[JetBrains]] написанная на языке JAVA. Это по настоящему мощная и компактная IDE предназначенная для программирования на таких языках как: [[PHP]] и [[JavaScript]]. Эта среда будет нашим основным инструментов для блока Back-end разработки Web-систем.

Как показывает многолетняя практика, если решить все 1052 задачи из книги Задачи по программированию, то можно приобрести уверенность в таком деле, как программирование, и смело браться за решение коммерческих задач. Но это для особо усердных и тех кому программирование действительно нравится, тех кто хочет сделать программирование своей работой. Завидуйте им.

Здесь для практики предлагается всего лишь 101 задача, которые приведены ниже, для упражнений на PHP и каждому необходимо их решить самостоятельно.

Для продуктивных консультаций коды решений всех задач сохраняете в своих аккаунтах на github.

Задачи для самостоятельной работы

Линейные алгоритмы

1. Нарисуйте блок-схему к следующей задаче: Преобразовать дату в «компьютерном» представлении (системную дату) в «российский» формат, т.е. день/месяц/год (например, 17/05/2009).
   Постановка задачи: Системная дата имеет вид 2009-06-15. Нужно преобразовать это значение в строку, строку разделить на компоненты (символ→разделитель→дефис), потом из этих компонентов сконструировать нужную строку.
2. Даны действительные числа А, В, С. Найти максимальное и минимальное из этих чисел.
3. Известны длины трёх сторон треугольника. Вычислить периметр треугольника и площадь (указание: [[формула Герона]], использовать модуль math и функцию sqrt ()).
4. Задан вес в граммах. Определить вес в тоннах и килограммах.
5. Известен объем информации в байтах. Перевести в килобайты, мегабайты.
6. Определить значение функции Z=1/(XY) при X и Y не равных 0.

Ветвления и оператор выбора

7. Дано натуральное число. Определить, будет ли это число: чётным, кратным 4.
8. Дано натуральное число. Определить, будет ли это число: нечётным, кратным 5.
9. Дано натуральное число. Определить, будет ли это число: нечётным, кратным 7.
10. Дано натуральное число. Определить, будет ли это число: чётным, кратным 10.
11. Имеется коробка со сторонами: A × B × C. Определить, пройдёт ли она в дверь с размерами M × K.
12. Дано вещественное число. Определить, какое это число: положительное, отрицательное, ноль.
13. Можно ли из бревна, имеющего диаметр поперечного сечения D, выпилить квадратный брус шириной A?
14. Можно ли в квадратном зале площадью S поместить круглую сцену радиусом R так, чтобы от стены до сцены был проход не менее K?
15. Дан номер места в плацкартном вагоне. Определить, какое это место: верхнее или нижнее, в купе или боковое.
16. Известна денежная сумма. Разменять её купюрами 500, 100, 10 и монетой 2 руб., если это возможно.
17. Имеются две ёмкости: кубическая с ребром A, цилиндрическая с высотой H и радиусом основания R. Определить, поместится ли жидкость объёма M в первую ёмкость, во вторую, в обе.
18. Имеются две ёмкости: кубическая с ребром A, цилиндрическая с высотой H и радиусом основания R. Определить, можно ли заполнить жидкостью объёма M первую ёмкость, вторую, обе.
19. Даны вещественные числа: X, Y, Z. Определить, существует ли треугольник с такими длинами сторон и, если существует, будет ли он прямоугольным.
20. Дано число X. Определить, принадлежит ли это число заданному промежутку [a,b].
21. Определить значение функции Z = 1/(XY ) при произвольных X и Y .
22. Даны вещественные числа: A, B, C. Определить, выполняются ли неравенства A < B B > C и какое именно неравенство выполняется.
23. Даны двещественные числа X и Y . Вычислить Z. Z = √(X x Y) при X > Y, Z = ln(X + Y ) в противном случае.
24. Даны вещественные положительные числа a, b, c, d. Выясните, может ли прямоугольник со сторонами a,b уместиться внутри прямоугольника со сторонами c,d так, чтобы каждая сторона внутреннего прямоугольника была параллельна или перпендикулярна стороне внешнего прямоугольника.
25. Дано вещественное число A. Вычислить f(A), если f(x) = x² + 4x + 5, при x ≤ 2; в противном случае f(x) = 1/(x² + 4x + 5).
26. Дано вещественное число A. Вычислить f(A), если f(x) = 0, при x ≤ 0; f(x) = x при 0 < x < 1, в противном случае f(x) = x⁴.
27. Дано вещественное число A. Вычислить f(A), если f(x) = 0 при x ≤ 0; f(x) = x² − x при 0 < x < 1, в противном случае f(x) = x² − sin(πx²).
28. Составить алгоритм и программу для реализации логических операций «И» и «ИЛИ» для двух переменных.
29. Известен ГОД. Определить, будет ли этот год високосным, и к какому веку этот год относится

Указание. При вычислении корней и логарифмов используйте функции sqrt() и log() модуля math. В этом же модуле определена константа pi (math.pi).

Циклические алгоритмы. Обработка последовательностей и одномерных массивов

30. Составьте блок-схему поиска максимального элемента в одномерном массиве.
31. Нарисуйте полную блок-схему алгоритма сортировки массива «методом пузырька».
32. Дан одномерный массив числовых значений, насчитывающий N элементов. Поменять местами элементы, стоящие на чётных и нечётных местах: A[1] ↔ A[2]; A[3] ↔ A[4] …
33. Дан одномерный массив числовых значений, насчитывающий N элементов. Выполнить перемещение элементов массива по кругу вправо, т. е. A[1] → A[2]; A[2] → A[3]; … A[n] → A[1].
34. Дан одномерный массив числовых значений, насчитывающий N элементов. Поменять местами первую и вторую половины массива.
35. Дан одномерный массив числовых значений, насчитывающий N элементов. Поменять местами группу из M элементов, начинающихся с позиции K с группой из M элементов, начинающихся с позиции P.
36. Дан одномерный массив числовых значений, насчитывающий N элементов. Вставить группу из M новых элементов, начиная с позиции K.
37. Дан одномерный массив числовых значений, насчитывающий N элементов. Сумму элементов массива и количество положительных элементов поставить на первое и второе место.
38. Дан одномерный массив числовых значений, насчитывающий N элементов.Исключить из него M элементов, начиная с позиции K.
39. Дан одномерный массив числовых значений, насчитывающий N элементов. Исключить все нулевые элементы.
40. Дан одномерный массив числовых значений, насчитывающий N элементов. После каждого отрицательного элемента вставить новый элемент, равный квадрату этого отрицательного элемента.
41. Дан одномерный массив числовых значений, насчитывающий N элементов. Определить, образуют ли элементы массива, расположенные перед первым отрицательным элементом, возрастающую последовательность.
42. Дан одномерный массив числовых значений, насчитывающий N элементов. Определить, образуют ли элементы массива, расположенные перед первым отрицательным элементом, убывающую последовательность.
43. Дан одномерный массив числовых значений, насчитывающий N элементов. Из элементов исходного массива построить два новых. В первый должны входить только элементы с положительными значениями, а во второй — только элементы с отрицательными значениями.
44. Дан одномерный массив числовых значений, насчитывающий N элементов. Добавить столько элементов, чтобы элементов с положительными и отрицательными значениями стало бы поровну.
45. Дан одномерный массив числовых значений, насчитывающий N элементов. Добавить к элементам массива такой новый элемент, чтобы сумма элементов с положительными значениями стала бы равна модулю суммы элементов с отрицательными значениями.
46. Дан одномерный массив числовых значений, насчитывающий N элементов. Дано положительное число T. Разделить это число между положительными элементами массива пропорционально значениям этих элементов и добавить полученные доли к соответствующим элементам.
47. Дан одномерный массив числовых значений, насчитывающий N элементов. Исключить из массива элементы, принадлежащие промежутку [B; C].
48. Дан одномерный массив числовых значений, насчитывающий N элементов. Вместо каждого элемента с нулевым значением поставить сумму двух предыдущих элементов массива.
49. Дан одномерный массив числовых значений, насчитывающий N элементов. Определить, имеются ли в массиве два подряд идущих нуля.
50. Дан одномерный массив числовых значений, насчитывающий N элементов. Подсчитать количество чисел, делящихся на 3 нацело, и среднее арифметическое чисел с чётными значениями. Поставить полученные величины на первое и последнее места в массиве (увеличив массив на 2 элемента).
51. Заданы M строк символов, которые вводятся с клавиатуры. Найти количество символов в самой длинной строке. Выровнять строки по самой длинной строке, поставив перед каждой строкой соответствующее количество звёздочек.
52. Заданы M строк символов, которые вводятся с клавиатуры. Из заданных строк, каждая из которых представляет одно слово, составить одну длинную строку, разделяя слова пробелами.
53. Заданы M строк слов, которые вводятся с клавиатуры. Подсчитать количество гласных букв в каждой из заданных строк.
54. Заданы M строк слов, которые вводятся с клавиатуры (в каждой строке – одно слово). Вводится слог (последовательность букв). Подсчитать количество таких слогов в каждой строке.
55. Заданы M строк слов, которые вводятся с клавиатуры (в каждой строке – одно слово). Вводится слог (последовательность букв). Удалить данный слог из каждой строки.
56. Заданы M строк символов, которые вводятся с клавиатуры. Напечатать все центральные буквы строк нечетной длины.
57. Заданы M строк символов, которые вводятся с клавиатуры. Каждая строка содержит слово. Записать каждое слово в разрядку (вставить по пробелу между буквами).
58. Задана строка символов, в которой встречается символ «.». Поставить после каждого такого символа системное время ПК.
59. Заданы M строк, которые вводятся с клавиатуры. Подсчитать количество пробелов в каждой из строк.
60. Заданы M строк символов, которые вводятся с клавиатуры. Каждая строка представляет собой последовательность символов, включающих в себя вопросительные знаки. Заменить в каждой строке все имеющиеся вопросительные знаки звёздочками.
61. Последовательно вводятся числа. Определить сумму чисел с нечётными номерами и произведение чисел с чётными номерами (по порядку ввода). Подсчитать количество слагаемых и количество сомножителей. При вводе числа 55555 закончить работу.
62. Определить сумму вводимых положительных чисел. Причём числа с нечётными номерами (по порядку ввода) суммировать с обратным знаком, а числа с чётными номерами перед суммированием возводить в квадрат. Подсчитать количество слагаемых. При вводе первого отрицательного числа закончить работу.
63. Даны число P и число H. Определить сумму чисел меньше P, произведение чисел больше H и количество чисел в диапазоне значений P и H. При вводе числа равного P или H, закончить работу.
64. Суммировать вводимые числа, среди которых нет нулевых. При вводе нуля обеспечить вывод текущего значения суммы. При вводе числа 99999 закончить работу.
65. Вводятся положительные числа. Определить сумму чисел, делящихся на положительное число B нацело. При вводе отрицательного числа закончить работу.
66. Для вводимых чисел определить процент положительных и отрицательных чисел. При вводе числа −65432 закончить работу.

Обработка двумерных массивов (матриц)

67. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти наибольший элемент столбца матрицы A, для которого сумма абсолютных значений элементов максимальна.
68. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти наибольшее значение среди средних значений для каждой строки матрицы.
69. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти наименьший элемент столбца матрицы A, для которого сумма абсолютных значений элементов максимальна.
70. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти наименьшее значение среди средних значений для каждой строки матрицы.
71. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Определить средние значения по всем строкам и столбцам матрицы. Результат оформить в виде матрицы из N + 1 строк и M + 1 столбцов.
72. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти сумму элементов всей матрицы. Определить, какую долю в этой сумме составляет сумма элементов каждого столбца. Результат оформить в виде матрицы из N + 1 строк и M столбцов.
73. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти сумму элементов всей матрицы. Определить, какую долю в этой сумме составляет сумма элементов каждой строки. Результат оформить в виде матрицы из N строк и M+1 столбцов.
74. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Определить, сколько отрицательных элементов содержится в каждом столбце и в каждой строке матрицы. Результат оформить в виде матрицы из N + 1 строк и M + 1 столбцов.
75. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Определить, сколько нулевых элементов содержится в верхних L строках матрицы и в левых К столбцах матрицы.
76. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Перемножить элементы каждого столбца матрицы с соответствующими элементами K-го столбца.Аим
77. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Просуммировать элементы каждой строки матрицы с соответствующими элементами L-й строки.
78. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Разделить элементы каждой строки на элемент этой строки с наибольшим значением.
79. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Разделить элементы каждого столбца матрицы на элемент этого столбца с наибольшим значением.
80. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Разделить элементы матрицы на элемент матрицы с наибольшим значением.
81. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Все элементы имеют целый тип. Дано целое число H. Определить, какие столбцы имеют хотя бы одно такое число, а какие не имеют.
82. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Исключить из матрицы строку с номером L. Сомкнуть строки матрицы.
83. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Добавить к матрице строку и вставить ее под номером L.
84. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Найти сумму элементов, стоящих на главной диагонали, и сумму элементов, стоящих на побочной диагонали (элементы главной диагонали имеют индексы от [0,0] до [N,N], а элементы побочной диагонали – от [N,0] до [0,N]).
85. Создать квадратную матрицу A, имеющую N строк и N столбцов со случайными элементами. Определить сумму элементов, расположенных параллельно главной диагонали (ближайшие к главной). Элементы главной диагонали имеют индексы от [0,0] до [N,N].
86. Создать квадратную матрицу A, имеющую N строк и N столбцов со случайными элементами. Определить произведение элементов, расположенных параллельно побочной диагонали (ближайшие к побочной). Элементы побочной диагонали имеют индексы от [N,0] до [0,N].
87. Создать квадратную матрицу A, имеющую N строк и N столбцов со случайными элементами. Каждой паре элементов, симметричных относительно главной диагонали (ближайшие к главной), присвоить значения, равные полусумме этих симметричных значений (элементы главной диагонали имеют индексы от [0,0] до [N,N]).
88. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Исходная матрица состоит из нулей и единиц. Добавить к матрице еще один столбец, каждый элемент которого делает количество единиц в каждой строке чётным.
89. Создать квадратную матрицу A, имеющую N строк и N столбцов со случайными элементами. Найти сумму элементов, расположенных выше главной диагонали, и произведение элементов, расположенных выше побочной диагонали (элементы главной диагонали имеют индексы от [0,0] до [N,N], а элементы побочной диагонали — от [N,0] до [0,N]).
90. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Дан номер строки L и номер столбца K, при помощи которых исходная матрица разбивается на четыре части. Найти сумму элементов каждой части.
91. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Определить, сколько нулевых элементов содержится в каждом столбце и в каждой строке матрицы. Результат оформить в виде матрицы из N + 1 строк и M + 1 столбцов.
92. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Дан номер строки L и номер столбца K, при помощи которых исходная матрица разбивается на четыре части. Найти среднее арифметическое элементов каждой части.
93. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Все элементы имеют целый тип. Дано целое число H. Определить, какие строки имеют хотя бы одно такое число, а какие не имеют.
94. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Исключить из матрицы столбец с номером K. Сомкнуть столбцы матрицы.
95. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Добавить к матрице столбец чисел и вставить его под номером K.
96. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Добавить к элементам каждого столбца такой новый элемент, чтобы сумма положительных элементов стала бы равна модулю суммы отрицательных элементов. Результат оформить в виде матрицы из N + 1 строк и M столбцов.
97. Создать прямоугольную матрицу A, имеющую N строк и M столбцов со случайными элементами. Добавить к элементам каждой строки такой новый элемент, чтобы сумма положительных элементов стала бы равна модулю суммы отрицательных элементов. Результат оформить в виде матрицы из N строк и M + 1 столбцов.

Работа с ассоциативными массивами (таблицами данных)

98. Используя данные таблицы отсортировать блюда по возрастанию цены. Вывести отсортированный вариант списка блюд.

    Блюдо

    Цена

    Борщь

    35

    Котлета

    40

    Каша

    20

    Чай

    3

99. Имеется список учеников и результаты трёх тестов (баллы от 0 до 100).Определить средний балл каждого ученика по трём тестам, вывести список учеников по убыванию среднего балла.
100. Известны данные о количестве мальчиков и девочек в нескольких классах. Отсортировать названия классов по возрастанию процента мальчиков, определить количество классов, в которых мальчиков больше, чем девочек, и вывести названия этих классов отдельно.
101. Решить задачу, связанную с оценкой экономической деятельности группы предприятий на основе известных данных:
     • название предприятий;
     • плановый объем розничного товарооборота;
     • фактический объем розничного товарооборота.

     Требуется определить:

     1. процент выполнения плана каждым предприятием;
     2. количество предприятий, недовыполнивших план на 10% и более;
     3. наименьший плановый товарооборот;
     4. упорядочить предприятия по убыванию планового товара.

Никлаус Вирт, швейцарский ученый-информатик, в 1976 году написал книгу под названием «Алгоритмы + Структуры данных = Программы».

Через 40 с лишним лет это тождество остается в силе. Вот почему соискатели, желающие стать программистами, должны продемонстрировать, что знают структуры данных и умеют их применять.

Практически во всех задачах от кандидата требуется глубокое понимание структур данных. При этом не столь важно, выпускник ли вы (закончили университет или курсы программирования), либо у вас за плечами десятки лет опыта.

Иногда в вопросах на интервью прямо упоминается та или иная структура данных, например, «дано двоичное дерево». В других случаях задача формулируется более завуалированно, например, «нужно отследить, сколько у нас книг от каждого автора».

Изучение структур данных — незаменимое дело, даже если вы просто стараетесь профессионально совершенствоваться на нынешней работе. Начнем с основ.

Что такое структура данных?

Если коротко, структура данных — это контейнер, информация в котором скомпонована характерным образом. Благодаря такой «компоновке», структура данных будет эффективна в одних операциях и неэффективна — в других. Наша цель — разобраться в структурах данных таким образом, чтобы вы могли выбрать из них наиболее подходящую для решения конкретной стоящей перед вами задачи.

Зачем нужны структуры данных?

Поскольку структуры данных используются для хранения информации в упорядоченном виде, а данные — самый важный феномен в информатике, истинная ценность структур данных очевидна.

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

В зависимости от конкретного сценария, данные нужно хранить в подходящем формате. У нас в распоряжении — ряд структур данных, обеспечивающих нас такими различными форматами.

Наиболее распространенные структуры данных

Сначала давайте перечислим наиболее распространенные структуры данных, а затем разберем каждую по очереди:

1. Массивы
2. Стеки
3. Очереди
4. Связные списки
5. Деревья
6. Графы
7. Боры (в сущности, это тоже деревья, но их целесообразно рассмотреть отдельно).
8. Хеш-таблицы

Массивы

Массив — это простейшая и наиболее распространенная структура данных. Другие структуры данных, например, стеки и очереди, производны от массивов.

Здесь показан простой массив размером 4, содержащий элементы (1, 2, 3 и 4).

Каждому элементу данных присваивается положительное числовое значение, именуемое индексом и соответствующее положению этого элемента в массиве. В большинстве языков программирования элементы в массиве нумеруются с 0.

Существуют массивы двух типов:

• Одномерные (такие, как показанный выше)
• Многомерные (массивы, в которые вложены другие массивы)

Простейшие операции с массивами

• Insert — вставляем элемент на позицию с заданным индексом
• Get — возвращаем элемент, занимающий позицию с заданным индексом
• Delete — удаляем элемент с заданным индексом
• Size — Получаем общее количество элементов в массиве

Вопросы по массивам, часто задаваемые на собеседованиях

• Найти второй минимальный элемент массива
• Найти неповторяющиеся целые числа в массиве
• Объединить два отсортированных массива
• Переупорядочить положительные и отрицательные значения в массиве

Стеки

Всем известна знаменитая опция «Отмена», предусмотренная почти во всех приложениях. Задумывались когда-нибудь, как она работает? Смысл такой: в программе сохраняются предшествующие состояния вашей работы (количество сохраняемых состояний ограничено), причем, они располагаются в памяти в таком порядке: последний сохраненный элемент идет первым. Одними массивами такую задачу не решить. Именно здесь нам пригодится стек.

Стек можно сравнить с высокой стопкой книг. Если вам нужна какая-то книга, лежащая около центра стопки, вам сначала придется снять все книги, лежащие выше. Именно так работает принцип [[LIFO]] (Последним пришел — первым вышел).

Так выглядит стек, содержащий три элемента данных (1, 2 и 3), где 3 находится сверху — поэтому будет убран первым:

Простейшие операции со стеком:

• Push — Вставляет элемент в стек сверху
• Pop — Возвращает верхний элемент после того, как удалит его из стека
• isEmpty — Возвращает true, если стек пуст
• Top — Возвращает верхний элемент, не удаляя его из стека

Вопросы о стеке, часто задаваемые на собеседованиях

• Вычислить постфиксное выражение при помощи стека
• Отсортировать значения в стеке
• Проверить сбалансированные скобки в выражении

Очереди

Очередь, как и стек — это линейная структура данных, элементы в которой хранятся в последовательном порядке. Единственное существенное отличие между стеком и очередью заключается в том, что в очереди вместо [[LIFO]] действует принцип [[FIFO]] (Первым пришел — первым вышел).

Идеальный реалистичный пример очереди — это и есть очередь покупателей в билетную кассу. Новый покупатель становится в самый хвост очереди, а не в начало. Тот же, кто стоит в очереди первым, первым приобретет билет и первым ее покинет.

Вот изображение очереди с четырьмя элементами данных (1, 2, 3 и 4), где 1 идет первым и первым же покинет очередь:

Простейшие операции с очередью

• Enqueue() — Добавляет элемент в конец очереди
• Dequeue() — Удаляет элемент из начала очереди
• isEmpty() — Возвращает true, если очередь пуста
• Top() — Возвращает первый элемент в очереди

Вопросы об очередях, часто задаваемые на собеседованиях

• Реализуйте стек при помощи очереди
• Обратите первые k элементов в очереди
• Сгенерируйте двоичные числа от 1 до n при помощи очереди

Связный список

Связный список — еще одна важная линейная структура данных, на первый взгляд напоминающая массив. Однако, связный список отличается от массива по выделению памяти, внутренней структуре и по тому, как в нем выполняются базовые операции вставки и удаления.

Связный список напоминает цепочку узлов, в каждом из которых содержится информация: например, данные и указатель на следующий узел в цепочке. Есть головной указатель, соответствующий первому элементу в связном списке, и, если список пуст, то он направлен просто на null (ничто).

При помощи связных списков реализуются файловые системы, хеш-таблицы и списки смежности.

Вот так можно наглядно изобразить внутреннюю структуру связного списка:

Существуют такие типы связных списков:

• Односвязный список (однонаправленный)
• Двусвязный список (двунаправленный)

Простейшие операции со связными списками:

• InsertAtEnd — Вставляет заданный элемент в конце связного списка
• InsertAtHead — Вставляет заданный элемент в начале (с головы) связного списка
• Delete — Удаляет заданный элемент из связного списка
• DeleteAtHead — Удаляет первый элемент в связном списке
• Search — Возвращает заданный элемент из связного списка
• isEmpty — Возвращает true, если связный список пуст

Вопросы о связных списках, часто задаваемые на собеседованиях:

• Обратите связный список
• Найдите петлю в связном списке
• Возвратите N-ный узел с начала связного списка
• Удалите из связного списка дублирующиеся значения

Графы

Граф — это множество узлов, соединенных друг с другом в виде сети. Узлы также называются вершинами. Пара (x,y) называется ребром, это означает, что вершина x соединена с вершиной y. Ребро может иметь вес/стоимость — показатель, характеризующий, насколько затратен переход от вершины x к вершине y.

Типы графов:

• Неориентированный граф
• Ориентированный граф

В языке программирования графы могут быть двух видов:

• Матрица смежности
• Список смежности

Распространенные алгоритмы обхода графа:

• Поиск в ширину
• Поиск в глубину

Вопросы о графах, часто задаваемые на собеседованиях:

• Реализуйте поиск в ширину и поиск в глубину
• Проверьте, является граф деревом или нет
• Подсчитайте количество ребер в графе
• Найдите кратчайший путь между двумя вершинами

Деревья

Дерево — это иерархическая структура данных, состоящая из вершин (узлов) и ребер, которые их соединяют. Деревья подобны графам, однако, ключевое отличие дерева от графа таково: в дереве не бывает циклов.

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

Вот схема простого дерева и базовая терминология, связанная с этой структурой данных:

Существуют деревья следующих типов:

• [[N-арное дерево]];
• [[Сбалансированное дерево]];
• [[Двоичное дерево]];
• [[Двоичное дерево поиска]];
• [[АВЛ-дерево]];
• [[Красно-черное дерево]];
• [[2—3 дерево]].

Из вышеперечисленных деревьев чаще всего используются двоичное дерево и двоичное дерево поиска.

Вопросы о деревьях, часто задаваемые на собеседованиях:

Найдите высоту двоичного дерева

Найдите k-ное максимальное значение в двоичном дереве поиска

Найдите узлы, расположенные на расстоянии “k” от корня

Найдите предков заданного узла в двоичном дереве

Бор

Бор, также именуемый «префиксное дерево» — это древовидная структура данных, которая особенно эффективна при решении задач на строки. Она обеспечивает быстрое извлечение данных и чаще всего применяется для поиска слов в словаре, автозавершений в поисковике и даже для IP-маршрутизации.

Вот как три слова top (верх), thus (следовательно), and their (их) хранятся в бору:

Слова располагаются в направлении сверху вниз, и зеленые узлы «p», «s» и «r» завершают, соответственно, слова «top», «thus» и «their».

Вопросы о борах, часто задаваемые на собеседованиях:

• Подсчитайте общее количество слов, сохраненных в бору
• Выведите на экран все слова, сохраненные в бору
• Отсортируйте элементы массива при помощи бора
• Постройте слова из словаря, воспользовавшись бором
• Создайте словарь T9

Хеш-таблица

Хеширование — это процесс, применяемый для уникальной идентификации объектов и сохранения каждого объекта по заранее вычисленному индексу, именуемому его «ключом». Таким образом, объект хранится в виде «ключ-значение», а коллекция таких объектов называется «словарь». Каждый объект можно искать по его ключу. Существуют разные структуры данных, построенные по принципу хеширования, но чаще всего из таких структур применяется хеш-таблица.

Как правило, хеш-таблицы реализуются при помощи массивов.

Производительность хеширующей структуры данных зависит от следующих трех факторов:

• Хеш-функция
• Размер хеш-таблицы
• Метод обработки коллизий

Ниже показано, как хеш отображается на массив. Индекс этого массива вычисляется при помощи хеш-функции.

Вопросы о хешировании, часто задаваемые на собеседованиях:

• Найдите симметричные пары в массиве
• Отследите полную траекторию пути
• Найдите, является ли массив подмножеством другого массива
• Проверьте, являются ли массивы непересекающимися

Выше описаны восемь важнейших структур данных, которые определенно нужно знать, прежде чем идти на собеседование по программированию.

Удачи и интересного обучения! 🙂

Источник перевода

PHP — наиболее популярный в мире серверный скриптовый язык. Он прошел большой путь развития от небольших, встраиваемых в код статических HTML страниц, снипетов, до современного языка, на котором разрабатывается большинство современных динамических сайтов.

Однако с ростом сложности и функциональности современных сайтов появилась необходимость структурировать и организовать сам процесс разработки. И PHP-фреймворки стали наиболее естественным решением этой задачи.

Зачем использовать фреймворк

Но прежде чем приступить к обзору 10 фреймворков, которые мы тщательно отобрали и заботливо проанализировали для Вас, давайте поясним, для чего же они собственно нужны и какая от них польза.

Все дело в том, что использование фреймворков:

• Существенно сокращает сроки разработки
• Позволяет писать хорошо структурированный, хорошо документированный и повторно используемый код
• Позволяет создавать масштабируемые, легко расширяемые приложения
• Скрывает от разработчика необходимость заботиться о низкоуровневой безопасности сайта
• Стимулирует следовать шаблону проектирования [[MVC]] (Модель-Представление-Контроллер), позволяющему разделить логику приложения и представление данных
• Способствует применению современных методов программирования, в первую очередь объектно-ориентированного.

Оригинал: 10 ЛУЧШИХ PHP-ФРЕЙМВОРКОВ

При разработке любого программного продукта перед командой разработчиков прежде всего стоит задача грамотного выбора программной платформы, определяющей структуру программной системы.

Для этого нужно учесть достаточно большое количество характеристик, от «как быстро всё будет работать» до «а необходима ли нам эта фича?». И так каждый раз. Именно в моменты мозгового штурма команда сравнивает удобство фреймворка, скорость, набор фич, которые реализованы в нем или в совместимых с ним модулях.

Но какой же всё-таки лучше, быстрее и производительнее?

Разработчики постоянно проводят сравнение фреймворков, чтобы прояснить для себя этот вопрос. Например, в статье Lukasz Kujawa приведено сравнение PHP фреймворков. Одно «но» — статья за 2013 год. А ведь время идёт… Поэтому мы решили провести своё, актуальное сравнение фреймворков.

Для оценки производительности был использован PHP Framework Benchmark. Он предлагает для сравнения множество фреймворков (не только указанных выше), но автор не спешит добавлять в репозиторий новые версии проектов, что, конечно же, печально, хотя и не смертельно. При желании добавить новую версию не сложно. 


Одной из основных целей данной статьи также является попытка практическим путем определить улучшения в производительности и эффективности новых версий PHP. Поэтому тестирование было проведено на РНР 5.6/7.0/7.1

Что будем сравнивать?

Для сравнения были выбраны следующие фреймворки:

• slim-3.0
• ci-3.0
• lumen-5.1
• yii-2.0
• silex-1.3
• fuel-1.8
• phpixie-3.2
• zf-2.5
• zf-3.0
• symfony-2.7
• symfony-3.0
• laravel-5.3
• laravel-5.4
• bluz (версия 7.0.0 — для РНР5.6 и версия 7.4 для РНР7.0 и выше)
• ze-1.0
• phalcon-3.0

Тестирование условно разделено на 4 вида:

• производительность (throughput),
• занимаемая память (memory),
• время выполнения (exec time),
• количество подключаемых файлов (included files).

Методика тестирования и тестовый стенд

Машина, на которой производилось тестирование, обладает следующими характеристиками:

Operation system: Linux Mint 17 Cinnamon 64-bit

php 7.1 / php7.0 / php5.6

Вводим команду git clone https://github.com/kenjis/php-framework-benchmark — и фрейм уже на нашей машине. Поскольку мы использовали Mint, необходимо выполнить настройку: 


# Added
net.netfilter.nf_conntrack_max = 100000
net.nf_conntrack_max = 100000
net.ipv4.tcp_max_tw_buckets = 180000
net.ipv4.tcp_tw_recycle = 1
net.ipv4.tcp_tw_reuse = 1
net.ipv4.tcp_fin_timeout = 10

sudo sysctl -p

Немного о структуре самого php-framework-benchmark:

/benchmarks — содержит bash-скрипты, отвечающие за сбор информации о количестве запросов в секунду (при помощи утилиты ab), количестве информации, сколько времени было потрачено и сколько файлов вызывалось из файла «точки старта».

/lib — директория, в которой находятся файлы, отвечающие за обработку полученной информации после вывода страницы “Hello world”, вывод таблиц с результатами и построение диаграмм.

/output — директория, в которую добавляются логи после выполнения тестирования. Здесь находится по два файла для каждого протестированного файла: .ab.log — лог после работы утилиты ab, и .output — содержит информацию, которая была выведена на экран (обычно это hello world и данные по памяти, времени выполнения, использовавшимся файлам).

Остальные папки — это заготовки фреймов, в которые уже добавлен один контроллер, который вернет строку “hello world” при обращении по URI, составленному по правилам обращения к данному фреймворку.

Для запуска теста сначала нужно настроить фреймворки. Рассмотрим два подхода.

Команда bash setup.sh настроит те фремворки, которые описаны в файле list.sh. Вы можете его редактировать: добавлять и удалять папки для тестирования. То есть конфигурировать так, как вам необходимо.

Командой bash setup.sh fatfree-3.5/ slim-3.0/ lumen-5.1/ silex-1.3/ вы можете установить какие-то отдельные фреймворки, задав их параметрами к команде. В некоторых случаях это удобно, но мы использовали первый подход.

После произведенной настройки фреймворков, мы запустили тестирование при помощи bash benchmark.sh.

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

Для отображения графиков мы воспользовались ссылкой http://localhost/php-framework-benchmark/.

Как вы понимаете, необходимо было произвести настройку Apache и заставить его смотреть в папку с фреймом. Всё это описано в readme, поэтому вопросов не возникает.

Результаты тестирования фреймворков

Каждый раздел имеет структуру, состоящую из двух форм представления результатов.

Первая форма — это наглядный тип представления. Каждая характеристика содержит 4 диаграммы. Каждая диаграмма отображает сравнение фреймворков между собой, плюс накопительная диаграмма. Она была построена при использовании определенной версии РНР. Таким образом можно проследить эволюцию улучшений в PHP и фреймворках.

Вторая форма — это результат тестирования в виде таблицы (хватить наглядности, давайте говорить серьезно — дайте мне больше чисел!).

Производительность (throughput)

Применительно к нашей ситуации, характеристика throughput измеряется в количестве запросов, которые наш фреймворк может обработать в течении секунды. Следовательно, чем выше это число, тем более производительно наше приложение, поскольку оно сможет корректно обрабатывать запросы большого количества пользователей.

Мы получили следующие результаты (запросы в секунду):

* — bluz-7.3.1 не поддерживает php 5.6

Для наглядности построили графики для каждой версии PHP:

PHP5.6:

PHP7.0:

PHP7.1:

Сводная накопительная диаграмма (по фреймворкам):

Занимаемая память (peak memory)

Эта характеристика (в мегабайтах) отвечает за количество занимаемой фреймворком памяти при выполнении поставленной перед ним задачи. Чем меньше данное число, тем лучше для нас и для сервера:

* — bluz-7.3.1 не поддерживает php 5.6

PHP 5.6:

PHP 7.0:

PHP 7.1:

Сводная накопительная диаграмма (по фреймворкам):

Время выполнения

Время выполнения — время, затрачиваемое системой для выполнения поставленной задачи. Измеряется от начала выполнения задачи до выдачи результата системой.

Мы рассмотрели, сколько запросов в секунду может обработать фреймворк, сколько памяти он при этом занимает. Теперь рассмотрим, сколько нам нужно ожидать, чтобы получить ответ от сервера. Чем ниже это значение, тем лучше для нас, да и для нервной системы клиента нашего приложения.

Время приведено в миллисекундах (ms):

PHP 5.6:

PHP 7.0:

PHP 7.1:

Сводная накопительная диаграмма (по фреймворкам):

Подключаемые файлы

Характеристика, отвечающая за количество подключаемых файлов, которые описаны в файле «точки входа» фреймворка. Понятно, что система тратит какое-то время на поиск и подключение. Следовательно, чем меньше файлов, тем быстрее будет осуществляться первый запуск приложения, так как обычно в последующие разы фреймворк работает с кэшем, что ускоряет работу:

Разница в количестве подключаемых файлов между Laravel 5.3 и Laravel 5.4 может показаться странной и дать повод к обсуждениям, спорам и т.п. Спешим разъяснить ситуацию. Как вы знаете, с помощью команды

php artisan optimize --force

в Laravel 5.3 можно сгенерировать файл compiled.php, и тем самым уменьшить количество подключаемых файлов, собрав их в один. Но есть одно «но»: команды для генерации этого файла в Laravel 5.4 больше нет. Разработчик решил удалить эту фичу, так как посчитал (https://github.com/laravel/framework/pull/17003), что для настройки производительности лучше использовать opcache.

Стоит ли обновляться?

Сводные данные по версиям более чем наглядно показывают, какой произойдет прирост производительности и эффективности использования ресурсов при переходе (или изначальном выборе) на новую версию PHP.

При переходе с PHP 5.6 на PHP 7.0 средний прирост производительности составил почти +90%, при этом минимальный прирост производительности составил +33% для Laravel 5.3, а максимум — >200% для Zend Framework 2.5.

Переход с версии 7.0 на 7.1 уже не так шокирует, но всё же в среднем даёт почти 20% прирост производительности.

Сведя все полученные данные по производительности различных версий PHP, получим вот такие «матрасы»:

Забавный факт: Laravel 5.3 показал наименьший прирост производительности при миграции с PHP 5.6 на PHP 7.0, но при этом наибольший прирост при миграции с версии 7.0 на версию 7.1, и как итог — производительность Laravel 5.3 и 5.4 на PHP 7.1 практически одинакова.

Потребление памяти тоже оптимизировали, так что переход с PHP 5.6 на PHP 7.0 позволит вашему приложению потреблять на 30% меньшем памяти.

Обновление с версии 7.0 до версии 7.1 практически не даёт прироста, а в последних Symfony и Laravel так и вовсе уходим в «минус», потому что они начинают чуть больше «кушать».

Осталось ещё посмотреть на время выполнения, и да, тут тоже всё отлично:

• переезд с PHP 5.6 на PHP 7.0 подарит вам ускорение в среднем на 44%.
• переезд с PHP 7.0 на PHP 7.1 подарит вам ускорение ещё на 14%.

Примечание. Тестирование при помощи ab — с чем мы столкнулись

«А что со slim и phpixie» — этот вопрос подтолкнул на расследование поведения утилиты ab при взаимодействии с этими фреймворками.

Выполним тест отдельно для Slim-3.0:

ab -c 10 -t 3 http://localhost/php-framework-benchmark/slim-3.0/index.php/hello/index

Transfer rate: 0.35 [Kbytes/sec] received

Что-то не так — количество запросов в секунду всего 0.4 (!)

ab -c 10 -t 3 http://localhost/php-framework-benchmark/laravel-5.4/public/index.php/hello/index

Transfer rate: 648.83 [Kbytes/sec] received

Дело было в Keep Alive соединении, подробнее можно узнать тут.

“When you make requests with «Connection: keep-alive» the subsequent request to the server will use the same TCP connection. This is called HTTP persistent connection. This helps in reduction CPU load on server side and improves latency/response time.

If a request is made with «Connection: close» this indicates that once the request has been made the server needs to close the connection. And so for each request a new TCP connection will be established.

By default HTTP 1.1 client/server uses keep-alive where as HTTP 1.0 client/server don’t support keep-alive by default.”

Таким образом, тест для Slim должен выглядеть так:

ab -H 'Connection: close' -c 10 -t 3 http://localhost/php-framework-benchmark/slim-3.0/index.php/hello/index

Transfer rate: 693.69 [Kbytes/sec] received

Заключение

Как и стоило ожидать безоговорочным лидером по производительности (но не скорости разработки) является Phalcon. Второе место, — а на самом деле первое среди PHP-фреймворков (а не C, на котором написан исходный код Phalcon) — занимает CodeIgniter 3!

Конечно же, не стоит забывать, что каждому инструменту своё предназначение. Если вы выбираете небольшой и легкий фреймворк и собираетесь написать на нём что-то отличное от простейших приложений или REST API, то, скорее всего, вы столкнётесь с проблемами при расширении функционала. И наоборот — избыточность полнофункциональных, больших фреймворков повлечёт за собой финансовые издержки на содержание хостинга даже для элементарных приложений под большой нагрузкой.

Это тестирование проводилось для того, чтобы убедить/рассказать/укрепить позицию языка РНР версий 7.0 и 7.1 в вашем сознании и в будущих проектах, донести информацию о том, что производительность действительно возросла.

Рефакторинг внутренних структур данных и добавление дополнительного этапа перед компиляцией кода в виде абстрактного синтаксического дерева — Abstract Syntax Tree (AST), — привели к превосходной производительности и более эффективному распределению памяти. Результаты сами по себе выглядят многообещающе: тесты, выполненные на реальных приложениях, показывают, что PHP 7 в среднем вдвое быстрее PHP 5.6, а также использует на 50% меньше памяти во время обработки запросов, что делает PHP 7 сильным соперником для компилятора HHVM JIT от Facebook.

Тесты полностью подтверждают и вдвое ускорившуюся обработку запроса в РНР7, и уменьшенное количество используемой памяти.

Оригинал: Как выбрать тот самый PHP-фреймворк. Сравнительное тестирование

В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.

PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.

Перевод Google из официальной документации по PHP

Содержание

• Понятие рекурсии
• Глубина рекурсии
• Опасности и подводные камни рекурсии
• Рекурсивные алгоритмы на PHP
  • Вычисление последовательности Фибоначчи

Понятие рекурсии

Для начала разберёмся с понятием рекурсии. В общем смысле рекурсия это отображение чего-либо внутри самого себя. Рекурсивные алгоритмы используют рекурсивные функции, обладающие данным свойством.

Существует два варианта реализации рекурсивных функций: простой и сложный. В простом случае рекурсивная функция вызывает саму себя. В сложном — функция вызывает другую функцию, которая вызывает исходную функцию, с которой всё начиналось.

Рассмотрим пример из жизни. Если взять два больших зеркала и поставить их друг напротив друга, то можно увидеть бесконечный коридор из изображений зеркал. Каждое зеркало несёт в себе функцию отражения пространства расположенного перед ним. Поэтому здесь мы имеем пример сложной рекурсии (функция вызывает другую функцию, которая вызывает исходную).

Другим примером можно взять всем хорошо известное детское стихотворение:

У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:

У попа была собака, он её любил,
Она съела кусок мяса, поп её убил,
В землю закопал,
И надпись написал о том, что:

…
Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).

Глубина рекурсии

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

Два примера выше иллюстрируют именно этот случай. Правда в реальном мире, в отличие от мира математических абстракций, всегда есть какие-либо ограничения. Нельзя например бесконечно пересказывать одно и то же стихотворение, так как мы ограничены во времени.

Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.

Опасности и подводные камни рекурсии

Рассмотрим простой пример.

<?php

// Пример бесконечной рекурсии

function foo(){
  return foo();
}

foo();

?>

Здесь функция foo() должна вызывать самое себя до бесконечности. В реальных условиях запуск программы приведёт к Segmentation fault, так как произойдёт переполнение стека вызова в силу ограничений на выделенную под него память. Понимая это следует избегать таких конструкций при разработке.

То же самое касается и примера со сложной рекурсией.

<?php

// Пример сложной бесконечной рекурсии

function foo(){
  return bar();
}

function bar(){
  return foo();
}

foo();

?>

В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно
приведёт к падению программы.

Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.

<?php

// Пример конечной рекурсии

function foo($n){
  if($n < 1)
    return;
  return foo($n-1);
}

foo(100000);

?>

Здесь рекурсивный вызов должен завершиться по достижении степени вложенности n.
На практике при запуске этой программы для больших значений n произойдёт та же самая ошибка переполнения стека. Это так же следует учитывать при обработке больших списков и других структур данных, в которых глубина рекурсии зависит от их размера.

Рекурсивные алгоритмы на PHP

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

Существует множество таких алгоритмов:

• Нахождение факториала
• Вычисление последовательности Фибоначчи
• Поиск максимального элемента в массиве
• Вычисление перестановок Ханойских башен
• Рассчёт вариантов размена суммы монетами
• Рекурсивный обход дерева
• и т.д.

Рассмотрим некоторые из них.

Вычисление последовательности Фибоначчи

Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…

В 1202 году Леонардо Пизанский, известный как Фибоначчи, решая задачу о размножении кроликов, пришёл к открытию рекуррентного соотношения:
Эта последовательность обладает одним замечательным свойством, а именно:
Число Фи, представляет собой золотую пропорцию, которая часто встречается в природе, выражая собой закон гармонии и красоты…

Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:

<?php

// Рекурсивный алгоритм вычисления последовательности Фибоначи

function F($n){
	if($n<=1){
		return 1;
	}
	return F($n-1)+F($n-2);
}

?>

С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:

<?php

// Итеративный алгоритм вычисления последовательности Фибоначчи

function F($n){
  $i=1; $r=1; $l=1; $s=1;
  while($i++<$n){
    $s=$l+$r;
    $l=$r;
    $r=$s;
  }
  return $s;
}

?>

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

Дело в том, что реализация рекурсивного алгоритма “в лоб” обладает одним существенным недостатком. А именно при такой реализации вызов функции для одного и того же аргумента производится многократно. Чтобы это увидеть, нужно внимательно рассмотреть само рекуррентное соотношение.

Повторные вызовы функции с одинаковыми аргументами занимает дополнительное время. Чтобы избежать этого, используют подход восходящего динамического программирования, который состоит в том, что задача разбивается на подзадачи и каждая подзадача решается только один раз. В нашем примере это можно реализовать в виде :

<?php

// Рекурсивный алгоритм Фибоначчи
// с использованием подхода восходящего динамического программирования

function F_recursive($n, $K){
	if($n<=1) {
		return 1;
	} elseif ($K[$n] == 0) {
		$K[$n]=F_recursive($n-1,$K) + F_recursive($n-2,$K);
	}
	return $K[$n];
}

function F($n){
	$K=array_fill(0,$n+1,0);
	return F_recursive($n,$K);
}

?>

Таким образом вызов функций над одним и тем же аргументом производится лишь однажды, в случае повторных вызовов производится обращение к памяти к уже вычисленным значениям. Такой алгоритм выполняется гораздо быстрее, чем его простая реализация. Но всё же при этом он значительно уступает итеративной версии. Вы спросите в чём же дело?

Оказывается, что при рекурсивном вызове функций создаются копии её аргументов в стеке и следовательно дополнительные затраты на время выполнения операций копирования.
Чтобы обойти это, может быть использована парадигма Объектно-Ориентированного Программирования (ООП). К примеру мы можем создать массив внутри объекта, который будет иметь рекурсивный метод, внутри которого будет доступ к этому массиву так, что не потребуется передавать этот массив в качестве параметра для каждого вызова этого метода:

<?php

// Рекурсивный алгоритм Фибоначчи
// с применением Объектно-Ориентированного Подхода

class Fibonachi {
  private $K;

  private function F_recursive($n){
  if($n<=1) {
  	return 1;
  } elseif ($this->K[$n] == 0) {
  	$this->K[$n]=$this->F_recursive($n-1,$this->K) + $this->F_recursive($n-2,$this->K);
  }
  return $this->K[$n];
  }

  // Интерфейс класса
  public function getNumberByIndex($n){
    $this->K=array_fill(0,$n+1,0);
    return $this->F_recursive($n);
  }
}

function F($n){
  $Fibonachi = new Fibonachi();
  return $Fibonachi->getNumberByIndex($n);
}

?>

Время выполнения этой программы уже приближается к времени выполнения программы основанной на итерациях. Но всё же для достаточно больших значений n мы будем иметь отставание рекурсивной версии от его итеративного эквивалента, которое может быть значительным в практическом плане. Тогда же в чём смысл рекурсии спросите вы?

Предлагаю вам пока самостоятельно поразмышлять на эту тему.

Есть материалы отсюда.