返回函数调用与仅在递归期间再次调用函数有什么区别？

Question

我正在尝试实现 DFS，但我不明白在自身内部调用函数（递归）和返回函数调用（也是递归？）之间的区别
代码段 1：返回函数调用（错误答案）
在这种情况下，代码没有正确回溯。

const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [1],
    4: [2, 6],
    5: [2, 6],
    6: [4, 5]
}

let visited = [];
const dfs = (node) => {
    if (visited.includes(node))
        return;
    console.log(node);
    visited.push(node);
    for (let i = 0; i < graph[node].length; i++) {
        if (!visited.includes(graph[node][i]))
            return dfs(graph[node][i])
    }
}

dfs(1);

代码段 2：仅调用函数（正确答案）
似乎工作正常

const graph = {
    1: [2, 3],
    2: [4, 5],
    3: [1],
    4: [2, 6],
    5: [2, 6],
    6: [4, 5]
}

let visited = [];
const dfs = (node) => {
    if (visited.includes(node))
        return;
    console.log(node);
    visited.push(node);
    for (let i = 0; i < graph[node].length; i++) {
        if (!visited.includes(graph[node][i]))
             dfs(graph[node][i])
    }
}

dfs(1);

两者有什么区别？（我以为他们是一样的）
这是某种特定于语言 (JS) 的东西还是我误解了递归？

Answer 1

当您 return “函数调用”时，您实际上 return 被调用函数产生的值。当您简单地递归调用函数而不对它进行 return 操作时，您不会对 return 值执行任何操作。它们都是递归的情况，当不在循环中时它们的工作方式类似。

在这种情况下，由于您在 for 循环中使用函数的 return 值，一旦 dfs(graph[node][i]) 第一次运行，函数将在 returning 一个值（或者刚刚完成执行，就像在这种情况下）并退出堆栈调用，for 循环结束，函数执行也停止。

Answer 2

在编程术语中，递归函数可以定义为直接调用自身的例程，或者 indirectly.So 在您的示例中，两者都将被视为递归。

但是考虑到递归原理是基于这样一个事实，即通过重新使用子集问题的解决方案来解决更大的问题，那么我们将需要那些子集结果来计算大结果。没有那个 return 你只会得到一个 undefined ，这对你解决问题没有帮助。

一个非常简单的例子是 fact(n) = n * fact(n-1)

的阶乘

function fact (n) {
 if (n===0 || n===1) return 1;
 else return n*fact(n-1);
}

正如您在此示例中所见，没有 return 的 fact(4) = 4 * fact(3) 将是未定义的。

P.S：在您的示例中，不调用 return 可能只是因为我们没有重新使用子集

的结果

Answer 3

如果您编写的函数避免改变外部状态，而是对提供的参数进行操作，那么您会遇到更少的麻烦。下面我们用三个参数写dfs

t - 输入树或图
i - 开始遍历的id
s - 已访问节点的集合，默认为 new Set

function* dfs (t, i, s = new Set)
{ if (s.has(i)) return
  s.add(i)
  yield i
  for (const v of t[i] ?? [])
    yield* dfs(t, v, s)
}

const graph =
  { 1: [2, 3]
  , 2: [4, 5]
  , 3: [1]
  , 4: [2, 6]
  , 5: [2, 6]
  , 6: [4, 5]
  }
  
for (const node of dfs(graph, 1))
  console.log(node)

备注

1.你原来的dfs函数有一个console.log副作用——也就是说我们函数的主要作用是遍历图作为副作用（第二个），它在控制台中打印节点。将这两个效果分开是有益的，因为它允许我们使用 dfs 函数来执行我们希望在节点上执行的任何操作，而不仅仅是打印到控制台 -

dfs(1)  // <- traverse + console.log

使用生成器可以让我们轻松地将深度优先遍历与控制台打印分开 -

for (const node of dfs(graph, 1)) // <- traverse effect
  console.log(node)               // <- print effect

效果分离使得以我们需要的任何方式重用dfs成为可能。也许我们不想打印所有节点，而是将它们收集在一个数组中以将它们发送到其他地方 -

const a = []
for (const node of dfs(graph, 1)) // <- traverse effect
  a.push(node)                    // <- array push effect
return a                          // <- return result

2. 当我们使用普通的 for 语句循环时，它需要中间状态和更多语法样板 -

for (let i = 0; i < graph[node].length; i++)
  if (!visited.includes(graph[node][i]))
    dfs(graph[node][i])

使用 for..of syntax (not to be confused with for..in) 可以让我们专注于重要的部分。这与上面的 for 循环 exact 相同 -

for (const child of graph[node])
  if (!visited.includes(child))
    dfs(child)

3. 使用数组捕获 visited 节点效率有点低，因为 Array#includes 是一个 O(n) 过程 -

const visited = []    // undefined
visited.push("x")     // 1
visited.includes("x") // true

使用 Set 的工作方式几乎相同，但是它提供即时 O(1) 查找 -

const s = new Set   // undefined
s.add("x")          // Set { "x" }
s.has("x")          // true

Answer 4

其他人已经解释了为什么 return 会使您的流程短路。

但我认为主要问题是您并没有真正将递归函数用于 return 任何东西，而只是依赖函数内部的副作用（打印到控制台）。如果你真的想要遍历你的图，那么编写一个 returned 节点的有序集合的函数会更清晰。 Thankyou 的回答给了你一个这样的函数，使用生成器函数，以及一些有价值的建议。

这是另一种方法，可将您的（连接的）图形转换为数组：

const dft = (graph, node, visited = new Set([node])) => [
  node,
  ... (graph [node] .flatMap (
    (n) => visited .has (n) ? [] : dft (graph, n, visited .add (n))
  )),
]

const graph = {1: [2, 3], 2: [4, 5], 3: [1], 4: [2, 6], 5: [2, 6], 6: [4, 5]}

console .log (dft (graph, 1)) //~> [1, 2, 4, 6, 5, 3]

我们也使用集合而不是数组来跟踪节点的访问状态。我们首先访问提供的节点，然后对于它连接的每个节点，如果我们尚未将其标记为已访问，我们将递归访问该节点。（我称之为 dft 因为它是深度优先遍历，而不是深度优先搜索。）

但是请仔细阅读Thankyou的回答中的建议。挺值钱的。

返回函数调用与仅在递归期间再次调用函数有什么区别？

What is the difference between returning a function call vs only calling the function again during recursion?

javascript

algorithm

recursion

return

depth-first-search