Реализовать функцию вычисления значения Фибоначчи с однократным вызовом рекурсии

Question

Не могу понять как как сделать однократным вызовом рекурсии

public static int fib(int n){
    if (n==1||n==2){ 
        return 1;
    }
  return result=fib(n-1)+fib(n-2);
}

Answer 1

Ваша функция должна возвращать объект с двумя полями: значение n-ного элемента последовательности и n-1

class Pair {
    private final int prev;
    private final int cur;
    public Pair(int prev, int cur) {
        this.prev = prev;
        this.cur = cur;
    }

    public int getPrev() {
        return prev;
    }

    public int getCur() {
        return cur;
    }
}

private static Pair internalFib(int n) {
    if (n == 1) { 
        return new Pair(0, 1);
    }
    Pair prev = internalFib(n - 1);
    return new Pair(prev.getCur(), prev.getPrev() + prev.getCur());
}

public static int fib(int n){
    return (n > 0) ? internalFib(n).getCur() : 0;
}

Answer 2

Можно классическое решение циклом преобразовать в tail-рекурсию:

public static int fib1(int n, int a, int b){
if (n<=2){ 
    return a + b;
}
  return fib1(n-1, b, a + b);
}

public static void main (String[] args) throws java.lang.Exception
{
    for (int i = 1; i < 10; i++) {
            System.out.println(fib1(i, 0, 1));
    }
}

Пример на ideone

Answer 3

Ещё одна реализация хвостовой рекурсии. Идея в том чтобы вычислять результат на аргументах рекурсивного вызова. Если вы всё сделали верно, то код должен выглядеть как-то так:

def tail_rec_func(...):
    ...
    return tail_rec_func(...)

Главное требование: рекурсивный вызов должен быть последним действием в функции перед вызовом return. Обычно такой набор параметров непривычен для пользователя. Поэтому рекурсивная функция fib_iter завёрнута в fib с нормальным интерфейсом. У fib_iter нарочно сделан избыточный интерфейс, чтобы было проще выразить инвариант, который соблюдается при вызовах. В "оптимизированном" виде параметер n отсутствует, а k считает от n - 1 до нуля:

public class FibonacciTailRecursion {
    public static void main(String... args) {
        for (int n = 0; n < 47; ++n) {
            System.out.println("fib(" + n + ") = " +  fib(n));
        }
    }

    public static int fib(int n) {
        if (n == 0) {
            return 0;
        }
        // fib_iter(n, 1, f[0], f[1])
        return fib_iter(n, 1, 0, 1);
    }

    // fib_iter(n, k, f[k - 1], f[k])
    private static int fib_iter(int n, int k, int a, int b) {
        if (k == n) {
            return b;
        }
        // fib_iter(n, k + 1, f[k], f[k + 1] = f[k - 1] + f[k])
        return fib_iter(n, k + 1, b, a + b);
    }
}

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
...
fib(45) = 1134903170
fib(46) = 1836311903

И в конце приманка: числа Фибоначчи можно вычислять ещё быстрее с помощью быстрого возведения в степень. Тоже можно сделать хвостовой рекурсией.

БЛОГ НА HUSL

Реализовать функцию вычисления значения Фибоначчи с однократным вызовом рекурсии

Ответы (3 шт):