Это рекурсия?

Я прочитал этот код из учебника Стэнфорда по классу CS106B в главе о рекурсии. Эта рекурсивная функция использует цикл. Хотя разложение происходит между рекурсивными вызовами, а цикл просто пробует разные комбинации, эта функция все еще определяет определение рекурсии?

Краткое изложение: код, который генерирует перестановки строки в наборе, например «ABC» -> «ACB», «BCA» ….

Set<string> generatePermutations(string str) {
Set<string> result;
if (str == "") {
result += "";
} else {
for (int i = 0; i < str.length(); i++) {
char ch = str[i];
string rest = str.substr(0, i) + str.substr(i + 1);
for (string s : generatePermutations(rest)) {
result += ch + s;
}
}
}
return result;
}

-2

Решение

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

7

Другие решения

Да, это рекурсия. Это просто перевод наивного алгоритма на язык программирования, и самый наивный алгоритм для перестановок длины n состоит в том, чтобы зафиксировать один элемент из множества и переставить остальные (n-1) элементы. Да, алгоритм рекурсивный, так же как и его реализация.

3

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector