时间戳

首页 > 解决方案 > 无论输入递归如何，一个函数是否只调用自己一次？

haskell - 无论输入递归如何，一个函数是否只调用自己一次？

问题描述

考虑一个函数，不管输入是什么，它最多执行一次操作并调用自身一次（不超过一个“递归”级别）。这个函数被认为是递归的吗？

例子：

join1 :: [Maybe a] -> [a]
join1 [Just x] = [x]
join1 [Nothing] = []
join1 (x) = concat (map join1 (map (\k->[k]) x))

在这种情况下，当调用：Join1 [nothing, just 2, just 3,...] 会在每个元素上调用join1函数，立即进入终止条件

标签： haskellrecursion

解决方案

是的，它是递归的。运行时的调用次数和运行时递归深度无关。如果出现在 中，则说定义x = expression是递归的，指的是我们现在正在定义的。xexpressionx

简而言之，“递归”是定义的句法属性，不考虑运行时行为。

作为一个愚蠢的例子，这个定义是递归的，即使它在运行时从不调用自己。即使它可以简单地简化为非递归的。

identity :: a -> a
identity x = (\_ -> x) identity

推荐阅读