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.
精彩评论