/  
 ДОКУМЕНТІВ 
20298
    КАТЕГОРІЙ 
30
Про проект  Рекламодавцям  Зворотній зв`язок  Контакт 

Рекурсивні означення та підпрограми, Детальна інформація

Тема: Рекурсивні означення та підпрограми
Тип документу: Реферат
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 0
Скачувань: 756
Скачати "Реферат на тему Рекурсивні означення та підпрограми"
Сторінки 1   2   3   4   5   6   7  
Реферат на тему:

Рекурсивні означення та підпрограми

1. Рекурсивні означення

Був собі білий бичок. І пішов він у ліс…

З усної народної творчості

Часто кажуть, що рекурсивне означення – це коли щось означається з його ж допомогою. Фраза ця не зовсім точна, а вірніше, зовсім неточна. Кожне означення задає щось, і цим чимось є, як правило, об'єкти, що утворюють деяку множину.

Означення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї ж множини. Об'єкти, задані рекурсивним означенням, також називаються рекурсивними. Нарешті, рекурсія – це використання рекурсивних означень.

Приклади

1. Значення функції "факторіал" задаються виразом: 0!=1, n!=n\xF0D7 (n-1)!. Вони утворюють множину {1,2,6,…}: 0!=1, 1!=1, 2!=2, 3!=6, … . Усі її елементи, крім першого, означаються рекурсивно.

Отже, функція "факторіал" задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Узагалі, будь-яке рекурентне співвідношення порядку k разом із завданням перших k елементів послідовності являє приклад рекурсивного означення.\xF0E7

2. Арифметичні вирази зі сталими та знаком операції '+' у повному дужковому записі (ПДЗ) задаються таким означенням:

1) стала є виразом у ПДЗ;

2) якщо E і F є виразами у ПДЗ, то (E)+(F) також є виразом у ПДЗ.

Такими виразами є, наприклад, 1, 2, (1)+(2), ((1)+(2))+(1). Всі вони, крім сталих, означаються рекурсивно.\xF0E7

Об'єкти, означені в прикладах 9.1–9.2, тобто значення функції "факторіал" та дужкові записи виразів, є рекурсивними.

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

Приклади

3. Змінимо означення функції "факторіал" на таке: n!=n\xF0D7 (n-1)! за n>0, 0!=1!. Спочатку значення функції від 1 виражається через її ж значення від 0, яке, у свою чергу, – через значення від 1. За цим "означенням" так і не дізнатися, чому ж дорівнює 1!.\xF0E7

4. "У попа був собака, піп його любив, той з'їв шматок м'яса, піп його забив, і в землю закопав, і на камені написав, що у попа …" і так далі. Ця сумна історія не має кінця, і не можна сказати, що ж саме піп написав на камені.\xF0E7

5. "– Де ти гроші береш?

– У шухлядці.

– А там вони звідки?

– Дружина кладе.

– А в неї звідки?

– Я даю.

– А де ти береш?

– У шухлядці…"

У цьому старому анекдоті не називається справжнє джерело грошей. Якщо через A, B, C позначити чоловіка, його дружину та шухлядку, то пересування грошей зображається так: A\xF0DF C\xF0DF B\xF0DF A\xF0DF …, і справжнє джерело грошей залишається невідомим.

Щоб подібна "дурна нескінченність" не виникала в рекурсивному означенні, повинні виконуватися умови:

множина означуваних об'єктів є частково упорядкованою;

Сторінки 1   2   3   4   5   6   7  
Коментарі до даного документу
Додати коментар