Относно: Въведение в програмирането с Java - 10 глава - Рекурсия


2
Здравейте !
Имам проблем с един пример от книгата на Наков, не съм сигурен дали това е правилната категория, във форума, но тъй като не спада към нито една от другите, реших да пиша в общата. Моля да бъде извинен, ако не съм прав.
Относно проблема, не разбирам примера с име: "RecursiveNestedLoops". Дебъгвах кода стъпка по стъпка и доколкото разбрах, функцията "return", връща "currentLoop" да е равна на "1". Не ми е ясно как "counter" след всеки oт "K" си сменя стойността на предишната + 1. Мисля че това има нещо общо с "return", но тъй като не е обяснено какво прави той във "void" метод, не мога да разбера точно как се случва всичко това (въпреки че видях в интернет, че функционира, така че спира метода в определено време). Също и как точно програмата преценя, кога да спре да върти цикъла "counter", след като всеки път цикъла си стига до "numberOfIterations", а "return" го връща и продължава наново...
Благодаря предварително, на отзовалите се ! :)



Отговори



2

Здравей, колега

Като за начало можи би трябва да започна с това какво прави return. Return спира изпълнението на метод и връща дадена стойност. Ако методът е void, т.е. не се очаква да върне нищо, то return се използва само, за да се прекрати методът.

Относно самата задача ще се пробвам да ти я обясня с няколко примерчета.

Нека имаме за N=2 и К=3. В началото влиза в nestedLoops и currentLoop е 0 и се намираме в първия цикъл от задачата (най-външния). Нека да обозначим този метод като (1) и още едно нещо трябва да доуточня, когато говоря за цикъл от задачата ще имам предвид двата цикъла от условието N=2, а само цикъл за цикъла в метода currentLoop. Проверява се условието (0 == 2) не е вярно и влиза в цикъла и counter е 1. Масивът loops е с 2 елемента, колкото са броят на циклите. В него ще се записват всички вариации с два елемента с числата 1, 2, 3. В нулевият индекс се запазва число от първия цикъл от задачата, а в елемента с индекс 1 – число от втория цикъл от задачата.

В нашия случай при първото влизане, когато counter = 1 ще присвоим 1 на нулевият индекс и след това се извиква рекурсивно метода, като се подава параметър със стойност 1 (currentLoops=1). Сега все едно сме влезнали във втория цикъл от задачата. Нека да обозначим този метод като (2).  Проверява се пак условието (1==2), което отново не е вярно и минава към цикъла. При първото влизане counter=1, currentLoop = 1 и следователно loops[1] = 1. Така в масива има следните два елемента loops[0]=1 и loops[1]=1. След което се вика отново рекурсивния метод и вече currentLoop = 2. Нека да обозначим този метод като (3).  Да обаче и numberOfLoops =2 и влиза в тялото на if. Вика метода за печатане и изписва на конзолата 1 1.След като приключи действието на printLoops() се връща в тялото на if-a (метод (3)) и се извиква return. Той прекратява действието на текущия метод nestedLoops и се връща в метод (2). Тук стойностите на променливите бяха следните currentLoop= 1;  и counter = 1. Завърта цикъла и counter става 2 следователно loops[1]= 2 и отново вика метод (3).

Сценарият се повтаря и се отпечатва 1 2. Връща се в метод (2) и завърта цикъла. Аналогично и тук за counter =3. След като отпечата и 1 3 на конзолата отново се връща в метод (2) и завърта цикъла, като counter става 4. Този път условието за прекратяване на цикъла е изпълнено и излиза от него. Програмата продължава да работи и като вижда, че след цикъла няма нищо за изпълнение се връща към цикъл (1). Това е нашият първи цикъл от задачата. В него него имаме currentLoop = 0 и counter=1. Завърта се  цикъла и counter става 2, присвоява се тази стойност на първия елемент от масива loops[0]=2 и се извиква рекурсивно метода (2), като му се подава currentLoop да е 1. Така аналогично на обясненията отгоре ще изпише на конзолата:

2 1
2 2
2 3

Връща се отново в метод (1), завърта се цикъла counter = 3. Следва loops[0] =3 и по същия начин ще отпечата:

3 1
3 2
3 3

Ще се върне в метод (1) ще се завърти цикъла и ще види, че условието за приключване на цикъла е изпълнено ще се върне в main метода и ще приключи програмата.

Доста дълго стана, но дано да схванеш идеята на задачата.

Поздрави и ако има нещо неясно питай.


от Nikolay_Radkov (2911 точки)


0
Благодаря излючително много, това ми помогна наистина да разбера абсолютно всичко, с изключение на една малка подробност, цитирам: "След като отпечата и 1 3 на конзолата отново се връща в метод (2) и завърта цикъла, като counter става 4. Този път условието за прекратяване на цикъла е изпълнено и излиза от него. Програмата продължава да работи и като вижда, че след цикъла няма нищо за изпълнение се връща към цикъл (1). Това е нашият първи цикъл от задачата. В него него имаме currentLoop = 0 и counter=1. Завърта се цикъла и counter става 2."
Кое е условието в програмата, което казва, че не трябва, когато counter = 4, да се възобнови пак и да увеличи числото с индекс 0, което всъщност ако увеличим излизаме от условието на задачата, но просто не мога да разбера как така решава кога да спре. Това е понеже до сега когато съм решавал задачки, сме слагали примерно if(условие) -> break; (чупи цикъла), а тук няма подобно нещо. Как разграничава кога да рестартира counter и кога да приключи ?

от kirev (50 точки)

0
В метода nestedLoops имаш следната сигнатура на цикъла
for (int counter=1; counter<=numberOfIterations; counter++) { ..... }
Самият for цикъл се състои от няколко части - for (първа_част; втора_част; трета_част) {} - Първа част - списък с параметри, които ще се използват в тялото на цикъла и задаване на началните им стойности (int counter=1) - Втора част - условие за приключване на цикъла (counter<=numberOfIterations). Докато то е true (истина/вярно) цикълът ще се завърта. Когато условието стане false (неистина/грешно) то цикълът приключва. В примера, който съм дал условието за приключване е когато counter стане по-голямо от numberOfIterations, което е 3. Затова когато counter е 4 ще излезе от цикъла. Предполагам, че това те интересуваше. - Трета част - промяна на някои от данните след завъртане на цикъла.

от Nikolay_Radkov (2911 точки)



3

Може да си го представиш като ключалка с шифър. В примера от книгата имаш 2 барабана, на които може да сложиш числата от 1 до 4. Как проверяваш всички комбинации? Първо си правиш си функия (nestedLoops), която върти всички числа от 1 до 4 (това е цикъла for от 1 до numberOfIterations). След това пускаш тази функция върху първия барабан (currentLoop = 0). Тя поставя там цифрата 1. След това викаш пак същата функция, но този път върху втория барабан (currentLoop + 1). Тя тръгва от начало и отново слага 1 на втория барабан. Викаш я пак за трети път (currentLoop + 1). Сега вече currentLoop има стойност 2, която е равна на броя барабани numberOfLoops (т.е. нямаш повече барабани) и може да отпечаташ комбинацията (в случая 1-1). И тук идва тънкия момент. Като отпечаташ комбинацията, след return се връщаш обратно там от където си бил извикан, а именно от функцията, която върти втория барабан. Тя си продължава работата, като върти нейния for цикъл и слага цифрата 2. Вика се пак nestedLoops и тя отпечатва следващата комбинация (1,2). По същия начин се отпечатва (1,3) и (1,4). При последното върщане, цикъла for приключва (няма повече цифри) и се връща там от където е бил извикан - а именно от функцията, която върти първия барабан. Тя продължава работата, като слага цифрата 2 на първо място, и отново почва да върти втория барабан, така получаваме (2,1), (2,2), (2,3) и (2,4). И т.н. Всичко приключва, като се изчерят числата за първия барабан. 


от neutrino (3376 точки)


0
Може да погледнеш темите за рекурсията и за комбинаториката от курса по алгоритми.

от svetlin.nakov (31978 точки)