Результат рекурсивного метода

Question

Я пытаюсь понять этот рекурсивный метод, но даже с отладчиком я не мог придумать что-то, что имеет смысл для меня, поэтому я надеюсь, что кто-то здесь мотивирован, чтобы объяснить мне, что здесь происходит. Я знаю, как рекурсия работает в основном, но способ записи этого метода беспокоит меня. Я знаю условный оператор в java, и я разработал новый код, но все же я его не понимаю, так что я ожидаю здесь.

Каков результат для m (5) И m (15). Как вы его вычислили? Спасибо

Редактировать после ответов. Я сделал таблицу с моими результатами для будущих читателей

m(n)::|0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|... 
result|0|0|1|1|1|2|3|4|6|9|13|19|28|41|60|88|... 

я проверил только результат 15 с моей программой.

public class practice { 

    /** 
    * Try to understand the way this works 
    * @param n 
    * @return 
    */ 
    static long m(long n) { 
     return n <= 1 ? 0 : n == 2 ? 1 : m(n - 1) + m(n - 3); 
    } 

    /** 
    * This is what i tried so far. 
    * @param n 
    * @return 
    */ 
    static long ma(long n) { 

     System.out.println("Method called"); 
     System.out.println("N is: " + n); 
     if (n <= 1) { 
      System.out.println("N<=1: " + n); 
      System.out.println("0 is returned"); 
      return 0; 
     } else if (n == 2) { 
      System.out.println("N==2: " + n); 
      System.out.println("1 is returned"); 
      return 1; 
     } else { 
      System.out.println("Inside ELSE, N is: " + n); 
      return ma(n - 1) + ma(n - 3); 
     } 
    } 

    public static void main(String[] args) { 
     ma(15); 
    } 

} 

Answer 1

писал об этом так, чтобы сделать его более понятным:

m(0) = 0 
m(1) = 0 
m(2) = 1 
m(n) = m(n - 1) + m(n - 3) // n >= 3 

Когда мы знаем значения для m(0), m(1) и m(2), мы можем вычислить любой m(n), где n >= 3, используя m(n - 1) + m(n - 3). Для любого отрицательного входа, то результат равен 0.

Например:

m(3) = m(3 - 1) + m(3 - 3) = m(2) + m(0) = 1 + 0 = 1 
m(4) = m(4 - 1) + m(4 - 3) = m(3) + m(1) = 1 + 0 = 1 
m(5) = m(5 - 1) + m(5 - 3) = m(4) + m(2) = 1 + 1 = 2 

И так далее ...

Answer 2

m(5) = m(4)+m(2) // 5>2, so the third condition 
m(4) + m(2) = m(3)+m(1) + 1 // 4>2, so the third condition 
m(3) + m(1) + 1 = m(2)+m(0) + 0 + 1 // 3>2, so the third condition 
m(2) + m(0) + 0 + 1 = 1 + 0 + 0 + 1 = 2 

Теперь между преобразованиями, m(2) s мгновенно заменяется 1 и m(n<=1) мгновенно заменяется 0. Вот как вы можете анализировать это на бумаге. Компьютер, однако, должен был вычислить m(4) перед вычислением m(2) и добавить результаты в первую строку - это происходит из-за порядка координат в рекурсивных функциях.

Answer 3

Карандаш и бумага, вы друзья.

Есть 3 случая (два из них являются базовыми условиями)

if n <= 1 then return 0 

if n == 2 then return 1 

else recursive call to m(n-1) + m(n-3) 

Так вы знаете, что на каждом рекурсивном вызове мы приближаемся один из базовых условий.

Вот трассировки стека, что происходит на m(5)

       m(5) 
        m(4)   +   m(2) 
     m(3)   +  m(1)   return 1 
m(2)  +  m(0)  return 0 
return 1  return 0 

Добавление все возвращения дает 1 + 0 + 0 + 1 что 2

Так

m(5) == 2 

Answer 4

Метод m в псевдокоде. (Это своего рода Скала/питона смять)

def m (number n) 
    if (n <= 1)  0 
    else if (n == 2) 1 
    else    m(n - 1) + m(n - 3) 

Глядя на это, вы можете увидеть, что все <= 2 является терминальным операция, возвращая 0 или 1 на основе входных данных. Если n> 2, начинается самое интересное. Возьмем, например, n=3. Поскольку 3 больше 2, нам нужно запустить третий if. Когда мы смотрим на эту линию, мы видим, что мы должны вернуть m(n - 1) + m(n - 3). Включение n = 3 в, это выглядит так: m(3 - 1) + m(3 - 3), или, более упрощенно, вот так: m(2) + m(0). Это будет прекращено с 1, потому что ни 2, ни 0 для n приведет к большему звонку m.

Итак, теперь у нас есть то, что мы понимаем, теперь мы можем тренироваться, что m(15) и m(5) вернутся.

Я буду работать только это для 5, поскольку стек вызовов для 15 будет способом долго

    m(5) 
      /   \ 
      m(5-1) + m(5-3) 
     /  \   | 
     m(4-1) + m(4-3)  | 
    /  \  |  | 
    m(3-1) + m(3-3) |  | 
    |  |  |  | 
    1 + 0 + 0 + 1 
       2 

Надеется, что это помогает!