Почему эта внутренняя функция F # не является хвостовой рекурсивной? - PullRequest
Новая
       50

Почему эта внутренняя функция F # не является хвостовой рекурсивной?

2 голосов
/ 12 марта 2011

Если я вызываю эту функцию с очень высоким начальным значением currentReflection, я получаю исключение переполнения стека, которое указывает на то, что функция не является рекурсивной (правильно?).Насколько я понимаю, если рекурсивный вызов был последним вычислением функции, то он должен быть оптимизирован компилятором как хвостовая рекурсивная функция для повторного использования текущего кадра стека.Кто-нибудь знает, почему это не так здесь? 

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 = List.minBy(fun x -> x.t) intersections
                    let reflectivity = intersection.sphere.material.reflectivity
                    primaryColor + traceColorAt newIntersection newRay  (currentReflection - 1) * reflectivity

Ответы [ 2 ]

4 голосов
/ 12 марта 2011

Рекурсивный вызов traceColorAt появляется как часть большего выражения. Это предотвращает оптимизацию хвостового вызова, потому что дальнейшие вычисления необходимы после возврата traceColorAt.

Чтобы преобразовать эту функцию в хвостовую рекурсию, вы можете добавить дополнительный параметр аккумулятора для primaryColor. Самый внешний вызов traceColorAt передал бы значение "ноль" для primaryColor (черный?), И каждый рекурсивный вызов суммируется в вычислении, которое он вычисляет, например, код будет выглядеть примерно так: 

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

Если вы хотите скрыть дополнительный параметр от вызывающих, введите вспомогательную функцию, выполняющую основную часть работы, и вызовите ее из traceColorAt.

4 голосов
/ 12 марта 2011

Хвостовая рекурсия работает, если функция просто возвращает результат другой функции.В этом случае у вас есть primaryColor + traceColorAt(...), что означает, что оно не просто возвращает значение функции, но и добавляет к нему что-то.

Это можно исправить, передав текущий накопленный цвет какпараметр.

...