C语言 如何优化 for 循环中的递归调用?

Question

我想知道如何在自己的定义循环中调用的递归函数像尾调用一样进行优化，以免受到性能和堆栈大小的影响。

通常，使用伪代码：

fun example(x):
if (something):
return // Stop the recursion
else:
for (/*...*/):
example() // Recursive call

对于一个具体的例子，我想知道如何在以下程序上应用这种优化，在这里找到：

// C program to print all permutations with duplicates allowed 
#include <stdio.h> 
#include <string.h> 
/* Function to swap values at two pointers */
void swap(char *x, char *y) 
{ 
char temp; 
temp = *x; 
*x = *y; 
*y = temp; 
} 
/* Function to print permutations of string 
This function takes three parameters: 
1. String 
2. Starting index of the string 
3. Ending index of the string. */
void permute(char *a, int l, int r) 
{ 
int i; 
if (l == r) 
printf("%sn", a); 
else
{ 
for (i = l; i <= r; i++) 
{ 
swap((a+l), (a+i)); 
permute(a, l+1, r); // Recursive call to be optimized
swap((a+l), (a+i));
} 
} 
} 
/* Driver program to test above functions */
int main() 
{ 
char str[] = "ABC"; 
int n = strlen(str); 
permute(str, 0, n-1); 
return 0; 
}

如果递归变得太深，则存在堆栈溢出的风险。那么我们如何通过这种递归函数来避免这种情况(如果可能的话，在不大幅修改算法的情况下(呢？

Answer 1

这不会产生完全相同的输出，但是一种打印字符串所有排列的迭代方式。改编自 cppreference.com。

void reverse(char *a, int l, int r)
{
while ((l != r) && (l != --r)) {
swap(a+(l++), a+r);
}
}
bool next_permutation(char *a, int l, int r)
{
if (l == r) return false;
int i = r;
if (l == --i) return false;
while (true) {
int i1 = i;
if (a[--i] < a[i1]) {
int i2 = r;
while (!(a[i] < a[--i2]))
;
swap(a+i, a+i2);
reverse(a, i1, r);
return true;
}
if (i == l) {
reverse(a, l, r);
return false;
}
}
}
void permute(char *a, int l, int r) 
{
do {
printf("%sn", a);
} while(next_permutation(a, l, r+1));
}

演示