Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
andy2050
0 / 0 / 0
Регистрация: 18.09.2009
Сообщений: 3
#1

Ребята, объясните пожалуйста эту рекурсию! - C++

19.09.2009, 17:45. Просмотров 840. Ответов 7
Метки нет (Все метки)

Ребята, ну хоть убейся не могу понять эту рекурсивную фунцию для задачи с Ханойской башней!
Всё работает отлично, но вот как! Кто может, объясните пошагово, буду очень признателен!

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;
 
int num;
 
void hanoy(int num,char a,char b,char c)
{
if(num>0)
{
hanoy(num-1,a,c,b);
cout<<a<<" -> "<<c<<endl;
hanoy(num-1,b,a,c);
}
 
}
 
int main(){
char a='A',b='B',c='C';
int num;  
  
cout<<"number of rings=";
cin>>num;
 
hanoy(num,a,b,c);
 
system("PAUSE");
return 0;
}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2775 / 1589 / 142
Регистрация: 03.12.2007
Сообщений: 4,162
Завершенные тесты: 1
19.09.2009, 18:02     Ребята, объясните пожалуйста эту рекурсию! #2
Ханойская башня - тут и алгоритм, и ещё рисунок в тему.
andy2050
0 / 0 / 0
Регистрация: 18.09.2009
Сообщений: 3
19.09.2009, 18:51  [ТС]     Ребята, объясните пожалуйста эту рекурсию! #3
алгоритм ясен, вот только рекурсивная функция и её работа в моём коде вообще не понятна!
odip
Эксперт С++
 Аватар для odip
7151 / 3291 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
20.09.2009, 18:43     Ребята, объясните пожалуйста эту рекурсию! #4
Чтобы понять рекурсию нужно сначала понять рекурсию.
just_a_cat
5 / 5 / 1
Регистрация: 16.09.2009
Сообщений: 4
20.09.2009, 23:30     Ребята, объясните пожалуйста эту рекурсию! #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
ты не понимаешь рекурсию вообщем ? или только рекурсию в данной задаче ?
если вообщем, то лучше изучать её на примере вычисления факториала :
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int fact(int N) 
{
           int Res;
    if (N > 1) {
        Res= fact(N-1)*N;
    }
    else {
        Res = 1;
    }
 
    return Res;
}
int main()
{
           cout << factorial(3);
 
           system("pause > nul");
           return 0;
}
для начала попробуем разбить нашу задачу вычисления факториала, на простые подзадачи
C
1
2
//N! = N*(N-1)*(N-2)*...*2*1 = (N-1)!*N
    //(N-1)! = (N-1)*(N-2)*...*2*1
тоесть нам нужно умножить н-1, потом н-1-1, потом н-1-1-1... и так пока н-1 не будет равно 1.
это мы и делаем вот в этой строке,

C
1
Res= fact(N-1)*N;
тоесть мы умножаем результат нашеё функции, на N, чему равен результат функции ? верно, мы не знаем, но мы можем пойти дальше, а потом вернуться.

C
1
Res= fact(N-1)*N;
компилятор смотрит на эту строку и что он делает ? он обращается к функции, только N делает на еденицу меньше, чему бы не было равно N, мы когда нибудь дойдём и оно будет равно еденице. И только когда оно будет равно еденице мы начнём возвращататься на те места с которых мы ушли, то есть мы начнём возвращать наш результат res, и куда же он вернётся ?
ну конечно же туда где мы его последний раз вызывали тоесть в нашу формулу
[C]Res= fact(N-1)*N;[/С]
потом мы снова отрезультируем (вернём результат) и снова вернёмся к формуле, то есть код будет считываться примерно вот так вот


C
1
2
3
4
5
 int fact(int N) 
{
           int Res;
    if (N > 1) {
        Res= fact(N-1)*N;
// fact (N-1) снова вызывает функцию, тоесть
C
1
2
3
4
5
int fact(int N) 
{
           int Res;
    if (N > 1) {
        Res= fact(N-1)*N;
// и так пока N будет больше 1
...................
C
1
2
3
4
5
6
7
8
9
10
11
int fact(int N) 
{
           int Res;
    if (N > 1) { // когда же мы наконец-то сравняем N с 1, то 
        Res= fact(N-1)*N; 
           }    
            else {
        Res = 1;     // мы наконец-то прийдём в эту точку, тоесть присвоем переменной res eдиницу
    }
 
    return Res; //   и вернём её
// а возвращать будем, туда откуда вызывали, тоесть вот сюда:

C
1
2
3
4
5
6
7
    Res= fact(N-1)*N; // только место  fact(N-1) будет наш Res
           }    
            else {                 
        Res = 1;   // сюда мы даже заходить не будем
    }
 
    return Res;  // а сразу пойдём сюда
// и так далее :

C
1
2
3
4
5
6
7
     Res= fact(N-1)*N; 
           }    
            else {                 
        Res = 1;   
    }
 
    return Res;
// пока не вернёмся в самое самое начало, к самому первому вызову.
C
1
2
3
4
5
6
7
 Res= fact(N-1)*N; 
           }    
            else {                 
        Res = 1;   
    }
 
    return Res;
// теперь мы уже будем возвращать рес не в функцию факт, а в инт меин () ...


если ты поймёшь всё то, что я написал выше, то ты должен понять и рекурсию в задаче с Ханойской башней.
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
21.09.2009, 00:49     Ребята, объясните пожалуйста эту рекурсию! #6
что конкретно непонятно с рекурсией?
andy2050
0 / 0 / 0
Регистрация: 18.09.2009
Сообщений: 3
21.09.2009, 13:29  [ТС]     Ребята, объясните пожалуйста эту рекурсию! #7
just_a_cat -> Спасибо огромное за такое тщательное и последовательное объяснение! Ещё раз уложил всё по полочкам. В принципе я знал что нужна базовая задача и задача которая сводится к базовой.
Что мне действительно не понятно в "моём ханойском коде", так это двойная рекурсия, где функция вызывает ещё ту же самую функцию 2 раза... Не могу вьехать в последовательность выполнения этой рекурсии!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.09.2009, 15:04     Ребята, объясните пожалуйста эту рекурсию!
Еще ссылки по теме:

C++ объясните пожалуйста эту программу
C++ объясните пожалуйста эту программу
объясните пожалуйста эту программу C++
C++ Ребята! Пожалуйста, объясните что делает данная программа?
C++ Ребята, объясните пожалуйста каждую строку этой программы

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
just_a_cat
5 / 5 / 1
Регистрация: 16.09.2009
Сообщений: 4
26.09.2009, 15:04     Ребята, объясните пожалуйста эту рекурсию! #8
хм... последовательно ....
ну сначала много раз делаем этот кусок кода (нум=3) :
C
1
2
3
4
5
void hanoy(int num,char a,char b,char c)
{
if(num>0)
{
hanoy(num-1,a,c,b);
запоминаем, передаём, запоминаем, передаём ... нум=0. Мы не проходим на чек поинте вот тут:
C
1
if(num>0)
поэтому возвращаем (возвращаем и нум который равен 1, потому что последний раз когда мы его запоминали он был равен 1) и начинаем делать вот этот кусок:
C
1
2
3
4
cout<<a<<" -> "<<c<<endl;
hanoy(num-1,b,a,c);
}
}
нум будет равно 0, поэтому мы опять обходим чек поинт первый и просто вернём вот суда же:
C
1
2
3
4
cout<<a<<" -> "<<c<<endl;
hanoy(num-1,b,a,c);
}
}
но вернём уже нум=2. То есть, нам таки уже дадут пройти чек поинт смотрим что будет:
C
1
2
3
4
5
void hanoy(int num,char a,char b,char c)
{
if(num>0)
{
hanoy(num-1,a,c,b);
оп и мы снова входим и вызовем функцию как в первый раз, только в этот раз мы будем в ней крутиться не так долго )
и так далее .....
запоминаем, передаём, запоминаем, передаём .... возвращаем, передаём, запоминаем, выводим, передаём, запоминаем, возвращаем ....

P.S. если не понятен чужой код, то советую пошагово его рассматривать, и обращать внимание на изменение переменных. Если после этого ничего не понятно, то можно просто удалить непонятный кусок кода или строку, и смотреть на результат
Yandex
Объявления
26.09.2009, 15:04     Ребята, объясните пожалуйста эту рекурсию!
Ответ Создать тему
Опции темы

Текущее время: 22:52. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru