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

@KOPC1886 · Регистрация: 28.10.2010

Студворк — интернет-сервис помощи студентам

Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо.

@lemegeton · 17.12.2010, 23:47

Сообщение от 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 · 18.12.2010, 11:02

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 · 18.12.2010, 17:25 **[ТС]**

silent_1991, а вот обратно при втором вызове НanoiTowers(int n, int from, int buf, int to) значения опят встают на свои места (то есть 1, 2, 3). Значения опять возвращаются! Я не совсем понимаю как происходит это "обмен". Как переменные записываются в память и как считываются?

silent_1991 · 18.12.2010, 17:42

Да написал же я, обмена никакого нет! У каждой функции будут свои from, buf, to. И при вызове из первой функции (у неё from1 = 1, buf1 = 2, to1 = 3) второй, у второй будут уже свои from2 = 1, buf2 = 3, to2 = 2. И когда мы выйдем из второй функции (которая вывела свои from2, buf2 и to2), её собственные переменные уничтожатся (мы их уже вывели, они нам больше не нужны), а по возвращении в первую функцию она оперирует снова со своими from1, buf1 и to1.

@KOPC1886 · 18.12.2010, 22:41 **[ТС]**

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 · 19.12.2010, 03:30

Что значит "последовательно"? Здесь такого не будет. Тут будет достаточно обширное дерево вызовов, попробуйте на бумажке нарисовать хотя бы для n = 5

@KOPC1886 · 19.12.2010, 15:14 **[ТС]**

Я написал вызов функции для n=4 посмотрите так?

silent_1991 · 20.12.2010, 02:29

KOPC1886, да. Так что вы имели ввиду под "последовательно"?

Новые блоги и статьи Все статьи Все блоги /
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .	мат медиц модель 30. презентация проекта anaschu 27.08.2026 хоп хоп хоп хидахоп, а я кладую))	Как у меня протекала болезнь zorxor 27.08.2026 Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .	Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему kumehtar 26.08.2026 ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352

	Объяснить рекурсию (на примере ханойской башни) 09.12.2010, 20:59. Показов 16195. Ответов 27 Метки нет (Все метки) Кто может объяснить рекурсию? Можно на примере ханойской башне.Заранее спасибо. 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.12.2010, 11:02
	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, вот вам и весь "обмен". Я говорю "обмен" в кавычках, потому что обмена никакого нет, ведь вызванная функция просто получает в качестве параметров с теми же именами, что и вызывающая, перемешанные значения. Не по теме: Тьфу, спасибо случайно жамкнул))) 2

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	18.12.2010, 17:25 [ТС]
	silent_1991, а вот обратно при втором вызове НanoiTowers(int n, int from, int buf, int to) значения опят встают на свои места (то есть 1, 2, 3). Значения опять возвращаются! Я не совсем понимаю как происходит это "обмен". Как переменные записываются в память и как считываются? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	18.12.2010, 17:42
	Да написал же я, обмена никакого нет! У каждой функции будут свои from, buf, to. И при вызове из первой функции (у неё from1 = 1, buf1 = 2, to1 = 3) второй, у второй будут уже свои from2 = 1, buf2 = 3, to2 = 2. И когда мы выйдем из второй функции (которая вывела свои from2, buf2 и to2), её собственные переменные уничтожатся (мы их уже вывели, они нам больше не нужны), а по возвращении в первую функцию она оперирует снова со своими from1, buf1 и to1. 2

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	18.12.2010, 22:41 [ТС]
	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 минуты А как мне тогда преподаватель объяснять, почему и как здесь происходит якобы "обмен" значений? Как объяснить работу этого кода? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	19.12.2010, 03:30
	Что значит "последовательно"? Здесь такого не будет. Тут будет достаточно обширное дерево вызовов, попробуйте на бумажке нарисовать хотя бы для n = 5 1

@KOPC1886 27 / 6 / 0 Регистрация: 28.10.2010 Сообщений: 352
	19.12.2010, 15:14 [ТС]
	Я написал вызов функции для n=4 посмотрите так? Миниатюры 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	20.12.2010, 02:29
	KOPC1886, да. Так что вы имели ввиду под "последовательно"? 0