Что делает эта рекурсивная функция?

Question

Что делает эта функция? И как вы оцениваете это?

Как проследить его? Как понять рекурсивный метод?

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

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

public class BalancedStrings { 

    public static void printBalanced(String prefix, int a, int b) { 
     if (a > 0) 
      printBalanced(prefix + "a", a - 1, b); 
     if (b > 0) 
      printBalanced(prefix + "b", a, b - 1); 
     if (a == 0 && b == 0) 
      System.out.println(prefix); 
    } 

    public static void printBalanced(int n) { 
     if (n % 2 == 0) { 
      printBalanced("", n/2, n/2); 
     } 
    } 

    public static void main(String[] args) { 
     printBalanced(4); 
    } 
} 

Answer 1

Звонки на номера printBalanced() являются рекурсивными вызовами. Способ распознавания рекурсии - это когда функция вызывает себя. Рекурсия лучше понять, если нарисован с использованием дерева:

Ветви дерева будет продолжать создавать больше функций до достижения конечного состояния удовлетворяется, в данном случае является a == 0 && b == 0. Предоставленная функция выглядит так, что она печатает префикс строки, конкатенированный с указанным числом символов «a» и «b», рекурсивно. Когда переменные a и b достигают 0, остановки рекурсии и результат выводится с использованием System.out.println(prefix);

В основной функции вы передаете целое число 4 для printBalanced(int n) которую вызовы printBalanced(String prefix, int a, int b) с параметрами, как это: printBalanced("",2,2);

общий результат приставка сцепляется со сбалансированным количеством элементов а и

Answer 2

Вашего останавливая условием б является то, что

a == 0 & b == 0 

Пока это условие не будет выполнено, то вызовите функцию рекурсивно и опустить а и Ь, пока они не являются 0.

Попробуйте положить некоторые контрольные точки в printBalanced(), так что вы можете увидеть, как это работает.

Answer 3

В самом базовом смысле информатики, рекурсия - это функция, которая называет себя. Несколько практических обычаев рекурсии.

обходе дерева
Графы
Lexing/Синтаксический
Сортировка

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

Например, рассмотрим следующий код С вычисления факториала числа

function factorial(int n) 
{ 
    int fact = 1; 
    for(int i = 2; i <= n; i++) 
    { 
    fact = fact * i; 
    } 
    return fact; 
} 

Answer 4

Это может помочь вам увидеть рекурсию, размещая операторы печати перед каждым вызовом printBalanced, а также печати заявление в качестве первая строка каждого определения метода printBalanced.Смотрите ниже:

public class BalancedStrings { 

    public static void printBalanced(String prefix, int a, int b) { 
     System.out.println("printBalanced called prefix = " + prefix + " a = " + a + " b = " + b); 
     if (a > 0) { 
      System.out.println("printBalanced calling printBalanced with prefix = " + prefix + " a-1 = " + (a-1) + " b = " + b); 
      printBalanced(prefix + "a", a - 1, b); 
     } 
     if (b > 0) { 
      System.out.println("printBalanced calling printBalanced with prefix = " + prefix + " a = " + a + " b-1 = " + (b-1)); 
      printBalanced(prefix + "b", a, b - 1); 
     } 
     if (a == 0 && b == 0) 
      System.out.println(prefix); 
    } 

    public static void printBalanced(int n) { 
     System.out.println("printBalanced called n = " + n); 
     if (n % 2 == 0) { 
      printBalanced("", n/2, n/2); 
     } 
    } 

    public static void main(String[] args) { 
     printBalanced(4); 
    } 
} 

Кроме того, printBalanced также называется перегруженный метод, потому что он имеет два «сигнатуру методов», которые в основном означает, что оно определенно более чем один раз, и каждое определение способа имеет другой набор переменных, передаются методу.

В принципе, printBalanced будет продолжать называть себя до тех пор, пока переменные a и b не уменьшатся до нуля. Затем он распечатает полученный префикс, который он будет накапливать.

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

Я надеюсь, что это поможет! Рекурсия может быть трудно понять. Вы также можете трассировать вызовы вручную, самостоятельно играя на компьютере и трассируя через выполнение методов, записывающих на бумаге значения префикса a и b, которые будут помещены в стек вызовов.

Вот вывод программы с отслеживанием гравюр включал:

C:\Users\>java BalancedStrings 
printBalanced called n = 4 
printBalanced called prefix = a = 2 b = 2 
printBalanced calling printBalanced with prefix = a-1 = 1 b = 2 
printBalanced called prefix = a a = 1 b = 2 
printBalanced calling printBalanced with prefix = a a-1 = 0 b = 2 
printBalanced called prefix = aa a = 0 b = 2 
printBalanced calling printBalanced with prefix = aa a = 0 b-1 = 1 
printBalanced called prefix = aab a = 0 b = 1 
printBalanced calling printBalanced with prefix = aab a = 0 b-1 = 0 
printBalanced called prefix = aabb a = 0 b = 0 
aabb 
printBalanced calling printBalanced with prefix = a a = 1 b-1 = 1 
printBalanced called prefix = ab a = 1 b = 1 
printBalanced calling printBalanced with prefix = ab a-1 = 0 b = 1 
printBalanced called prefix = aba a = 0 b = 1 
printBalanced calling printBalanced with prefix = aba a = 0 b-1 = 0 
printBalanced called prefix = abab a = 0 b = 0 
abab 
printBalanced calling printBalanced with prefix = ab a = 1 b-1 = 0 
printBalanced called prefix = abb a = 1 b = 0 
printBalanced calling printBalanced with prefix = abb a-1 = 0 b = 0 
printBalanced called prefix = abba a = 0 b = 0 
abba 
printBalanced calling printBalanced with prefix = a = 2 b-1 = 1 
printBalanced called prefix = b a = 2 b = 1 
printBalanced calling printBalanced with prefix = b a-1 = 1 b = 1 
printBalanced called prefix = ba a = 1 b = 1 
printBalanced calling printBalanced with prefix = ba a-1 = 0 b = 1 
printBalanced called prefix = baa a = 0 b = 1 
printBalanced calling printBalanced with prefix = baa a = 0 b-1 = 0 
printBalanced called prefix = baab a = 0 b = 0 
baab 
printBalanced calling printBalanced with prefix = ba a = 1 b-1 = 0 
printBalanced called prefix = bab a = 1 b = 0 
printBalanced calling printBalanced with prefix = bab a-1 = 0 b = 0 
printBalanced called prefix = baba a = 0 b = 0 
baba 
printBalanced calling printBalanced with prefix = b a = 2 b-1 = 0 
printBalanced called prefix = bb a = 2 b = 0 
printBalanced calling printBalanced with prefix = bb a-1 = 1 b = 0 
printBalanced called prefix = bba a = 1 b = 0 
printBalanced calling printBalanced with prefix = bba a-1 = 0 b = 0 
printBalanced called prefix = bbaa a = 0 b = 0 
bbaa