Пълно изчерпване
Целта на този урок е на студентите да се демонстрират прости, но важни идеи за писане на рекурсивни функции, като : всяка рекурсивна функция си има база и обикновено от базата започва написването на рекурсивната функция; обикновено за всяка рекурсивна фунцкия може да се посочи аргументът, по който "се осъществява" рекурсията, т.е. чиято стойност с всяко следващо рекурсивно извикване задължително се приближава до базата, което гарантира завършването на функцията.
Хубаво е преди да се премине към пълното изчерпване да се провери дали студентите разбират достатъчно добре най-простите примери за рекурсивни функции като факториел и числата на фибоначи, както и да се нарисуват някакви схеми на оценки на извиквания на тези функции.
Задача 1. Да се дефинира функция
void place (bool desk[3][3], int n)
която поставя n на брой шахматни топове (офицери, коне, царици и др.) върху шахматната дъска 3x3.
Най-удачно е задачата да се реши с достатъчно количество помощни функции, което значително ще съкрати кода на основната функция и тя по-лесно ще бъде разбрана. Такива са например printDesk и най-важната free(desk,i,j), която проверява дали на дадена позиция може да бъде поставена съответната шахматна фигура без това да доведе до конфликт. Да се посочи как поведението на шахматната фигура се контролира именно от free и как задачата се решава за всички шахматни фигури само с промяна на free.
Хубаво е да се дадат някакви допълнителни обяснения, тъй като често се случва пълното изчерпване да е изцяло нова идея. Например нещо от рода на "ако аз знам как да поставя 1 топ, а имам приятел, който знае как да намери всички конфигурации от 3, то на мен ми остава само да поставям топа на всички възможни места и да моля приятеля си да се справя с останалите 3".
Задача 2. Да се дефинира процедура
void place(int desk[3][3])
която разполага във всички клетки на desk някое от числата 1,2,3, така че на никой ред и никоя колона да няма еднакви числа. Функцията да печата всички възможни такива конфигурации.
Най-удобно е тази задача да се реши чрез съответните модификации в решението на горната, за да се види тяхното сходство. Тук базата на рекурсията има по-скрит вид, т.е. няма явна проверка "достигната ли е базовата стойност на еди-кой си аргумент". Тук "намаляващият аргумент" е неявен и е всъщност броят на свободните места на дъската.