小贝子编程

如何在 Javascript 中用递归替换 for 循环



我有 2 个for循环，可以很好地创建带有行和列的网格，但我想使用递归改进解决方案，因为它更干净和推荐(在函数式编程中)。

所需的输出是 css 网格中使用的单个对数组

const createGrid = (rows,columns) => {
let grid=[]
for (let y = 3; y <= rows; y += 2){
let row = []
for (let x = 3; x <= columns; x += 2){
let col = [y, x]
row = [...row,col]
}
grid =[...grid, ...row]
}
return grid
}

是否还有关于如何在可能的情况下将循环转换为递归解决方案的准则？

原始递归

以下是使用递归制作网格的一种可能方法 -

const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols), makeRow(f, rows, cols) ]
const makeRow = (f, row = 0, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, row, cols - 1), f(row, cols) ]
const g =
makeGrid((x, y) => ({ xPos: x, yPos: y }), 2, 3)
console.log(JSON.stringify(g))
// [ [ {"xPos":1,"yPos":1}
//   , {"xPos":1,"yPos":2}
//   , {"xPos":1,"yPos":3}
//   ]
// , [ {"xPos":2,"yPos":1}
//   , {"xPos":2,"yPos":2}
//   , {"xPos":2,"yPos":3}
//   ]
// ]

功能参数f允许我们以多种方式构建网格单元

const g =
makeGrid((x, y) => [ x - 1, y - 1 ], 3, 2)
console.log(JSON.stringify(g))
// [ [ [ 0, 0 ]
//   , [ 0, 1 ]
//   ]
// , [ [ 1, 0 ]
//   , [ 1, 1 ]
//   ]
// , [ [ 2, 0 ]
//   , [ 2, 1 ]
//   ]
// ]
更

聪明地工作，而不是更努力地工作

根据 Bergi 的评论，您可以使用柯里单元格构造函数来减少一些额外的参数传递 -

const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols), makeRow(f(rows), cols) ]
const makeRow = (f, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, cols - 1), f(cols) ]
const g =
makeGrid
( x => y => [ x, y ] // "curried" constructor
, 2
, 3
)
console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
//   , [ 1, 2 ]
//   , [ 1, 3 ]
//   ]
// , [ [ 2, 1 ]
//   , [ 2, 2 ]
//   , [ 2, 3 ]
//   ]
// ]

吃你的蛋糕，也吃

或者，我们可以合并建议，并且仍然使用部分应用程序在调用站点接受二进制函数 -

const makeGrid = (f, rows = 0, cols = 0) =>
rows <= 0
? []
: [ ...makeGrid(f, rows - 1, cols)
, makeRow(_ => f(rows, _), cols) // <-- partially apply f
]
const makeRow = (f, cols = 0) =>
cols <= 0
? []
: [ ...makeRow(f, cols - 1), f(cols) ]
const g =
makeGrid
( (x,y) => [ x, y ] // ordinary constructor
, 2
, 3
)
console.log(JSON.stringify(g))
// [ [ [ 1, 1 ]
//   , [ 1, 2 ]
//   , [ 1, 3 ]
//   ]
// , [ [ 2, 1 ]
//   , [ 2, 2 ]
//   , [ 2, 3 ]
//   ]
// ]

第 N 个维度

上面我们仅限于二维网格。如果我们想要三维甚至更多尺寸怎么办？

const identity = x =>
x
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ] // <-- recursion
const map = ([ x, ...more ], f = identity) =>
x === undefined
? []
: [ f(x), ...map(more, f) ] // <-- recursion
const makeGrid = (r = [], d = 0, ...more) =>
d === 0
? r
: map(range(0, d), x => makeGrid(r(x), ...more)) // <-- recursion
const g =
makeGrid
( x => y => z => [ x, y, z ] // <-- constructor
, 2       // <-- dimension 1
, 2       // <-- dimension 2
, 3       // <-- dimension 3
, // ...     <-- dimension N
)
console.log(JSON.stringify(g))

输出

[ [ [ [0,0,0]
, [0,0,1]
, [0,0,2]
]
, [ [0,1,0]
, [0,1,1]
, [0,1,2]
]
]
, [ [ [1,0,0]
, [1,0,1]
, [1,0,2]
]
, [ [1,1,0]
, [1,1,1]
, [1,1,2]
]
]
]

任何尺寸;平坦结果

根据您的评论，您想要一个扁平的对数组。您可以通过简单地用map代替flatMap来实现这一点，如下所示 -

const identity = x =>
x
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ]
const flatMap = ([ x, ...more ], f = identity) =>
x === undefined
? []
: [ ...f(x), ...flatMap(more, f) ] // <-- flat!
const makeGrid = (r = [], d = 0, ...more) =>
d === 0
? r
: flatMap(range(0, d), x => makeGrid(r(x), ...more))
const g =
makeGrid
( x => y => [{ x, y }]  // <-- constructor
, 2       // <-- dimension 1
, 2       // <-- dimension 2
, // ...     <-- dimension N
)
console.log(JSON.stringify(g))
// [ { x: 0, y: 0 }
// , { x: 0, y: 1 }
// , { x: 1, y: 0 }
// , { x: 1, y: 1 }
// ]

函数构造函数再次展示了它的多功能性 -

const g =
makeGrid
( x => y =>
[[ 3 + x * 2, 3 + y * 2 ]] // whatever you want
, 3
, 3
)
console.log(JSON.stringify(g))
// [[3,3],[3,5],[3,7],[5,3],[5,5],[5,7],[7,3],[7,5],[7,7]]

了解更多信息

正如其他人所表明的那样，使用flatMap的这种特定版本的makeGrid正在有效地计算笛卡尔乘积。等你把脑袋绕到flatMap的时候，你已经知道了名单莫纳德！

请多吃蛋糕！

如果你渴望更多，我想给你一个关于我在计算研究中最喜欢的主题之一的入门：分隔延续。开始使用头等舱延续涉及对它们使用的某些方式的直觉 -

reset
( call
( (x, y) => [[ x, y ]]
, amb([ 'J', 'Q', 'K', 'A' ])
, amb([ '♡', '♢', '♤', '♧' ])
)
)
// [ [ J, ♡ ], [ J, ♢ ], [ J, ♤ ], [ J, ♧ ]
// , [ Q, ♡ ], [ Q, ♢ ], [ Q, ♤ ], [ Q, ♧ ]
// , [ K, ♡ ], [ K, ♢ ], [ K, ♤ ], [ K, ♧ ]
// , [ A, ♡ ], [ A, ♢ ], [ A, ♤ ], [ A, ♧ ]
// ]

就像上面的列表Monad一样，上面的amb封装了这种模棱两可(非确定性)计算的概念。我们可以使用分隔的延续轻松编写二维simpleGrid-

const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
reset
( call
( f
, amb(range(0, dim1))
, amb(range(0, dim2))
)
)
simpleGrid((x, y) => [[x, y]], 3, 3)
// [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

多亏了amb，创建 N 维网格也轻而易举。实现几乎消失了——

const always = x =>
_ => x
const multiGrid = (f = always([]), ...dims) =>
reset
( apply
( f
, dims.map(_ => amb(range(0, _)))
)
)
multiGrid
( (x, y, z) => [[ x, y, z ]] // <-- not curried this time, btw
, 3
, 3
, 3
)
// [ [0,0,0], [0,0,1], [0,0,2]
// , [0,1,0], [0,1,1], [0,1,2]
// , [0,2,0], [0,2,1], [0,2,2]
// , [1,0,0], [1,0,1], [1,0,2]
// , [1,1,0], [1,1,1], [1,1,2]
// , [1,2,0], [1,2,1], [1,2,2]
// , [2,0,0], [2,0,1], [2,0,2]
// , [2,1,0], [2,1,1], [2,1,2]
// , [2,2,0], [2,2,1], [2,2,2]
// ]

或者我们可以使用单元格构造函数中的line创建所需的增量和偏移量 -

const line = (m = 1, b = 0) =>
x => m * x + b // <-- linear equation, y = mx + b
multiGrid
( (...all) => [ all.map(line(2, 3)) ] // <-- slope: 2, y-offset: 3
, 3
, 3
, 3
)
// [ [3,3,3], [3,3,5], [3,3,7]
// , [3,5,3], [3,5,5], [3,5,7]
// , [3,7,3], [3,7,5], [3,7,7]
// , [5,3,3], [5,3,5], [5,3,7]
// , [5,5,3], [5,5,5], [5,5,7]
// , [5,7,3], [5,7,5], [5,7,7]
// , [7,3,3], [7,3,5], [7,3,7]
// , [7,5,3], [7,5,5], [7,5,7]
// , [7,7,3], [7,7,5], [7,7,7]
// ]

那么reset、call、apply和amb从何而来呢？JavaScript 不支持第一类延续，但没有什么能阻止我们自己实现它们——

const call = (f, ...values) =>
({ type: call, f, values })  //<-- ordinary object
const apply = (f, values) =>
({ type: call, f, values })  //<-- ordinary object
const shift = (f = identity) =>
({ type: shift, f })         //<-- ordinary object
const amb = (xs = []) =>
shift(k => xs.flatMap(x => k(x))) //<-- returns ordinary object
const reset = (expr = {}) =>
loop(() => expr)             //<-- ???
const loop = f =>
// ...                       //<-- follow the link!

鉴于您问题的上下文，很明显，这是一项纯粹的学术练习。斯科特的回答为我们所做的一些权衡提供了合理的理由。希望本节向您展示，更强大的计算功能可以轻松解决最初看起来很复杂的问题。

一流的延续为您的程序解锁了强大的控制流。你有没有想过JavaScript是如何实现function*和yield的？如果 JavaScript 没有这些功能呢？阅读这篇文章，看看我们如何只使用普通函数来制作这些(以及更多)。

延续代码演示

在您自己的浏览器中看到它的工作！展开下面的代码片段，使用分隔的延续生成网格...在JavaScript中！-

// identity : 'a -> 'a
const identity = x =>
x
// always : 'a -> 'b -> 'a
const always = x =>
_ => x
// log : (string, 'a) -> unit
const log = (label, x) =>
console.log(label, JSON.stringify(x))

// line : (int, int) -> int -> int
const line = (m, b) =>
x => m * x + b

// range : (int, int) -> int array
const range = (start = 0, end = 0) =>
start >= end
? []
: [ start, ...range(start + 1, end) ]
// call : (* -> 'a expr, *) -> 'a expr
const call = (f, ...values) =>
({ type: call, f, values })
// apply : (* -> 'a expr, * array) -> 'a expr
const apply = (f, values) =>
({ type: call, f, values })
// shift : ('a expr -> 'b expr) -> 'b expr
const shift = (f = identity) =>
({ type: shift, f })
// reset : 'a expr -> 'a
const reset = (expr = {}) =>
loop(() => expr)
// amb : ('a array) -> ('a array) expr
const amb = (xs = []) =>
shift(k => xs .flatMap (x => k (x)))
// loop : (unit -> 'a expr) -> 'a
const loop = f =>
{ // aux1 : ('a expr, 'a -> 'b) -> 'b
const aux1 = (expr = {}, k = identity) =>
{ switch (expr.type)
{ case call:
return call(aux, expr.f, expr.values, k)
case shift:
return call
( aux1
, expr.f(x => trampoline(aux1(x, k)))
, identity
)
default:
return call(k, expr)
}
}
// aux : (* -> 'a, (* expr) array, 'a -> 'b) -> 'b
const aux = (f, exprs = [], k) =>
{ switch (exprs.length)
{ case 0:
return call(aux1, f(), k) // nullary continuation
case 1:
return call
( aux1
, exprs[0]
, x => call(aux1, f(x), k) // unary
)
case 2:
return call
( aux1
, exprs[0]
, x =>
call
( aux1
, exprs[1]
, y => call(aux1, f(x, y), k) // binary
)
)
case 3: // ternary ...
case 4: // quaternary ...
default: // variadic
return call
( exprs.reduce
( (mr, e) =>
k => call(mr, r => call(aux1, e, x => call(k, [ ...r, x ])))
, k => call(k, [])
)
, values => call(aux1, f(...values), k)
)
}
}
return trampoline(aux1(f()))
}
// trampoline : * -> *
const trampoline = r =>
{ while (r && r.type === call)
r = r.f(...r.values)
return r
}
// simpleGrid : ((...int -> 'a), int, int) -> 'a array
const simpleGrid = (f, dim1 = 0, dim2 = 0) =>
reset
( call
( f
, amb(range(0, dim1))
, amb(range(0, dim2))
)
)
// multiGrid : (...int -> 'a, ...int) -> 'a array
const multiGrid = (f = always([]), ...dims) =>
reset
( apply
( f
, dims.map(_ => amb(range(0, _)))
)
)
// : unit
log
( "simple grid:"
, simpleGrid((x, y) => [[x, y]], 3, 3)
)
// : unit
log
( "multiGrid:"
, multiGrid
( (...all) => [ all.map(line(2, 3)) ]
, 3
, 3
, 3
)
)

起初，在阅读您的代码时，我认为您生成了一种样式的网格，因此makeGrid (7, 9)会产生如下结果：

[
[[3, 3], [3, 5], [3, 7], [3, 9]], 
[[5, 3], [5, 5], [5, 7], [5, 9]], 
[[7, 3], [7, 5], [7, 7], [7, 9]]
]

相反，它返回单个对数组：

[[3, 3], [3, 5], [3, 7], [3, 9], [5, 3], [5, 5], [5, 7], [5, 9], [7, 3], [7, 5], [7, 7], [7, 9]]

我很确定我不是唯一一个。 Bergi在评论中建议进行修复，将其更改为前者。 (这就是将grid =[...grid, ...row]更改为grid =[...grid, row]可以做的事情。 而《谢谢》的精彩回答也是基于同样的假设。

这是一个问题。

当读者无法快速理解你的代码做什么时，维护起来就会变得更加困难......即使是几周后你自己。

您可能会听到用递归替换循环的建议的原因与此有关。 循环都是关于显式命令式指令来获得你想要的东西，这取决于变异变量，然后你必须跟踪这些变量，并且很容易受到逐个错误的影响。 递归通常更具声明性，这是一种说法，即您正在寻找的结果只是将这些更简单的结果与我们当前的数据相结合，并指出如何通过基本情况或递归调用获得更简单的结果。

但是，可读性和可理解性的优势是关键，而不是解决方案是递归的事实。

不要误会我的意思，递归是我最喜欢的编程技术之一。 谢谢的回答是美丽而优雅的。 但这并不是解决显式for循环存在的问题的唯一技术。 通常，当尝试将初级程序员转移到中级及以后时，我做的第一件事就是用更有意义的结构替换for循环。 大多数循环都试图做一些事情之一。 他们试图将列表中的每个元素转换为新的东西(map)，试图选择元素的一些重要子集(filter)，试图找到第一个重要元素(find)，或者试图将所有元素组合成一个值(reduce)。 通过改用这些代码，代码变得更加明确。

同样重要的是，正如Thankyou的回答所示，拆分出可重用的代码片段，以便您的主要功能可以专注于重要部分。 下面的版本提取了一个函数rangeBy，它为我常用的range函数添加了一个step参数。range创建一个整数范围，例如，range (3, 12)产生[3, 4, 5, 6, 7, 8, 9, 10, 11, 12]rangeBy添加一个初始step参数，以便range (2) (3, 12)产生[3, 5, 7, 9, 11]。

我们将该rangeBy函数与map及其表亲flatMap一起使用，以制作循环函数的更显式版本：

const rangeBy = (step) => (lo, hi) => 
[... Array (Math .ceil ((hi - lo + 1) / step))] 
.map ((_, i) => i * step  + lo)
const createGrid = (rows, columns) => 
rangeBy (2) (3, rows) .flatMap (y => 
rangeBy (2) (3, columns) .map (x => 
[y, x]
)
)
console .log (createGrid (7, 9))

知道rangeBy做什么，我们可以在心理上将其解读为

const createGrid = (rows, columns) => 
[3, 5, 7, ..., rows] .flatMap (y => 
[3, 5, 7, ..., columns] .map (x => 
[y, x]
)
)

请注意，如果您想要我期望的行为，您只需将flatMap替换为createGrid中的map即可实现它。 此外，如果您这样做，添加 Thankyou 提供的更通用的行为是微不足道的，方法是将[y, x]替换为f (x, y)并将f作为参数传递。 此版本中仍然硬编码的是将rows和columns转换为以 3 开头的奇数数组。 我们可以将实际数组作为函数的参数，并在外部应用rangeBy。 但在这一点上，我们可能正在寻找一个理想的不同函数cartesianProduct.

所以递归是一个神奇而有用的工具。 但它是一个工具，而不是一个目标。 然而，简单、可读的代码是一个重要的目标。

更新

我本来想提这个，只是忘记了。 以下版本表明，rangeBy中的咖喱远非根本。 我们可以轻松地使用单个调用：

const rangeBy = (step, lo, hi) => 
[... Array (Math .ceil ((hi - lo + 1) / step))] 
.map ((_, i) => i * step  + lo)
const createGrid = (rows, columns) => 
rangeBy (2, 3, rows) .flatMap (y => 
rangeBy (2, 3, columns) .map (x => 
[y, x]
)
)
console .log (createGrid (7, 9))

咖喱rangeBy的主要理由是，当它这样写时：

const rangeBy = (step) => (lo, hi) => 
[... Array (Math .ceil ((hi - lo + 1) / step))] 
.map ((_, i) => i * step  + lo)

我们可以通过简单地将1应用于上述内容来编写更常见的range。 那是

const range = rangeBy (1)
range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

这非常有用，以至于它已成为我编写函数的常用风格。 但这不是简化问题的重要部分。

函数式编程更多的是关于高阶函数，而不是直接递归。我相信以下内容等效于您的示例，使用下划线中的_.range.js以及标准库中的map和flatMap。

const rowRange = _.range(3, rows + 1, 2);
const colRange = _.range(3, columns + 1, 2);
return rowRange.flatMap(row => colRange.map(col => [col, row]));

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium