Форум программистов, компьютерный форум 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 минут все, не надо, сам разобрался. подробнее

Показать сообщение отдельно
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
10.12.2010, 13:14     Объяснить рекурсию (на примере ханойской башни)
Рекурсивная функция-функция ,вызывающая сама себя. Каждое выполнение тела функции имеет свою область стека для параметров и локальных переменных.
Достоинство:создание компактного кода.
Недостатки:затраты времени на вызов функции и передачу ей копий параметров, затраты памяти для организации каждого вложенного вызова.
При этом следует избегать(по возможности) использования локальных переменных в рекурсивной функции.
Например, факториал:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int f(int n)
{
  if(n<=1) return 1;
  else
    {
       int x=f(n-1);
       return n*x;
     }
}
int main()
{
  int n=3;
  int res= f(n);
}
стек при 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

Здесь каждый раз под х приходиться отводить память. В данном случае можно обойтись без локальной переменной. Пример в посте Crudelis
 
Текущее время: 01:07. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru