Рекурсия Java с двумя переменными

Question

Я пытался выяснить, как будет выглядеть стек этого рекурсивного метода.

public class Apples { 

    public static void main (String [] args) { 
     q1(5); 
    } 

    public static int q1 (int x) { 
     if (x < 1) { 
      System.out.println(x); 
      return 1; 
     } 
     int a = 3 + q1(x/2); 
     int b = 2 * q1(x - 2) + 1; 
     System.out.println(x + ";" + a + ";" + b); 
     return a + b; 
    } 
} 

Но до сих пор, я только думаю, что стек растет в соответствии с х/2:

x=0 returns 1; 
x=1 a=4 b=3  returns 7; 
x=2 a=10 b=3  returns 13; 
x=5 a=16 b=9  returns 19; 

Это, очевидно, ни истинным, ни полным. Пожалуйста, помогите мне понять, как складывается стек.

Answer 1

Теория:

Каждый раз, когда эта функция будет рекурсия вниз q1(x/2) пути первой, пока он не достигнет состояния окончания. Затем будут обрабатываться все ожидающие вызова q1(x-2). Сейчас это становится сложно, на каждом q1(x-2) мы сначала обрабатываем q1(x/2). Таким образом, мы теперь возвращаемся к тому же месту, что и раньше, только один слой вниз, повторяя, пока не обработаем все вызовы q1(x-2) (в последнем слое q1(x/2)).

Один из способов думать о нем, как дерево:

Я только думаю, что стек растет в соответствии с х/2

Вы правы, если по выше вы имеете в виду, что эта функция намного быстрее выполняется в q1(x/2), чем в направлении q1(x-2). Тем не менее, то, что вы говорите, означает, что оно растет в lg (n) мода (lg (n) - основание 2).

Тем не менее, мы по-прежнему необходимо проанализировать другие кадры стека, поэтому мы установили следующее рекуррентное соотношение:

Т (п) = Т (п/2) + T (N-2) + с1

Answer 2

Чтобы узнать фактическое преобразование вызова начать с q1(0), q1(1)...

Я могу помочь вам в q1(2), то вы легко можете попробовать q1(5).

x = -1, q1(-1) => 1 // "q1(-1) => 1" means q1 returns 1 
x = 0, q1(0) => 1 // "q1(0) => 1" means q1 returns 1 

x = 1, a = 3 + q1(0) = 3 + 1 = 4 
     b = 2 * q1(-1) + 1 = 2*1 + 1 = 3 
     q1(1) => 7 

x = 2, a = 3 + q1(1) = 3 + 7 = 10 
     b = 2 * q1(0) + 1 = 2*1 + 1 = 3 
     q1(2) => 13 

... 

Таким образом, вы можете распечатать q1(2) и вы получите выход 13. Отладка поможет вам лучше понять.

Answer 3

Стек для этой рекурсивной функции будет изначально из-за повторяющихся рекурсивных вызовов, выполненных для вычисления значения a; то есть, мы будем продолжать называть q1(x/2) до x/2 < 1, в этом случае мы достигли базового варианта рекурсии и может просто вернуть 1.

Каждый раз, когда мы вернемся из одного из начальных q1(x/2) вызовов, затем мы должны следовать вызов q1(x-2), который производится для вычисления b.Этот рекурсивный вызов также будет иметь ряд последовательных рекурсивных вызовов для a (поскольку a сначала вычисляется в вашей функции), которые следуют тому же правилу; после возврата каждого из них мы делаем рекурсивный вызов для b, и этот процесс повторяется, пока мы не достигнем базового аргумента во всех ветвях вызовов.

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

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

Надеюсь, эта схема поможет разобраться.

   |     |     | 
       |     |     | 
       |     |     | 
    +--------+ |     |     | 
    | a = | |     |     | 
    | b = | |     |     | 
    +--------+ |     |     | 
    | x = 0 | 
    +--------+ 
    returns 1 

    ^   +--------+ 
     |    | a = | 
     |    | b = | 
     |    +--------+ 
     |  /| x = -1 | 
     |  / +--------+ 
     |  / returns 1 
     |  /
    +--------+/   
    | a = 4 |/   
    | b = 3 |/    
    +--------|    
    | x = 1 |    
    +--------+    
    returns 7     

    ^   +--------+ 
     |    | a = | 
     |    | b = | 
     |    +--------+ 
     |  /| x = 0 | 
     |  / +--------+ 
     |  / returns 1 
     |  /
    +--------+/   
    | a = 10 |/   
    | b = 3 |/    
    +--------+    
    | x = 2 |    
    +--------+    
    returns 13    

    ^   +--------+ 
     |    | a = | 
     |    | b = | 
     |    +--------+ 
     |    | x = 0 | 
     |    +--------+ 
     |    returns 1 
     | 
     |    ^   +--------+ 
     |     |    | a = | 
     |     |    | b = | 
     |     |    +--------+ 
     |     |  /| x = -1 | 
     |     |  / +--------+ 
     |     |  / returns 1 
     |     |  /
     |    +--------+/
     |    | a = 4 |/
     |    | b = 3 |/ 
     |    +--------+ 
     |    | x = 1 | 
     |    +--------+ 
     |    returns 7 
     |     
     |    ^   +--------+ 
     |     |    | a = | 
     |     |    | b = | 
     |     |    +--------+ 
     |     |    | x = 0 | 
     |     |    +--------+ 
     |     |    returns 1 
     |     | 
     |     |    ^   +--------+ 
     |     |     |    | a = | 
     |     |     |    | b = | 
     |     |     |    +--------+ 
     |     |     |  /| x = -1 | 
     |     |     |  / +--------+ 
     |     |     |  / returns 1 
     |     |     |  /
     |     |    +--------+/
     |     |    | a = 4 |/
     |     |    | b = 3 |/ 
     |     |    +--------+ 
     |     |  /| x = 1 | 
     |     |  / +--------+ 
     |     |  / returns 7    
     |     |  /     
     |     | /     
     |    +--------+/      
     |    | a = 10 |/      
     |    | b = 15 |       
     |    +--------+       
     |  /| x = 3 |       
     |  / +--------+       
     |  / returns 25       
     |  /          
    +--------+/          
    | a = 16 |/          
    | b = 51 |/           
    +--------+ |     |     | 
    | x = 5 | |     |     | 
    +--------+ |     |     | 
    returns 67 |     |     | 
       |     |     | 
       |     |     | 
       |     |     | 

У Brofessor хороший теоретический подход, но что-то, что он говорит, немного неточен; когда он говорит, что q1(x/2) рекурсирует быстрее, чем q1(x-2), он означает, что первый быстро достигнет базового блока по сравнению с последним. Подумайте о больших количествах, чем 5. При больших значениях xx/2 намного меньше x-2. Таким образом, корпус x-2 заканчивается тем, что делает намного больше рекурсивных вызовов, чем случай x/2, поэтому вызовы x-2 доминируют над ростом стека.

Например, у q1(64) будет 7 рекурсивных вызовов для q1(x/2) (64/2, 32/2, ..., 1/2 = 0). Но у него будет так много рекурсивных вызовов для q1(x-2) (64-2, 62-2, 60-2, ..., 2-2 = 0).

В его чертеже было бы более реалистичным, если бы правильное поддерево было больше, потому что это поддерево займет намного больше времени. Фактически, это можно увидеть на моей диаграмме. Если вы считаете вертикальные и диагональные стрелки ветвями дерева, поддерево для самого первого рекурсивного вызова с использованием x/2 имеет только 5 узлов, а поддерево для самого первого рекурсивного вызова с использованием x-2 имеет 7 узлов. Это почти всегда будет иметь место.