Рекурсивный вызов Фибоначчи - PullRequest
Новая
       24

Рекурсивный вызов Фибоначчи

0 голосов
/ 10 ноября 2018

Сколько раз метод fib вызывается для fib (6). где метод FIB 

public static long fib(long index) {
    if (index == 0) // Base case
      return 0;
    else if (index == 1) // Base case
      return 1;
   else // Reduction and recursive calls
     return fib(index - 1) + fib(index - 2);
      }
}

В итоге я отслеживаю рекурсивный вызов, чтобы узнать, сколько раз вызывался этот метод, но это непрактично. Имеет ли это функцию закрытой формы, где вы заменяете проверенное значение, чтобы узнать, сколько рекурсивных вызовов вы получите?

Обратите внимание, что это был вопрос на моем предыдущем экзамене (экзамен написан). Я знаю, что мог бы использовать переменную count. Извините, что не упомянул об этом в первую очередь. Вот почему я спрашиваю, есть ли для него функция закрытой формы.

Ответы [ 4 ]

0 голосов
/ 10 ноября 2018

Создайте целочисленную переменную в вашей главной функции, public static int count = 0;. Затем, но эта переменная в вашей рекурсивной функции показана ниже: 

`public static long fib(long index) {
     count ++;
     if (index == 0) // Base case
       return 0;
     else if (index == 1) // Base case
       return 1;
      else // Reduction and recursive calls
       return fib(index - 1) + fib(index - 2);}`
0 голосов
/ 10 ноября 2018

Одним из вариантов может быть добавление статического счетчика в ваш содержащий класс: 

public class YourFib {
    private static int counter;

    public static long fib(long index) {
        ++counter;
        if (index == 0) // Base case
            return 0;
        else if (index == 1) // Base case
            return 1;
        else // Reduction and recursive calls
            return fib(index - 1) + fib(index - 2);
    }

    public static void main(String[] args) {
        counter = 0;
        fib(6l);
        System.out.println("There were " + counter + " recursive calls.");
    }
}

Кстати, вычисление последовательности Фибоначчи с использованием рекурсии серьезно неоптимально. Вы должны прочитать о динамическом программировании, например, о том, что каждый уровень нужно вычислять только один раз.

0 голосов
/ 10 ноября 2018

Вы можете использовать что-то вроде этого, 

public class A {
    private static int count = 0;

    public static void main(String[] argv) {

        System.out.println(fib(6));
        System.out.println(count);
    }

    public static long fib(long index) {
        count++;
        if (index == 0) // Base case
            return 0;
        else if (index == 1) // Base case
            return 1;
        else // Reduction and recursive calls
            return fib(index - 1) + fib(index - 2);
    }
}
0 голосов
/ 10 ноября 2018

Вы можете передать какой-то счетчик в качестве дополнительного параметра, который увеличивается при каждом вызове функции: 

class Counter {
    private int value = 0;
    public void increment() {
      value++;
    }

    public int getCurrentValue() {
        return value;
    }
}

Чтобы ваш код стал: 

public static long fib(long index, Counter counter) {
   counter.increment();
   if (index == 0) // Base case
       return 0;
   else if (index == 1) // Base case
       return 1;
   else // Reduction and recursive calls
      return fib(index - 1, counter) + fib(index - 2, counter);
   }
}

Вызов: 

Counter counter = new Counter();
fib(6,counter);
counter.getCurrentValue(); //  retrieve the current value which is exactly the number of invocation of fib function
...