Практикум для изучения дисциплины «Основы программирования»
жүктеу/скачать 1,55 Mb. Pdf көрінісі
|
А.А. Тюгашев
| ЗАМЕЧАНИЕ
Чтобы рекурсия не продолжалась вечно, необходима проверка так называемого условия останова рекурсии, или граничного условия. Пример рекурсивного вычисления факториала на языке Си: /* Рекурсивное вычисление факториала */ long int fac(int N) { if (N==0) return 1; if (N>18) {printf(" Слишком большое число!\n\a");return -1;}; return N*fac(N-1); } Через рекурсию определяются знаменитые числа Фибоначчи, менее известные числа Люка и многие другие замечательные математические 42 объекты, что позволяет писать для их вычисления лаконичные и прозрачные по смыслу программы. ЗАМЕЧАНИЕ Часто рекурсивные программы весьма лаконичны, непосредственно передают смысл задачи, изящны по сравнению с решающими ту же задачу итеративными. Любопытно, что формула для прямого вычисления чисел Фибоначчи и Люка тесно связана с понятием золотого сечения, по мнению многих, являющегося воплощением красоты и гармонии. Не связано ли это магическим образом с красотой рекурсивных программ? Следует отметить, что вызов подпрограммы — это некоторое количество дополнительных действий, причем на каждый рекурсивный вызов для запоминания точки возврата требуется некоторое количество оперативной памяти. При чрезмерно большой глубине рекурсии может наступить ошибка типа «переполнение стека вызовов». В отличие от этого поддержка итерации в ЭВМ архитектуры фон Неймана более проста и естественна. В некоторых языках программирования (Кобол, Бейсик, Фортран ранних версий) рекурсивные вызовы запрещены. В других языках, напротив, отсутствует поддержка итерации, и реализовать повторное выполнение одних и тех же действий можно только с использованием рекурсии. Большинство современных языков программирования допускает применение как итерации, так и рекурсии. Конструкции, обеспечивающие итерацию, называются циклическими конструкциями. Примером может служить цикл ПОКА, обеспечивающий выполнение S, пока выполняется логическое условие P. Цикл ПОКА представлен на рис. 5. Рис. 5 43 Действие S1 называют телом цикла. ПОКА еще называют циклом с предусловием. Обратим внимание на следующие важные моменты: Цикл с предпроверкой может быть не выполнен ни разу — в случае, если условие P изначально ложно. При выполнении цикла программа может войти в бесконечное исполнение в случае, если условие P изначально истинно, а выполнение тела цикла не влияет на истинность условия. Эта ситуация называется зацикливанием. Пример на языке Си: /* Умножение на два и печать значения, пока не дойдем до тысячи */ while (a<1000) { a*=2;printf(" уже дошли до a=%d!\n",a); } Пример вычисления факториала с помощью итерации на языке Си: /* Итеративное вычисление факториала */ long int fac(int N) { int i; long F; if (N==0) return 1; if (N>18) {printf(" Слишком большое число!\n\a");return -1;}; i=F=1; while (i<=N) F*=i++; return F; } В языках программирования встречаются и другие виды циклических конструкций. Пример — цикл с постусловием, или цикл ДО. Графически он может быть изображен таким, как на рис. 6. жүктеу/скачать 1,55 Mb. Достарыңызбен бөлісу:
|