Rand monad 无限递归问题咨询及相关代码分析

先把你的代码补全并格式化一下（看起来randomTree1没写完，我帮你补了合理的结尾）：

import Control.Monad.Random

data Tree = Node Tree Tree Tree Tree | Leaf Bool deriving (Show)

randomTree' :: (RandomGen a) => Int -> Rand a Tree
randomTree' 0 = do
    r <- getRandom
    return $ Leaf r
randomTree' depth = do
    let d = depth - 1
    a <- randomTree' d
    b <- randomTree' d
    c <- randomTree' d
    d <- randomTree' d  -- 这里有个小坑：变量名和前面的d重名了，可读性很差
    r <- getRandom
    if r then return $ Node a b c d else randomTree' 0

randomTree1 :: Int -> Tree
randomTree1 seed = evalRand (randomTree' 4) (mkStdGen seed)

先提个小问题：变量名冲突 #

你在randomTree' depth里先定义了let d = depth-1，然后又用d <- randomTree' d，虽然Haskell的词法作用域允许这么写，但内层的d会覆盖外层的，很容易让人看懵，建议改成不同的名字，比如：

randomTree' depth = do
    let nextDepth = depth - 1
    a <- randomTree' nextDepth
    b <- randomTree' nextDepth
    c <- randomTree' nextDepth
    subTreeD <- randomTree' nextDepth
    r <- getRandom
    if r then return $ Node a b c subTreeD else randomTree' 0

回到你的核心疑问：会不会有无限递归？ #

放心，这段代码不会出现无限递归，原因很明确：

• 递归的终止条件非常清晰：当depth == 0时，直接生成一个Leaf节点，不会再往下递归。
• 只要depth > 0，所有递归调用的参数都是depth-1，每次递归的深度都会严格递减，直到触碰到depth=0的终止条件。
• 哪怕最后抛随机数得到False，调用的也是randomTree' 0，这是终止分支，不会继续递归下去。

可能你担心Rand Monad会不会影响递归的终止？其实完全不会——Rand Monad只是帮你封装了随机状态的传递逻辑，递归的终止完全由depth参数控制，随机数只是决定最后返回Node还是Leaf，不管哪种情况，递归都是有限次数的。

额外提个性能小提醒 #

虽然没有无限递归，但当depth比较大的时候，这个函数的递归调用量会爆炸：比如depth=4时，如果每次都返回Node，那总共会有4^4 + 4^3 + 4^2 +4^1次递归调用，内存和CPU消耗会增长得很快，这是这种四叉树结构本身的问题，不是递归逻辑的bug。

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