АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Алгоритми роботи посадових осіб щодо профілактики суїцидальних проявів
  2. АЛГОРИТМИЗАЦИИ
  3. Алгоритмизация и программирование
  4. Алгоритмизация модели и её машинная реализация
  5. Алгоритмизация процесса разработки и принятия управленческого решения
  6. Алгоритмизация решения задач на компьютере
  7. Глава 3. Основы алгоритмизации и программирования
  8. Какие компоненты образуют алгоритмический язык?
  9. Какие понятия используют алгоритмические языки?
  10. Лекция № 6: Алгоритмизация и программирование
  11. Основні алгоритми роботи з літерними величинами
  12. Основы алгоритмизации и программирования.

 

Алгоритми, що викликають самі себе, називаються рекурсивними.

 

Це означає, що в тілі алгоритму є команда виклику цього алгоритму. У цьому випадку говорять про пряму рекурсію. Але буває і непряма рекурсія. Це така рекурсія, за якої, наприклад, алгоритм А викликає алгоритм В, а він, у свою чергу, викликає алгоритм С, що викликає початковий алгоритм А. Рекурсія широко застосовується в програмуванні, і це невипадково, оскільки багато математичних алгоритмів засновані на рекурсії. Вона дозволяє спростити алгоритм розв’язання завдання, значно зменшити його в розмірах. До того ж, у розв’язанні завдань перебору обійтися без рекурсії дуже складно, а часом навіть неможливо. Водночас треба знати, що для реалізації рекурсивних алгоритмів на комп’ютері треба набагато більше пам’яті, ніж нерекурсивних, тому що при кожному входженні в рекурсію змінним виділяється нова пам’ять.

Перш ніж встановити рекурсивний алгоритм, необхідно створити рекурсивний опис вихідного завдання (рекурсивну постановку завдання). Оскільки виконання рекурсивних алгоритмів здійснюється послідовним чином « занурення – вихід », то рекурсивна постановка завдання має являти собою розвинену схему, що вміщує принаймні два варіанти – під час занурення в рекурсію і під час виходу з неї, з відповідною умовою вибору необхідних дій.

Ось чому правильна постановка завдання є найважливішим моментом у використанні рекурсії для розв’язування завдань.

Обмежимося кількома прикладами алгоритмів із прямою рекурсією, а на прикладі 2 покажемо схему рекурсивного занурення і виходу алгоритму Фібоначчі.

 

Приклад 1. Обчислити значення функції n!

Розв’язання стає очевидним, якщо подати факторіал рекурентним співвідношенням,

Алгоритм-функція має вигляд:

АЛГ ціл fact(ціл n)

ПОЧ ціл f

якщо n=1 або n=0

то f:=1

fact:=f

інакше f:=fact(n – 1)*n

fact:=f

Все

КІН

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.002 сек.)