Использование рекурсии для вычисления количества чего-либо для печати

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

Например: если вы должны были передать число 3, оно должно напечатать 2 ^ 3 звезды, поэтому оно напечатает 8 звезд.

Я должен напечатать его 2 ^ k раз, где k — переданное целое число. Ответ на вопрос:

public String printStars(int k) {
    if (k == 0) 
        return "*";
    else 
        return printStars(k - 1) + printStars(k - 1); 
}

Кажется, я не могу понять стек вызовов и то, как это решает проблему, как я это вижу, когда я передаю 3 для int k, он будет делать n - 1 3 раза, пока не достигнет базового случая, и вернет 2 звезды к вызову перед этим, и поскольку для этого потребовалось 3 уровня, он напечатает 3 x 2 звезды, поэтому он напечатает 6 звезд. Это странно, потому что большинство других рекурсий легко даются мне, но это сбивает с толку.


java recursion exponent
person user6064023    schedule 15.03.2016    source источник
comment
Я предполагаю, что вы имеете в виду k вместо n (или наоборот).   -  person Andy Turner    schedule 15.03.2016

Ответы (3)


arrow_upward
0
arrow_downward

Я думаю, что простой способ увидеть это - просто развернуть каждый вызов функции:

Когда k = 3, оператор return оценивается как printStars(2) + printStars(2).

Таким образом, он сначала вызовет printStars(2) слева, что будет оцениваться как:

printStars(1) + printStars(1) + printStars(2)

Опять же, давайте сначала расширим левый:

printStars(0) + printStars(0) + printStars(1) + printStars(2)

printStars(0), наконец, будет равно "*", поэтому у нас будет

"*" + "*" + printStars(1) + printStars(2) == "**" + printStars(1) + printStars(2).

И мы уже видели это printStars(1) == "**", так что у нас есть:

"****" + printStars(2). И мы уже знаем, что printStars(2) решит.

person Oliver Dain    schedule 15.03.2016
comment
Спасибо, я следил за этим, но забыл, что исходный Call of printStars (#) нужно добавить к тому, с чем вы рекурсируете. так что я получил ответ, который был правильным ответом - то, что вы получаете от исходного звонка. Спасибо, что так объяснили - person user6064023; 15.03.2016

arrow_upward
1
arrow_downward

Я думаю, это всегда должно быть k или n?

Как работает рекурсия: она охватывает дерево:

Каждый вызов printStars приводит к одному * (2^0) или двум * (2^1).

Если вы вызываете printStars(4):

Уровень рекурсии 4 ist != 0, поэтому он возвращает сокращение двух отдельных вызовов самого себя, каждый с параметром (3).

Уровень рекурсии 3 ist != 0, поэтому он возвращает сокращение двух отдельных вызовов самого себя, каждый с параметром (2).

Уровень рекурсии 2 ist != 0, поэтому он возвращает сокращение двух отдельных вызовов самого себя, каждый с параметром (1).

Уровень рекурсии 1 ist != 0, поэтому он возвращает сокращение двух отдельных вызовов самого себя, каждый с параметром (0).

Уровень рекурсии 0 ist == 0, поэтому каждый вызов возвращает один *.

Вернувшись на уровень рекурсии 1, мы получаем два *, сокращаем и возвращаем их.

Вернувшись на уровень рекурсии 2, мы получаем два **, сокращаем и возвращаем их.

Вернувшись на уровень рекурсии 3, мы получаем два ****, сокращаем и возвращаем их.

Вернувшись на уровень рекурсии 4, мы получаем два ********, сокращаем и возвращаем их.

Таким образом, вызывающий абонент получает «***************» 2 ^ 4 = 16 *

caller                 |
k=4              /         \            (just call yourself 2 times an return contraction of both calls)
k=3          /     \     /     \        (just call yourself 2 times an return contraction of both calls)
k=2         / \   / \   / \   / \       (just call yourself 2 times an return contraction of both calls)
k=1        /\ /\ /\ /\ /\ /\ /\ /\      (just call yourself 2 times an return contraction of both calls)
k=0        ** ** ** ** ** ** ** **      (just return 2^0 = 1 '*')
person cmks    schedule 15.03.2016
comment
Отличная диаграмма, спасибо за ваш ответ, который делает процесс очень понятным, спасибо за ваше время! - person user6064023; 15.03.2016

arrow_upward
0
arrow_downward

Просто следуйте коду через:

Должно быть понятно, что в небазовом случае:

printStars(k).length() == 2 * printStars(k - 1).length()

поскольку значение в этом случае определяется выражением

return printStars(k - 1) + printStars(k - 1);

Используя это наблюдение, мы можем доказать по индукции, что:

printStars(k).length() == 2^k

(где ^ обозначает мощность, а не побитовое XOR)

  • Верно, что в базовом случае printStars(0).length() == 2^0
  • Предположим, что printStars(k - 1).length() == 2^(k-1), printStars(k).length() == 2 * printStars(k - 1).length() == 2^k

КЭД.

person Andy Turner    schedule 15.03.2016
comment
Спасибо за ваше объяснение, это было очень полезно! - person user6064023; 15.03.2016