时间戳

首页 > 解决方案 > 如何使用循环编写此递归

c++ - 如何使用循环编写此递归

问题描述

我在网站上看到以下内容作为练习。它基本上说在不使用递归和不使用向量、堆栈等结构的情况下编写以下函数：

void rec(int n) {
        if (n != 0) {
                cout << n << " ";
                rec(n-1);
                rec(n-1);
        }
}

起初我以为这会很容易，但我出人意料地努力完成它。

为了更好地理解它，我将它定义为一个数学函数，如下所示：

f(x) = {1 if x = 0, f(x-1) + f(x-1) else}（其中 + 运算符表示连接，- 是正常的减号）

然而，展开这让它变得更难了，我被困住了。有没有直接的方法把它写成循环？而且，更一般地说，是否有解决此类问题的算法？

标签： c++algorithmrecursion

解决方案

如果您对它进行了足够的摆弄，您至少可以获得一种输出有序序列而无需重新访问它的方法:)

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)

（代码正在构建一个字符串，我认为根据规则应该不允许，但仅用于演示；我们可以直接输出数字。）

推荐阅读