开发者

Why isn't this F# inner function tail-recursive?

If I call this function with a very high initial currentReflection value I get a stack overflow exception, which indicates that the function is not tail-recursive (correct?). My understanding was that as long as the recursive call was the final computation of the function then it should be compiler-optimized as a tail-recursive function to reuse the current stack frame. Anyone know why this isn't the case here?

let rec traceColorAt intersection ray currentReflection =
        // some useful values to compute at the start
        let matrix = intersection.sphere.transformation |> transpose |> invert
        let transNormal = matrix.Transform(intersection.normal) |> norm
        let hitPoint = intersection.point

        let ambient = ambientColorAt intersection
        let specular = specularColorAt intersection hitPoint transNormal
        let diffuse = diffuseColorAt intersection hitPoint transNormal
        let primaryColor = ambient + diffuse + specular

        if currentReflection = 0 then 
            primaryColor
        else
            let reflectDir = (ray.direction - 2.0 * norm ((Vector3D.DotProduct(ray.direction, intersection.normal)) * intersection.normal))
            let newRay = { origin=intersection.point; direction=reflectDir }
            let intersections = castRay newRay scene
            match intersections with
                | [] -> primaryColor
                | _  -> 
                    let newIntersection = L开发者_运维知识库ist.minBy(fun x -> x.t) intersections
                    let reflectivity = intersection.sphere.material.reflectivity
                    primaryColor + traceColorAt newIntersection newRay  (currentReflection - 1) * reflectivity


The recursive call to traceColorAt appears as part of a larger expression. This prevents tail call optimization because further computation is necessary after traceColorAt returns.

To convert this function to be tail recursive, you could add an additional accumulator parameter for primaryColor. The outermost call to traceColorAt would pass the "zero" value for primaryColor (black?) and each recursive call would sum in the adjustment it computes, e.g. the code would look something like:

let rec traceColorAt intersection ray currentReflection primaryColor
...
let newPrimaryColor = primaryColor + ambient + diffuse + specular
...
match intersections with
    | [] -> newPrimaryColor
    | _ ->
        ...
        traceColorAt newIntersection newRay ((currentReflection - 1) * reflectivity) newPrimaryColor

If you wish to hide the extra parameter from callers, introduce a helper function that performs the bulk of the work and call that from traceColorAt.


Tail recursion works if the function would simply return the result of another function. In this case, you have primaryColor + traceColorAt(...), which means that it is not simply returning the value of the function-- it's also adding something to it.

You could fix this by passing the current accumulated color as a parameter.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜