Гораздо проще придумать рекурсивные алгоритмы для многих задач. Единственная загвоздка в том, что рекурсия использует стековую память, которой не хватает, в то время как итеративные версии используют список, доступ к которому осуществляется по принципу «последний пришел – первый вышел». Здесь мы увидим три алгоритма, а именно: факториал, глубину бинарного дерева и генерацию всех n-выберите-k комбинаций набора.
Факториал
Факториал числа можно определить рекурсивно как:
f(0) = 1 f(n) = n* f(n-1)
Это позволяет прямой перевод в следующий код:
int factorial(int n) {
if (n > 1) {
// Recursive case
return n * factorial(n - 1);
} else {
// Base case
return 1;
}
}
Преобразовать его в итеративную функцию довольно просто. Однако даже рекурсивная функция при компиляции с помощью компилятора GNU C++ создает итеративный код, как показано в следующем выводе ассемблера.
_Z9factoriali: .LFB0: endbr64 movl $1, %eax cmpl $1, %edi jle .L4 .L3: movl %edi, %edx subl $1, %edi imull %edx, %eax cmpl $1, %edi jne .L3 ret ;; redundant code .L4: ret
Таким образом, может не быть необходимости активно преобразовывать рекурсивную функцию в итеративную функцию, особенно если функция является хвостовой рекурсией. Многие языки поддерживают хвостовые вызовы, где, если последний оператор является вызовом другой функции, происходит переход, а не вызов, тем самым предотвращая рост стека. C++ не может этого сделать, отчасти потому, что деструкторы и финализаторы должны вызываться непосредственно перед возвратом функции.
Глубина бинарного дерева
Рассмотрим функцию для вычисления глубины бинарного дерева. Рекурсивная версия воспроизводится ниже:
int recursive_depth(Node* root){
if (root ==nullptr) return 0;
else {
int dleft = recursive_depth(root->left);
int dright = recursive_depth(root->right);
return 1 + std::max(dleft,dright);
}
}
Выходные данные языка ассемблера, показанные ниже, показывают, что, как и код C++, функция вызывается дважды рекурсивно.
_Z15recursive_depthP4Node: .LFB6: endbr64 testq %rdi, %rdi je .L6 pushq %rbp pushq %rbx movq %rdi, %rbx subq $8, %rsp movq (%rdi), %rdi call _Z15recursive_depthP4Node movq 8(%rbx), %rdi movl %eax, %ebp call _Z15recursive_depthP4Node leal 1(%rbp), %ecx movl %eax, %edx leal 1(%rax), %eax cmpl %edx, %ebp cmovg %ecx, %eax addq $8, %rsp popq %rbx popq %rbp ret .L6: xorl %eax, %eax ret
Один из способов преобразовать его в итеративную функцию — преобразовать его в стиль передачи продолжения (CPS). Переводя версию Ocaml на Gasche, мы получаем следующий код C++.
typedef std::function<int(int)> call_back;
int cps_depth( Node* root, call_back cps){
if(root==nullptr) return cps(0);
else return cps_depth(root->left,[&] (int dleft) {
return cps_depth(root->right, [&] (int dright){
return cps(1 + std::max(dleft,dright));
});});
}
int depth(Node* root){
return cps_depth(root, [](int k){return k;});
}
Однако, несмотря на хвостовую рекурсию, компилятор C++ не может преобразовать его в итеративную функцию, как показывает собранный вывод, который не показан. Способ преобразования рекурсивной функции в CPS обычно заключается в использовании функции CPS, которая принимает возвращаемое значение рекурсивной функции в качестве входного параметра, а затем добавляет остальную часть исходной функции в качестве кода для функции CPS. Важно, чтобы рекурсивная функция использовала функцию CPS перед возвратом в каждом случае.
Следуя Гаше, теперь мы можем преобразовать приведенный выше код в две взаимно рекурсивные функции, которые на самом деле являются хвостовыми вызовами.
enum class item_type { tree, height};
struct item {
item_type type;
union { Tree* root; unsigned height; };
item(Tree* r):type(item_type::tree)
{root=r;}
item(unsigned h):type(item_type::height)
{height=h;}
};
static int height_aux(Tree *root, stack<item>& items){
if(root)
{
item it(root->right);
items.push(it);
return height_aux(root->left,items);
} else {
return eval(items, 0);
}
}
static int eval(stack<items>, unsigned depth){
if(items.empty()){
return depth;
}else{
item cur = items.top();
items.pop();
switch (cur.type)
{
case item_type::tree:
{
item next(depth);
items.push(next);
return height_aux(cur.root, items);
}
case item_type::height:
{
return eval(items, 1 + std::max(depth, cur.height));
}
}
}
}
static unsigned height(Tree* root){
stack<item> items;
return height_aux(root,items);
}
Давайте расшифруем, что здесь происходит. Давайте снова посмотрим на обратный вызов версии CPS.
return cps_depth(root->left,[&] (int dleft) {
return cps_depth(root->right, [&] (int dright){
return cps(1 + std::max(dleft,dright));
});});
Второй или внутренний вызов cps_depth требует значения root-›right и ничего больше. Последующему вызову cps требуется только значение dleft, которое становится доступным только при вызове внешней функции. Следовательно, нам нужен союз, который указывает, какое из двух значений требуется.
Объединение eval и height_aux в одну итеративную функцию не так уж сложно, как показано ниже.
static int height(Tree *root){
enum class item_type { tree, height};
struct item {
item_type type;
union {
Tree* root;
unsigned height;
};
item(Tree* r):type(item_type::tree)
{root=r;}
item(unsigned h):type(item_type::height)
{height=h;}
};
bool go_on=true;
unsigned depth = 0;
std::stack<item> items;
while (go_on) {
if (root) {
item it(root->right);
items.push(it);
root = root->left;
} else {
go_on=false;
depth=0;
while (!items.empty()&& !go_on) {
item cur = items.top();
items.pop();
switch (cur.type) {
case item_type::tree: {
item next(depth);
items.push(next);
root = cur.root;
go_on = true;
}
break;
case item_type::height: {
depth = 1 + std::max(depth, cur.height);
}
break;
}
}
}
}
return depth;
}
Сгенерировать все комбинации
Рассмотрим задачу генерации всех k-комбинаций множества, содержащего n элементов.
void print(const vector<int>& nums, ostream& fout)
{
for (auto& a : nums) { fout << a << ' '; }
fout << endl;
}
void combo(vector<int>& nums, int n, int k, vector<int>& result)
{
if ( k == 0 ) {
print(result,cout);
}
else if (n == k){
result.insert(result.end(),nums.begin(),nums.begin()+k);
print(result,cout);
result.erase(result.end()-k,result.end());
} else {
result.push_back(nums[0]);
//include num[0] and reduce n
swap(nums[0],nums[n-1]);
combo(nums,n-1,k-1,result);
result.pop_back();
//exclude old num[0]
combo(nums,n-1,k,result);
swap(nums[0],nums[n-1]);
}
}
void doCombo(vector<int>& nums, int n, int k){
vector<int> result;
combo(nums,n,k,result);
}
Обратите внимание, что изначально результат пуст, и в ходе вычисления «результат» будет одинаковым в начале и в конце функции во всех экземплярах вызова. Излишне говорить, что компилятор не преобразует ее автоматически в итеративную функцию. Используя ту же технику, что и раньше, давайте создадим версию CPS, показанную ниже:
typedef std::function<void()> callback;
void combo_cps(vector<int>& nums, int n, int k,
vector<int>& result, callback cps){
if ( k == 0 ) {
print(result,cout);
cps();
} else if (n == k){
result.insert(result.end(),nums.begin(),nums.begin()+k);
print(result,cout);
result.erase(result.end()-k,result.end());
cps();
} else {
result.push_back(nums[0]);
//include num[0]
swap(nums[0],nums[n-1]);
combo_cps(nums,n-1,k-1,result,
[&](){
result.pop_back();
//exclude old num[0]
combo_cps(nums,n-1,k,result, [&]()
{
swap(nums[0],nums[n-1]);
cps();
});
});
}
}
void combo(vector<int>& nums, int n, int k){
combo_cps(nums,n,k,[](){}):
}
(От себя лично: я совершил ошибку новичка, не позвонив cps перед возвращением, и мне потребовалось некоторое время, чтобы решить эту проблему).
Чтобы преобразовать приведенную выше версию CPS в итеративную версию, нам нужно отслеживать два значения, n и k, и состояние, которое означает, включено или исключено num[0]. Результат показан ниже:
struct iter{
int n;
int k;
enum { include, exclude, none } state;
};
void combo_iter(vector<int>& nums, int n, int k){
vector<int> result;
vector<iter> items;
iter it{0,0,iter::none};
items.push_back(it);
for(;;){
while(!(k==0 || k==n)){
result.push_back(nums[0]);
swap(nums[0],nums[n-1]);
iter it{n-1,k-1,iter::include};
items.push_back(it);
--n;
--k;
}
if ( k == 0 ) {
print(result,cout);
} else if (n == k){
result.insert(result.end(),nums.begin(),nums.begin()+k);
print(result,cout);
result.erase(result.end()-k,result.end());
}
bool go_on = true;
while(go_on){
iter it = items.back();
items.pop_back();
switch (it.state){
case iter::exclude:
n=it.n;
k= it.k;
swap(nums[0],nums[n]);
break;
case iter::include:
result.pop_back();
it = iter{it.n,it.k+1,iter::exclude};
items.emplace_back(it);
n=it.n;
k= it.k;
go_on = false;
break;
case iter::none:
return;
break;
}
}
}
}
Обратите внимание, что структура кода почти такая же, как и для задачи о глубине дерева. Чтобы включить num[0], мы уменьшаем k и добавляем num[0] к результату. Чтобы исключить num[0], мы возвращаемся к старому значению k и извлекаем верхнее значение из result. Обратите внимание, что оператор switch выполняется только после того, как будет вычислен хотя бы один полный результат.
