我在网站上看到以下内容作为练习。基本上说写以下函数时不使用递归，也不使用向量，堆栈等结构：
void rec(int n) {
if (n != 0) {
cout << n << " ";
rec(n-1);
rec(n-1);
}
}
起初我以为这会很容易，但是我很惊讶地要完成它。
为了更好地理解它，我将其定义为以下数学函数：
f（x）= {如果x = 0，则为1，否则为f（x-1）+ f（x-1）}（其中+运算符表示串联，-是正常减号）
但是，展开此操作会更加困难，并且我被卡住了。有没有直接的方法可以将其编写为循环？而且，更笼统地说，有没有一种算法可以解决这类问题？
如果您足够弄弄它，则可以得到至少一种在不重新访问它的情况下输出有序序列的方法：）
let n = 5
// Recursive
let rec_str = ''
function rec(n) {
if (n != 0) {
rec_str += n
rec(n-1);
rec(n-1);
}
}
rec(n)
console.log(rec_str)
// Iterative
function f(n){
let str = ''
for (let i=1; i<1<<n; i++){
let t = i
let p = n
let k = (1 << n) - 1
while (k > 2){
if (t < 2){
break
} else if (t <= k){
t = t - 1
p = p - 1
k = k >> 1
} else {
t = t - k
}
}
str += p
}
console.log(str)
}
f(n)
（代码正在构建一个字符串，我认为应该根据规则禁止该字符串，但仅用于演示；我们可以改为输出数字。）
,
void loop(int n)
{
int j = 0;
int m = n - 1;
for (int i = 0; i < int(pow(2,n)) - 1; i++)
{
j = i;
if (j == 0)
{
std::cout << n << " ";
continue;
}
m = n - 1;
while (true)
{
if (m == 1)
{
std::cout << m << " ";
m = n - 1;
break;
}
if (j >= int(pow(2,m)))
{
j = j - int(pow(2,m)) + 1;
}
if (j == 1)
{
std::cout << m << " ";
m = n - 1;
break;
}
else
{
j--;
}
m--;
}
}
std::cout << std::endl;
}
对于n = 3，例如
out = [3 2 1 1 2 1 1]
indexes = [0 1 2 3 4 5 6]
考虑索引列表；对于i> 0和i
例如，对于n = 4，这是所有索引在每个while步骤中发生的情况。 p（x）表示值x在该索引处打印。 /表示已经打印了索引。
n = 4,m = 3
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14]
m = 3
[p(n=4) 1 2 3 4 5 6 7 8 9 10 11 12 13 14]
if(i >=2^3) -> i = i -2^3 + 1)
[/ 1 2 3 4 5 6 7 1 2 3 4 5 6 7]
if(i == 1) -> print m,else i = i -1
[/ p(3) 1 2 3 4 5 6 p(3)1 2 3 4 5 6]
m = 2
if (i >=2^2) -> i = i - 2^2 +1
[/ / 1 2 3 1 2 3 / 1 2 3 1 2 3]
if(i == 1) -> print m,else i = i -1
[ / / p(2) 1 2 p(2) 1 2 / p(2) 1 2 p(2) 1 2]
m = 1
if (m == 1) -> print(m)
[ / / / p(1) p(1) / p(1) p(1) / / p(1) p(1) / p(1) p(1)]
因此结果是：
[4 3 2 1 1 2 1 1 3 2 1 1 2 1 1]
void via_loop(int n) {
string prev = "1 ",ans = "1 ";
for (int i = 2; i <= n; i++) {
ans = to_string(i) + " " + prev + prev;
prev = ans;
}
cout << ans;
}
想法是保存每个数字先前的计算结果。完整代码：
void rec(int n) {
if (n != 0) {
cout << n << " ";
rec(n-1);
rec(n-1);
}
}
void via_loop(int n) {
string prev = "1 ",ans = "1 ";
for (int i = 2; i <= n; i++) {
ans = to_string(i) + " " + prev + prev;
prev = ans;
}
cout << ans;
}
int main() {
int n = 5;
cout << "Rec : ";
rec(n);
cout << endl;
cout << "Loop: ";
via_loop(n);
cout << endl;
}
输出：
Rec : 5 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1
Loop: 5 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1 4 3 2 1 1 2 1 1 3 2 1 1 2 1 1