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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Работа с массивами http://www.cyberforum.ru/cpp-beginners/thread207399.html
Определить значения и адреса элементов массива, вычисляемых по формуле X(катое)=a(катое)/k(факториал).
C++ Матрицы Помогите с программой: Дана квадратная матрица А порядка n. Найти А в четвертой степени http://www.cyberforum.ru/cpp-beginners/thread207390.html
C++ выводит неверный ответ
#include <iostream.h> #include <stdio.h> const int n = 100; int main (int argc, char * const argv) { int x; cout << "введите размер массива "; cin >> x; int mas;
Создать класс C++
Для соответствующего класса, перегрузить арифметические операции(+,-,*,/). При перезгузке арифметические действия должны выполняться относительно только числовых полей!!! Создать несколько объектов класса и проинициализировать их с помощью конструктора с параметрами. Создать несколько дополнительных объектов таким образом, чтобы: - первый объект являлся суммой двух других объектов; - второй...
C++ Абстрактные методы или указатели на функции? http://www.cyberforum.ru/cpp-beginners/thread207345.html
Сабж для класса систем дифференциальных уравнений вида y'=f(x,y) Что лучше: класс с полем указателя на вектор функцию и передача указателя в конструктор, или внутри класса абстрактный метод, а в программе его перекрывать? Оба метода работают. Но какой логичнее и/или лучше?
C++ Как поменять местами элементы вектора ? собственно вопрос совпадает с темой, как поменять местами 2 элемента вектора ? в C++ Добавлено через 25 минут все, не надо, сам разобрался. подробнее

Показать сообщение отдельно
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
16.12.2010, 09:38     Объяснить рекурсию (на примере ханойской башни)
Цитата Сообщение от st_dent Посмотреть сообщение
стек при n=3
||стековый кадр для n=3
||адрес возврата 1
||3
стек при n=2
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3
стек при n=1
||стековый кадр для n=1
||адрес возврата 3
||1
||стековый кадр для n=2
||адрес возврата 2
||2
||стековый кадр для n=3
||адрес возврата 1
||3
может не совсем понятно, суть в том, что в стеке создается несоклько копий одной ф-ции и в каждой копии содержатся разные значения переменных. Например:
C++
1
2
3
4
5
6
int f(int n){
   if(n==1)return n;
   return n+f(--n);//рекурсия
}
//вызываем ф-цию так
f(3);
ф-ция посчитает 3+2+1
Вот как это все выгдядет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int f(n=3){
   if(n==1)return n;
   return n+f(--n);//n не равно 1, поэтому вызываем дальше
}
int f(n=2){
   if(n==1)return n;
   return n+f(--n);//n не равно 1, поэтому вызываем дальше
}
int f(n=1){
   if(n==1)return n;//возвращаем 1
   return n+f(--n);
}
int f(n=2){//значение вернется в копию ф-ции, где n=2
   if(n==1)return n;
   return n+f(--n);//и будет возвращено 2+то, что вернула ф-ция, т.е. 2+1
}
int f(n=3){//в копию, где n=3 возвращено 2+1, т.е. 3
   if(n==1)return n;
   return n+f(--n); будет возвращено 3+3, т.е. 6
}
если после этого не понятно, тогда - практика до посинения )))

Добавлено через 12 часов 39 минут
Есть мысль написать что-то типа FAQ про рекурсию, с очень подробным разъяснением (на низком уровне) и картинками. Если кто-нибудь напишет, что это нужно, вечером напишу.
 
Текущее время: 01:47. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru