时间戳

首页 > 解决方案 > 难以分析函数的递归步骤

recursion - 难以分析函数的递归步骤

问题描述

我目前正在学习 OCaml 以进行函数式编程考试，并且在尝试在本练习中遵循此递归函数的步骤时遇到了一些困难。任务是在 int N-ary 树中找到最昂贵的叶子（叶子成本由通往叶子的路径上的整数之和给出）。

这是类型定义：

type 'a ntree = Ntree of 'a * 'a ntree list

这是练习的辅助功能

let rec maxpair = function
  | [] -> failwith "empty list"
  | [(x, y)] -> (x, y)
  | (x, y) :: (a, b) :: rest -> 
      if y > b then maxpair ((x, y) :: rest) 
      else maxpair ((a, b) :: rest)

最后是最后的功能

let rec leaf_cost = function
  | Ntree (x, []) -> (x, x)
  | Ntree (x, tlist) -> 
      let (y, c) = maxpair (List.map leaf_cost tlist)
      in 
      (y, c + x)

这是练习的解决方案，这意味着它有效。但是我在尝试分析函数中的每个递归步骤时遇到了麻烦，特别是因为我对let (y, c) ... in (y, c + x)声明有点困惑。

标签： recursionfunctional-programmingtreeocaml

解决方案

给定一棵树，leaf_cost返回一对(v, c)，它是具有最大成本的叶节点的值v，以及成本c。

在基本情况下，当没有子节点时，值为x，其成本也为x。

在一般情况下，节点由整数x和子节点列表children（aka tlist）组成。

List.map leaf_cost children

上面的表达式是一个对的列表，每一个都是最大叶及其在以每个子节点为根的相应子树中的相关成本。

通常，可能有多个叶子具有相同的成本，但您的问题忽略了这一点，并以实现定义的方式选择迄今为止所有成本中成本最大的一对。

这是通过调用 来完成的maxpair，它给出了一个对(y, c)，其中第一个叶子在递归获得的所有对中y具有最大成本。c

知道在所有子树中，(y, c)是一个具有成本的叶子c，并且您当前的节点权重x为 ，当前节点的成本是c + x。这就是为什么在一般情况下返回值是(y, c+x)，跟踪导致此成本的子树中的叶子。

推荐阅读