Ответ 1
Да, все рекурсивные алгоритмы могут быть преобразованы в итеративные. Рекурсивное решение вашей проблемы - это что-то вроде (псевдокода):
def f(n):
if n == 0: return 1
if n == 1: return 3
return 3 * f(n-1) - f(n-2)
Поскольку вам нужно только помнить предыдущие два выражения для вычисления текущего, вы можете использовать что-то вроде следующего псевдокода:
def f(n):
if n == 0:
return 1
if n == 1:
return 3
grandparent = 1
parent = 3
for i = 2 to n:
me = 3 * parent - grandparent
grandparent = parent
parent = me
return me
Это просто сначала обрабатывает условие "рекурсивного" завершения, затем выполняет итерацию, где он обычно называет себя. На каждой итерации вы вычисляете текущий термин, затем вращаете члены через grandparent и parent.
Нет необходимости держать бабушку и дедушку, как только вы вычислили текущую итерацию, поскольку она больше не используется.
На самом деле можно сказать, что итеративное решение лучше (с точки зрения производительности), поскольку термины не пересчитываются, поскольку они находятся в рекурсивном решении. Рекурсивное решение имеет определенную элегантность, хотя (обычно рекурсивные решения).
Конечно, как и последовательность Фибоначчи, это значение, которое вы вычисляете, быстро растет, поэтому, если вы хотите, чтобы, пожалуй, самое быстрое решение (вы должны проверить все требования к производительности, включая мои), предварительно рассчитанная таблица поиска может быть способом идти.
Используя следующий код Java для создания таблицы с длинными значениями (условие while - это всего лишь хитроумный трюк, чтобы перехватить переполнение, то есть точку, в которой вы можете остановить построение массива):
class GenLookup {
public static void main(String args[]) {
long a = 1, b = 3, c;
System.out.print ("long lookup[] = { " + a + "L, " + b + "L");
c = 3 * b - a;
while ((c + a) / 3 == b) {
System.out.print (", " + c + "L");
a = b; b = c; c = 3 * b - a;
}
System.out.println (" };");
}
}
дает вам определение массива, которое вы можете просто подключить к функции поиска, как показано в следующем примере:
public static long fn (int n) {
long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
498454011879264L, 1304969544928657L, 3416454622906707L,
8944394323791464L, 23416728348467685L, 61305790721611591L,
160500643816367088L, 420196140727489673L, 1100087778366101931L,
2880067194370816120L, 7540113804746346429L };
if ((n < 1) || (n > lookup.length))
return -1L;
return lookup[n-1];
}
Интересно, что WolframAlpha предлагает формульный подход, который даже не использует итерацию. Если вы перейдете на их сайт и введите f(0)=1, f(1)=3, f(n)=3f(n-1)-f(n-2), вы получите формулу:
К сожалению, это может быть не так быстро, как итерация, учитывая ограниченное количество входных значений, которые приводят к чему-то, что может поместиться в Java long, поскольку оно использует с плавающей точкой. Это почти наверняка (но, опять же, вам нужно будет проверить это) медленнее, чем поиск в таблице.
И, вероятно, он идеален в мире математики, где реальные ограничения, такие как бесконечное хранилище, не вступают в игру, но, возможно, из-за пределов точности IEEE, он разбивается при более высоких значениях n.
Следующие функции эквивалентны этому выражению и поисковому решению:
class CheckWolf {
public static long fn2 (int n) {
return (long)(
(5.0 - 3.0 * Math.sqrt(5.0)) *
Math.pow(((3.0 - Math.sqrt(5.0)) / 2.0), n-1) +
(5.0 + 3.0 * Math.sqrt(5.0)) *
Math.pow(((3.0 + Math.sqrt(5.0)) / 2.0), n-1)
) / 10;
}
public static long fn (int n) {
long lookup[] = { 1L, 3L, 8L, 21L, 55L, 144L, 377L, 987L, 2584L, 6765L,
17711L, 46368L, 121393L, 317811L, 832040L, 2178309L, 5702887L,
14930352L, 39088169L, 102334155L, 267914296L, 701408733L,
1836311903L, 4807526976L, 12586269025L, 32951280099L, 86267571272L,
225851433717L, 591286729879L, 1548008755920L, 4052739537881L,
10610209857723L, 27777890035288L, 72723460248141L, 190392490709135L,
498454011879264L, 1304969544928657L, 3416454622906707L,
8944394323791464L, 23416728348467685L, 61305790721611591L,
160500643816367088L, 420196140727489673L, 1100087778366101931L,
2880067194370816120L, 7540113804746346429L };
if ((n < 1) || (n > lookup.length)) return -1L;
return lookup[n-1];
}
Теперь нам нужна ссылка для сравнения:
public static void main(String args[]) {
for (int i = 1; i < 50; i++)
if (fn(i) != fn2(i))
System.out.println ("BAD: " + i + ": " + fn(i) + ", " + fn2(i)
+ " (" + Math.abs(fn(i) - fn2(i)) + ")");
else
System.out.println ("GOOD: " + i + ": " + fn(i) + ", " + fn2(i));
}
}
Это выведет:
GOOD: 1: 1, 1
GOOD: 2: 3, 3
GOOD: 3: 8, 8
GOOD: 4: 21, 21
GOOD: 5: 55, 55
GOOD: 6: 144, 144
GOOD: 7: 377, 377
GOOD: 8: 987, 987
GOOD: 9: 2584, 2584
GOOD: 10: 6765, 6765
GOOD: 11: 17711, 17711
GOOD: 12: 46368, 46368
GOOD: 13: 121393, 121393
GOOD: 14: 317811, 317811
GOOD: 15: 832040, 832040
GOOD: 16: 2178309, 2178309
GOOD: 17: 5702887, 5702887
GOOD: 18: 14930352, 14930352
GOOD: 19: 39088169, 39088169
GOOD: 20: 102334155, 102334155
GOOD: 21: 267914296, 267914296
GOOD: 22: 701408733, 701408733
GOOD: 23: 1836311903, 1836311903
GOOD: 24: 4807526976, 4807526976
GOOD: 25: 12586269025, 12586269025
Хорошо смотрим здесь, еще несколько:
GOOD: 26: 32951280099, 32951280099
GOOD: 27: 86267571272, 86267571272
GOOD: 28: 225851433717, 225851433717
GOOD: 29: 591286729879, 591286729879
GOOD: 30: 1548008755920, 1548008755920
GOOD: 31: 4052739537881, 4052739537881
GOOD: 32: 10610209857723, 10610209857723
GOOD: 33: 27777890035288, 27777890035288
GOOD: 34: 72723460248141, 72723460248141
GOOD: 35: 190392490709135, 190392490709135
GOOD: 36: 498454011879264, 498454011879264
Но тогда что-то начинает срываться:
BAD: 37: 1304969544928657, 1304969544928658 (1)
BAD: 38: 3416454622906707, 3416454622906709 (2)
BAD: 39: 8944394323791464, 8944394323791472 (8)
BAD: 40: 23416728348467685, 23416728348467705 (20)
BAD: 41: 61305790721611591, 61305790721611648 (57)
BAD: 42: 160500643816367088, 160500643816367232 (144)
BAD: 43: 420196140727489673, 420196140727490048 (375)
Тот факт, что приведенное выше мучительно близко, и что число цифр в ошибке пропорционально количеству цифр в результате, указывает на то, что это, вероятно, проблема потери точности.
После этой точки формульная функция только начинает возвращать максимальное длинное значение:
BAD: 44: 1100087778366101931, 922337203685477580 (177750574680624351)
BAD: 45: 2880067194370816120, 922337203685477580 (1957729990685338540)
BAD: 46: 7540113804746346429, 922337203685477580 (6617776601060868849)
И тогда наша функция поиска также ломается, так как числа слишком велики надолго:
BAD: 47: -1, 922337203685477580 (922337203685477581)
BAD: 48: -1, 922337203685477580 (922337203685477581)
BAD: 49: -1, 922337203685477580 (922337203685477581)