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

@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, да. Так что вы имели ввиду под "последовательно"?

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .

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

	Объяснить рекурсию (на примере ханойской башни) 09.12.2010, 20:59. Показов 16419. Ответов 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