Вопрос рекурсии английского правителя

Question

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

public static void drawRuler(int nInches, int majorlength)
{
  drawLine(majorLength, 0);
  for (int j =1; j<= nInches, j++)
  {
   drawInterval(majorLength-1);
   drawLine(majorLength, j);
 }
}

private static void drawInterval (int centralLength)
{
 if (centralLength>=1)
 {
  drawInterval(centralLength - 1);
  drawLine(centralLength);
  drawInterval(centrakLength-1);
 }
}

public static void drawLine(int tickLength, int tickLabel)
{
 for (int j=0; j<ticklength; j++)
   System.out.print("-")
 if (tickLabel>=0)
  System.out.print(" "+tickLable);
 System.out.print("\n");
}

private static void drawLine(int tickLength)
{
  drawLine(tickLength, -1);
}

Во-первых, я ввожу nInches = 1 and majorlength 3,

1 - drawLine будет вызываться с (3,0) // длиной тика и меткой тикла

public static void drawLine(3, 0)
    {
     for (int j=0; j<3; j++)
       System.out.print("-")
     if (tickLabel>=0)
      System.out.print(" "+tickLable);
     System.out.print("\n");
    }

вывод:

--- 0

2- Сейчаснижний цикл будет запускаться из функции drawRuler

for (int j =1; j<=1, j++)
      {
       drawInterval(majorLength-1);

* Точка 1: среднее значение над линией вызовет drawInterval (2)? *

drawLine(majorLength, j);
     }

3- Мы переходим кфункция drawInterval с 2 в качестве аргумента

private static void drawInterval (2)
    {
     if (centralLength>=1)   // true
     {
      drawInterval(centralLength - 1);
 **Point 2: what the point of calling same function with 1 ? and will it call itself again without drawing anything? and function will go on nextline after drawInterval become 0?**


drawLine(centralLength);
      drawInterval(centrakLength-1);
     }
    }

Point3: drawLine(tickLength, -1); Почему мы используем это -1?

Answer 1

Кажется, вы взяли свой код из книги Структуры данных и алгоритмы в Java .

Но ваш код даже не компилируется, существует так много синтаксических ошибок и неправильных переменных.Вы получили этот исходный код из книги через scan + OCR, не пытаясь запустить его с Java?

Итак, сначала давайте исправим ошибки и превратим этот фрагментарный код в класс с методом main, не так ли?

package de.scrum_master.stackoverflow;

public class EnglishRuler {
  public static void main(String[] args) {
    drawRuler(2, 4);
  }

  public static void drawRuler(int nInches, int majorLength) {
    drawLine(majorLength, 0);
    for (int j = 1; j <= nInches; j++) {
      drawInterval(majorLength - 1);
      drawLine(majorLength, j);
    }
  }

  private static void drawInterval(int centralLength) {
    if (centralLength >= 1) {
      drawInterval(centralLength - 1);
      drawLine(centralLength);
      drawInterval(centralLength - 1);
    }
  }

  private static void drawLine(int tickLength, int tickLabel) {
    for (int j = 0; j < tickLength; j++)
      System.out.print("-");
    if (tickLabel >= 0)
      System.out.print(" " + tickLabel);
    System.out.print("\n");
  }

  private static void drawLine(int tickLength) {
    drawLine(tickLength, -1);
  }
}

drawRuler(1, 3) отпечатков:

--- 0
-
--
-
--- 1

drawRuler(1, 5) отпечатков:

----- 0
-
--
-
---
-
--
-
----
-
--
-
---
-
--
-
----- 1

drawRuler(2, 4) отпечатков:

---- 0
-
--
-
---
-
--
-
---- 1
-
--
-
---
-
--
-
---- 2

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

package de.scrum_master.stackoverflow;

public class EnglishRuler {
  private static boolean DEBUG = true;
  private static String indent = "";

  public static void main(String[] args) {
    drawRuler(1, 3);
  }

  public static void drawRuler(int nInches, int majorLength) {
    if (DEBUG)
      System.out.println("drawRuler(" + nInches + ", " + majorLength + ")");
    drawLine(majorLength, 0);
    for (int j = 1; j <= nInches; j++) {
      drawInterval(majorLength - 1);
      drawLine(majorLength, j);
    }
  }

  private static void drawInterval(int centralLength) {
    indent += "  ";
    if (DEBUG)
      System.out.println(indent + "drawInterval(" + centralLength + ")");
    if (centralLength >= 1) {
      drawInterval(centralLength - 1);
      drawLine(centralLength);
      drawInterval(centralLength - 1);
    }
    indent = indent.substring(2);
  }

  private static void drawLine(int tickLength, int tickLabel) {
    indent += "  ";
    if (DEBUG)
      System.out.println(indent + "drawLine(" + tickLength + ", " + tickLabel + ")");
    for (int j = 0; j < tickLength; j++)
      System.out.print("-");
    if (tickLabel >= 0)
      System.out.print(" " + tickLabel);
    System.out.print("\n");
    indent = indent.substring(2);
  }

  private static void drawLine(int tickLength) {
    drawLine(tickLength, -1);
  }
}

Это не изменит вывод, пока DEBUG равен false.Если вы установите true, журнал для drawRuler(1, 3) станет:

drawRuler(1, 3)
  drawLine(3, 0)
--- 0
  drawInterval(2)
    drawInterval(1)
      drawInterval(0)
      drawLine(1, -1)
-
      drawInterval(0)
    drawLine(2, -1)
--
    drawInterval(1)
      drawInterval(0)
      drawLine(1, -1)
-
      drawInterval(0)
  drawLine(3, 1)
--- 1

Там у вас есть автоматически сгенерированная версия пробного прогона.

Итак, что касается ваших вопросов:

В первый раз я ввожу nInches = 1 и majorlength = 3,

1) drawLine будет вызываться с (3,0) (tickLength и * 1044)*)

Правильно.

Точка1: Среднее значение над линией вызовет drawInterval(2)?

Правильно.

Точка3: drawLine(tickLength, -1).Почему мы используем это -1?

Потому что в drawLine(int tickLength, int tickLabel) говорится:

    if (tickLabel >= 0)
      System.out.print(" " + tickLabel);

Так что сделать значение для tickLabel меньше нуля - это просто способизбегайте печати этикетки, когда мы не на главном интервале, а на меньшем промежуточном интервале.

---

Обновление: Я также добавил отступ в соответствии с уровнем рекурсии дляверсия программы с выходом отладки, а также обновленный вывод журнала для отступа для лучшего понимания ОП.

---

Обновление 2: Вы можете упростить программу, указав удобный методdrawLine(int tickLength) следующим образом:

  private static void drawInterval(int centralLength) {
    // ...
      drawInterval(centralLength - 1);
      drawLine(centralLength, -1);  // Note the additional ", -1"
      drawInterval(centralLength - 1);
    // ...
  }

А затем удалите этот, поскольку он больше не используется:

  // Delete me!
  private static void drawLine(int tickLength) {
    drawLine(tickLength, -1);
  }

---

Обновление 3: Поскольку вы, кажется, настолько раздражены, что я не распечатывал вывод журнала для удобного метода drawLine(int tickLength), вот еще одна расширенная версия исходной программы, генерирующей вывод для этого метода, теперь точно копирующая пробный прогон с ручкой и бумагой:

package de.scrum_master.stackoverflow;

public class EnglishRuler {
  private static boolean DEBUG = true;
  private static String indentText = "";

  public static void main(String[] args) {
    drawRuler(1, 3);
  }

  public static void drawRuler(int nInches, int majorLength) {
    debugPrint("drawRuler(" + nInches + ", " + majorLength + ")");
    drawLine(majorLength, 0);
    for (int j = 1; j <= nInches; j++) {
      drawInterval(majorLength - 1);
      drawLine(majorLength, j);
    }
  }

  private static void drawInterval(int centralLength) {
    indent();
    debugPrint("drawInterval(" + centralLength + ")");
    if (centralLength >= 1) {
      drawInterval(centralLength - 1);
      drawLine(centralLength);
      drawInterval(centralLength - 1);
    }
    dedent();
  }

  private static void drawLine(int tickLength, int tickLabel) {
    indent();
    debugPrint("drawLine(" + tickLength + ", " + tickLabel + ")");
    for (int j = 0; j < tickLength; j++)
      System.out.print("-");
    if (tickLabel >= 0)
      System.out.print(" " + tickLabel);
    System.out.print("\n");
    dedent();
  }

  private static void drawLine(int tickLength) {
    indent();
    debugPrint("drawLine(" + tickLength + ")");
    drawLine(tickLength, -1);
    dedent();
  }

  private static void debugPrint(String message) {
    if (DEBUG)
      System.out.println(indentText + message);
  }

  private static void indent() {
    indentText += "  ";
  }

  private static void dedent() {
    indentText = indentText.substring(2);
  }
}

Обновленный консольный журнал становится:

drawRuler(1, 3)
  drawLine(3, 0)
--- 0
  drawInterval(2)
    drawInterval(1)
      drawInterval(0)
      drawLine(1)
        drawLine(1, -1)
-
      drawInterval(0)
    drawLine(2)
      drawLine(2, -1)
--
    drawInterval(1)
      drawInterval(0)
      drawLine(1)
        drawLine(1, -1)
-
      drawInterval(0)
  drawLine(3, 1)
--- 1

Я нашел это ненужным, но если это поможет вам, я рад.