SLC21 Week4 - Recursia
1 comment
Я планував і цей раз попрацювати з рядками (а отже з циклами та масивами), нагадаю що минулого разу ми познайомилися з рядками, раджу ще раз прочитати минулий урок.
Після того як ви опанували основи програмування, умовний оператор та цикли варто ще згадати про одні "цикли")) Це не зовсім цикли в прямому їх розумінні.
Сьогодні я розповім про рекурсію.
Рекурсія часто складна та незрозуміла тема для новачків. Для більшості з вас буде важко розв'язати задачі на тему рекурсії.
Кажуть що будь-який циклічний алгоритм можна реалізувати через рекурсію, і відповідно рекурсивний алгоритм - через ітеративний. Класичний приклад на якому вивчають рекурсію це обчислення факторіалу.
Що таке факторіал - це добуток послідовних натуральних чисел.
n! = 1*2*3*4*5*6*7*...(n-2)*(n-1)*n, наприклад 3!=6, 3!=123, a 5!=120 =12345
Перше що прийде на думку це запустити цикл для генерації натуральних чисел
for(int k=1; k<=n; k++)
так як факторіал росте дуже швидко то вже на перших десятках обчислене значення буде обмежене типом даних.
Здається вже 33! засобами мови С не обчислити - тому саме друге завдання задам таке: дослідити межу яке найбільше значення факторіалу можна обчислити певним типом даних. У вас має вийти така таблиця
| type | n | n! |
|---|---|---|
| char | 5 | 120 |
| .. | .. | .. |
А як же обчислити факторіал рекурсією? Скільки буде 2+3=? якщо я відповім що це буде 3+2, або 4+1 чи 5+0 - то чим буде моя відповідь? на що вона схожа? Це я намагаюся відійти від відповіді? Чи не знаю сам цю відповідь і так викручуюся?
Скільки буде 5!
Скориставшись вище описаним як можна викрутитися не відповідаючи? тобто дати відповідь, і ніби вірну відповідь....але не остаточну.
Як обчислити 5! - треба обчислити 4! і помножити його на 5.
А як же обчислити 4! - треба обчислити 3! і помножити його на 4.
А як же обчислити 3! - треба обчислити 2! і помножити його на 3.
А як же обчислити 2! - треба обчислити 1! і помножити його на 2.
А як же обчислити 1! - треба обчислити 0! і помножити його на 1.
А як же обчислити 0! - а його обчислювати вже не треба - це буде просто 1
(подумайте чому 0!=1)
Я на цьому прикладі пояснив рекурсію - тобто вирішення задачі, зводиться до вирішення цієї ж задачі але в меншому об'ємі.
Як побудувати триповерховий будинок?
Треба спочатку побідувати 1й поверх а потім якось добудувати решту - 2 поверхи
А як же побудувати ще 2 поверхи?
Треба побудувати другий поверх - а потім якось добудувати решту.
А як же побудувати третій поверх? - а це вже просто зробити, бо він лишився один.
Це було пояснення рекурсії через приклади.
Тобто рекурсія — це спосіб вирішувати складні задачі, звівши їх до аналогічних простіших, доки не досягнеться базовий випадок, який вирішується без рекурсії. Є ще одне жартівливе пояснення рекурсії. "Щоб зрозуміти рекурсію слід спочатку зрозуміти рекурсію".
В мові програмування рекурсія, рекурсивна функція - це функція що викликає сама себе.
void Recursion()
{
Recursion();
}
int main()
{
Recursion();
return 0;
}
Якщо функція викликатиме сама себе - то це ж приведе до зависання, тобто до вічного циклу.
Аналогічно до do ; while(1); або for(;;) або while(1); - це вічні цикли.
Але з рекурсією це не так - вічна рекурсія закінчиться.
Третє завдання - дослідити скільки викликів здійснить функція, перш ніж завершиться. На різних комп'ютерах, системах, компіляторах, налаштуваннях - ця кількість буде різною. Як зробити цю кількість викликів більшою або меншою? Звісно ви не можете зробити точно 12034 викликів))). Але якщо наприклад ви підрахували що на вашій системі вічний рекурсивний виклик здійснив до аварійного завершення 1234 виклики - то як можна цю кількість збільшити/зменшити.
Код класичного обчислення факторіалу
int factorial(int n)
{
if (n == 0) // base case, simple case, no recursion
{
return 1;
}
return n * factorial(n - 1); // recursia call
}
if (n == 0) - ілюструє перше правило - рекурсія має колись закінчитися. Тобто деякий простий, базовий, елементарний випадок обчислення ми виконуємо без рекурсії.
return n * factorial(n - 1); - рекурсивний цикл)) - це я його так назвав - цикл. Але ж рекурсивний виклик повторюється - а отже це цикл)).
Домашнє завдання
Завдання 1. (1b)
Опишіть рекурсію як її зрозуміли. Чи стикалися ви з рекурсією раніше? Як пов'язане слово "фрактал" з рекурсією?
Завдання 2. (1b)
Дослідити межу яке найбільше значення факторіалу можна обчислити певним типом даних. У вас має вийти така таблиця
| type | n | n! |
|---|---|---|
| char | 5 | 120 |
| .. | .. | .. |
Завдання 3. (1b)
Дослідити скільки викликів здійснить функція, перш ніж завершиться. дательніше про це завдання описано в лекції.
Завдання 4. (1b)
Надрукувати числа від 1 до n.
Завдання 5. (1b)
Надрукувати числа від n до 1.
Завдання 6. (2b)
Написати функцію для обчислення суму двох чисел a+b. Не використовувати обчислення a+b безпосередньо. Виконайте спочатку це завдання з допомогою циклу (1бал), можливо це підкаже як тут використати рекурсію і виконати це завдання (1бал)
Завдання 7 (1.5b)
Надрукувати рядок посимвольно(як масив). Пригадайте що при оголошенні рядка char s[]="recursia"; s це не сам рядок - а це адреса його першого символа, адреса масиву. А вивести символ за адресою що зберігається в s можна так printf("%c", s[0]); або printf("%c", *s); - якщо s це адреса масиву символів(рядка), то s[0] це його перший символ. А запис *s означає розіменувати вказівник - тобто отримати значення що розміщене за адресою s
Тим хто знає с++ - тут легше - просто виводите через cout або s[0] або *s. Додам ще одну підказку: якщо s адреса першого символу - то s+1 адреса другого)))
Завдання 8 (1.5b)
Аналогічно попередньому завданню - але рядок треба вивести задом наперед, розвернутим.
Правила проведення
Публікувати можна на будь-якій мові, в будь якій спільноті чи просто у власному блозі, посилання на вашу роботу додайте сюди коментарем
Щоб я швидко знайшов, перевірив та оцінив ваші роботи залиште посилання в коментарі під цим текстом а в роботі поставите тег #slc21w4sergeyk
До всіх завдань код наводити скріншотом, не текстом. Демонструвати теж скріншотом результат роботи програми.
Будьте обережні стосовно ідеальних та надефективних рішень, звичайній людині, початківцю їх не легко найти.
Не надавати рішення задач з допомогою матеріалів, які не вчили. Наприклад масивів, котрі ми ще не вчили. Це обмеження не стосується тих студентів які вже практично знайомі з програмуванням, та надають розширені відповіді на завдання, що більш схоже на лекцію.
Плагіат і використання ШІ заборонено.
Учасники мають бути перевіреними та активними користувачами платформи.
Використані зображення мають належати автору або бути вільними від авторських прав. (Не забудьте вказати джерело.)
Учасники не повинні використовувати будь-які сервіси ботів для голосування, не брати участь у купівлі голосів.
Порекомендуйте прийняти участь своїм друзям.
Роботи слід опублікувати з Monday 18 Nov 24 to Sunday 24 Nov 24
Ваші роботи будуть мною прокоментовані, оцінені та відібрані чотири кращі роботи.
Comments