Elixir中不可变2D列表递归状态丢失的解决方法问询

在Elixir的无状态场景下，递归时的状态丢失问题，核心原因是没正确传递更新后的不可变数据副本——因为所有数据都是不可变的，每次修改都会生成新对象，你必须把这个新对象传给下一层递归，才能让后续步骤拿到最新状态。你的代码里状态丢失，就是因为复用了原始未修改的变量，没把更新后的grid传递下去。

核心处理原则 #

• 递归函数必须返回更新后的状态：终止条件要返回最终的状态实例，中间步骤要返回递归调用后的状态，确保上层能拿到最新数据。
• 每次递归都传递新状态：不要在递归中使用原始变量，必须把修改后的新数据作为参数传给下一次调用。
• 避免无返回的操作：如果函数修改了数据，不能只做IO输出就结束，必须返回修改后的结果。

你的代码问题分析 #

1. write_out_column的终止分支只输出日志，没有返回更新后的grid，导致前面修改的状态直接丢失。
2. write_out_row调用write_out_column后，没有返回其结果，上层调用拿不到修改后的grid。
3. fill_out_remainder里调用write_out_row后，依然用原始的grid进行下一次递归，完全没用到修改后的状态。

修正后的代码 #

defmodule Euler do
  def euler_15() do
    grid = create_2d_list(10, 10)
    # 填充第一行
    grid = write_out_first_row(grid, 0)
    # 填充第一列
    grid = write_out_first_column(grid, 0)
    # 填充剩余单元格，最终返回完整grid
    fill_out_remainder(grid, 1, 1)
  end

  # 终止条件：行号到10时返回最终grid
  def fill_out_remainder(grid, 10, _) do
    IO.puts("填充完成")
    grid
  end

  # 终止条件：列号到10时返回当前行更新后的grid
  def write_out_column(grid, _row, 10) do
    grid
  end

  def write_out_column(grid, row, col) do
    cell_above = get_element(grid, row-1, col)
    cell_left = get_element(grid, row, col-1)
    # 生成新的grid副本
    new_grid = set_element(grid, row, col, cell_above + cell_left)
    # 传递新grid给下一次递归，并返回结果
    write_out_column(new_grid, row, col + 1)
  end

  def write_out_row(grid, row) do
    # 返回write_out_column更新后的grid
    write_out_column(grid, row, 1)
  end

  def fill_out_remainder(grid, row_ct, col_ct) do
    # 获取当前行更新后的grid
    updated_grid = write_out_row(grid, row_ct)
    # 传递新grid给下一次递归
    fill_out_remainder(updated_grid, row_ct + 1, col_ct)
  end

  def write_out_first_row(grid, 10) do
    grid
  end

  def write_out_first_row(grid, counter) do
    new_grid = set_element(grid, 0, counter, 1)
    write_out_first_row(new_grid, counter + 1)
  end

  def write_out_first_column(grid, 10) do
    grid
  end

  def write_out_first_column(grid, counter) do
    new_grid = set_element(grid, counter, 0, 1)
    write_out_first_column(new_grid, counter + 1)
  end

  def create_2d_list(rows, cols) do
    for _ <- 1..rows, do: for(_ <- 1..cols, do: nil)
  end

  def get_element(grid, r, c) do
    grid |> Enum.at(r) |> Enum.at(c)
  end

  def set_element(grid, r, c, new_value) do
    grid
    |> List.update_at(r, fn row -> List.replace_at(row, c, new_value) end)
  end
end

# 调用并打印最终结果
Euler.euler_15() |> IO.inspect()

关键修改点 #

1. 所有递归函数的终止分支都返回当前的grid，确保状态能向上传递。
2. 每次修改grid后生成新的变量（比如new_grid），并将其传给下一次递归调用。
3. write_out_row返回write_out_column的结果，fill_out_remainder用更新后的grid继续递归。
4. 简化了set_element的实现，用List.update_at更符合Elixir的管道风格。

内容的提问来源于stack exchange，提问作者Kevin