Если тебя интересует формальное избавление от рекурсии то не знаю.
Если просто волнует время вычисления, тое сть стандартный способ
Имеем записи
a b f(a,b)
Если нужное нам значение есть в таблице, то берём из таблицы.
Если нужного нам значения нет в таблице, то вычисляем его и заносим в таблицу.
Для данных a, b ни одно значение функции не будет считаться дважды
Время работы и необходимая память (могу ошибаться) О(a+b)
Заметим, что (для неотрицательных a, b) f = { 1,2,3 }.
Поэтому все последние варианты сведутся к вызову функции f(a-1,???) = f(a-2,???) = ... = f(1,???) = 3
Здравствуйте, mihoshi, Вы писали:
M>В машинных кодах нет рекурсии. Соответственно, все рекурсия приводятся к итерация. Естественный образ — с помощью стека.
Можно ввести определение, отличающие рекурсию от итерации.
В итерационных алгоритмах расход памяти — постоянный.
В рекурсивных — динамический; неважно, будет ли задействован стек возвратов или какой-то самодельный.
Итерационные алгоритмы суть конечные автоматы (пусть даже с очень большим количеством состояний).
Рекурсивные — магазинные автоматы.
Разумеется, если рассмотреть машину целиком, то она является автоматом с гигантским количеством микросостояний (2^количество_триггеров_в_памяти_и_процессоре). И поэтому такой подход непродуктивен.
A>Время работы и необходимая память (могу ошибаться) О(a+b)
Для функции Аккермана от трёх аргументов, примерно подобного порядка, для ackr(3,3,8) требуется таблица около 16млн записей, или индекс элементов достигает 16млн, если память не изменяет. В общем, таблично её вычисление ускорить не удалось
Здравствуйте, MikaRSDN Soukhov, Вы писали:
MS>Здравствуйте, MichaelP, Вы писали:
MS>А если я еще раз скажу, что был не прав. Я еще раз ошибся в ф-ии
MS>Вот ее нормальное описание MS>
MS> _
MS> | b + 1 при a = 0
MS>f(a, b)= -| f(a - 1, 1) при b = 0
MS> |_f(a - 1, f(a, b - 1)) в других случаях
MS>
Тогда скажу, что мы с третьей попытки дошли наконец до функции Аккермана , которая специально была придумана как "неизбавимая" от длинной рекурсии .
Я видел решение для своего вида функции Аккермана (трёхпараметрической, формулу на память не помню, но отличается не принципиально) с развёрткой рекурсии в пару циклов. Вот только на VC7 вариант с циклами считался в несколько раз медленнее, чем рекурсивный.
Здравствуйте, Balancer, Вы писали:
MS>>Тоесть, она решаема или не решаема?
B>Я видел решение для своего вида функции Аккермана (трёхпараметрической, формулу на память не помню, но отличается не принципиально) с развёрткой рекурсии в пару циклов. Вот только на VC7 вариант с циклами считался в несколько раз медленнее, чем рекурсивный.
Здравствуйте, MikaRSDN Soukhov, Вы писали:
MS>Здравствуйте, Balancer, Вы писали:
MS>>>Тоесть, она решаема или не решаема?
B>>Я видел решение для своего вида функции Аккермана (трёхпараметрической, формулу на память не помню, но отличается не принципиально) с развёрткой рекурсии в пару циклов. Вот только на VC7 вариант с циклами считался в несколько раз медленнее, чем рекурсивный.
MS>Запостишь?
Несмотря на то, что много воды уже утекло с тех пор, я запостю свой нерекурсивный вариант функции Аккермана в последней (и, наверное, окончательной) постановке.
ak(0, b) = b+1
ak(a, 0) = ak(a-1, 1)
ak(a, b) = ak(a-1, ak(a, b-1))
Этот нерекурсивный вариант работает быстрее рекурсивной реализации "в лоб". Это связано с тем, что не вычисляются лишний раз промежуточные значения. Расход памяти пропорционален параметру a. Для первых четырех значений a можно вывести формулы
ak(0, b) = b+1
ak(1, b) = b+2
ak(2, b) = 2*b+3
ak(3, b) = 2^b-3
Для значений a больших 3, функция Аккермана настолько быстро растет, что врядли, кому-то понадобится ее считать. Хотя, кто знает... может, у кого-то есть формулы в общем виде?
Да, код писался в расчете на удобную верификацию, но доказательство я не привожу (места на полях не хватает).
integer akerman(integer a, integer b) {
struct Item {
integer m_b;
integer m_ak;
};
Item *array = new Item[a+1];
for(integer i=0; i<a; ++i) {
array[i+1].m_b = -1;
array[i+1].m_ak = 1;
}
array[0].m_b = -1;
array[0].m_ak = 0;
while(array[a].m_b != b) {
array[0].m_b++;
array[0].m_ak++;
for(integer i=0; (i != a) && (array[i].m_b == array[i+1].m_ak); ++i) {
array[i+1].m_b++;
array[i+1].m_ak = array[i].m_ak;
}
}
integer result = array[a].m_ak;
delete[] array;
return result;
}