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

Объяснить рекурсию (на примере ханойской башни) - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
09.12.2010, 20:59     Объяснить рекурсию (на примере ханойской башни) #1
Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.12.2010, 20:59     Объяснить рекурсию (на примере ханойской башни)
Посмотрите здесь:

C++ Ханойские башни
C++ Написать рекурсивную и нерекурсивную версию задачи о ханойской башне
C++ Отладить программу в VS 2012 (объяснить ошибку в примере из книжки)
Объяснить что такое "раздельная компиляция", что такое "интерфейс класса" и "реализация класса" на примере C++
C++ Не могу понять алгоритм Ханойской башни
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
17.12.2010, 23:47     Объяснить рекурсию (на примере ханойской башни) #21
Цитата Сообщение от Kastaneda Посмотреть сообщение
еще нужно сказать, чего не пишут в сишной лит-ре (по крайней мере я не встречал) в стек так же кладется адрес строки
Это в основном пишут в учебниках по ассемблеру. Там, где учат вызывать подпрограммы. Там же написано, что в стеке еще могут лежать состояния флагов процессора, что, правда, уже совсем бессмысленная в данном контексте информация.
Цитата Сообщение от Kastaneda Посмотреть сообщение
Помним, что по соглашению cdecl данные передаются справа налево, поэтому в стек будут «втолкнуты» (от англ. push) сначала переменная z, потом y, потом x.
Продемонстрируем:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
 
using namespace std;
 
// переменные в стеке оказываются в обратном порядке
void f(int a, int b, int c)
{
        int *p = &c;
        cout << *(p+1) << endl;
        cout << *(p+2) << endl;
}
 
int main(int argc, char *argv[])
{
        f(1, 2, 3);
        return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.12.2010, 11:02     Объяснить рекурсию (на примере ханойской башни) #22
KOPC1886,
А что по-подробнее-то? Ничего не считывается. Вот вы когда вызываете функцию, например, sqrt, в функции main, вы передаёте ей параметр - число. Оно копируется в собственную переменную функции sqrt, там с этой переменной происходят какие-то манипуляции и функция возвращает результат. Так вот тут то же самое, при вызове функции HanoiTowers ей передаются какие-то аргументы, они копируются в собственные переменные функции, она в свою очередь вызывает саму себя (теоретически), но фактически это уже другая функция с другими локальными параметрами, в которые и копируются значения тех параметров, которые этой новой функции передала вызывающая функция. Т.н. "обмен" происходит только потому, что сама вызывающая функция передаёт вызываемой свои же параметры, но в другом порядке. Т.е., например, у нас есть функция HanoiTowers(int n, int from, int buf, int to), и мы изначально вызвали HanoiTowers(10, 1, 2, 3), а она вызвала рекурсивно HanoiTowers(9, 1, 3, 2), т.е. в первой функции from был равен 1, buf - 2, to - 3, а в новой функции стало from - 1, buf - 3, to - 2, вот вам и весь "обмен". Я говорю "обмен" в кавычках, потому что обмена никакого нет, ведь вызванная функция просто получает в качестве параметров с теми же именами, что и вызывающая, перемешанные значения.

Не по теме:

Тьфу, спасибо случайно жамкнул)))

KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
18.12.2010, 17:25  [ТС]     Объяснить рекурсию (на примере ханойской башни) #23
silent_1991, а вот обратно при втором вызове НanoiTowers(int n, int from, int buf, int to) значения опят встают на свои места (то есть 1, 2, 3). Значения опять возвращаются! Я не совсем понимаю как происходит это "обмен". Как переменные записываются в память и как считываются?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.12.2010, 17:42     Объяснить рекурсию (на примере ханойской башни) #24
Да написал же я, обмена никакого нет! У каждой функции будут свои from, buf, to. И при вызове из первой функции (у неё from1 = 1, buf1 = 2, to1 = 3) второй, у второй будут уже свои from2 = 1, buf2 = 3, to2 = 2. И когда мы выйдем из второй функции (которая вывела свои from2, buf2 и to2), её собственные переменные уничтожатся (мы их уже вывели, они нам больше не нужны), а по возвращении в первую функцию она оперирует снова со своими from1, buf1 и to1.
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
18.12.2010, 22:41  [ТС]     Объяснить рекурсию (на примере ханойской башни) #25
silent_1991, а почему, кстати, первый вызов функции происходит так НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)-НanoiTowers(int n, int from, int buf, int to)... до тех пор пока n не стане равным 1? А все остальные вызовы идут последовательно?

Добавлено через 2 часа 24 минуты
А как мне тогда преподаватель объяснять, почему и как здесь происходит якобы "обмен" значений?
Как объяснить работу этого кода?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
19.12.2010, 03:30     Объяснить рекурсию (на примере ханойской башни) #26
Что значит "последовательно"? Здесь такого не будет. Тут будет достаточно обширное дерево вызовов, попробуйте на бумажке нарисовать хотя бы для n = 5
KOPC1886
27 / 6 / 0
Регистрация: 28.10.2010
Сообщений: 352
19.12.2010, 15:14  [ТС]     Объяснить рекурсию (на примере ханойской башни) #27
Я написал вызов функции для n=4 посмотрите так?
Миниатюры
Объяснить рекурсию (на примере ханойской башни)  
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2010, 02:29     Объяснить рекурсию (на примере ханойской башни)
Еще ссылки по теме:

Объяснить на примере работу оператора ветвления if else C++
Объяснить как работает рекурсивная функция и стек вызовов на моем примере C++
C++ Написать программу Ханойские башни, используя рекурсию

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

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
20.12.2010, 02:29     Объяснить рекурсию (на примере ханойской башни) #28
KOPC1886, да. Так что вы имели ввиду под "последовательно"?
Yandex
Объявления
20.12.2010, 02:29     Объяснить рекурсию (на примере ханойской башни)
Ответ Создать тему
Опции темы

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