<p>It's essentially because not all GPUs can support function calls&mdash;and even if they can, function calls may be quite slow or have limitations such as a very small stack depth.</p>

<p>Shader code and GPU compute code may appear to have function calls all over the place, but under normal circumstances they're all 100% inlined by the compiler. The machine code executed by the GPU contains branches and loops, but no function calls. However, recursive function calls cannot be inlined for obvious reasons. (Unless some of the arguments are compile-time constants, in such a way that the compiler can fold them and inline the entire tree of calls.)</p>

<p>In order to implement true function calls, you need a stack.  Most of the time, shader code doesn't use a stack at all&mdash;GPUs have large register files and shaders can keep all their data in registers the whole time.  It's difficult to make a stack work because (a) you would need a lot of stack space to provide for all the many warps that can be in flight at a time, and (b) the GPU memory system is optimized for batching together a lot of memory transactions to achieve high throughput, but this comes at the expense of latency, so my guess is stack operations like saving/restoring local variables would be awfully slow.</p>

<p>Historically, hardware-level function calls haven't been too useful on the GPU, as it has made more sense to inline everything in the compiler.  So GPU architects haven't focused on making them fast.  Probably some different tradeoffs could be made, if there is a demand for efficient hardware-level calls in the future, but (as with everything in engineering) it will incur a cost somewhere else.</p>

<p>As far as raytracing is concerned, the way people usually handle this sort of thing is by creating queues of rays that are in the process of being traced.  Instead of recursing, you add a ray to a queue, and at the high level somewhere you have a loop that keeps processing until all the queues are empty.  It does require significant reorganization of your rendering code if you're starting from a classic recursive raytracer, though.  For more info, a good paper to read on this is <a href="https://research.nvidia.com/publication/megakernels-considered-harmful-wavefront-path-tracing-gpus">Wavefront Path Tracing</a>.</p>

CC BY-SA 3.0
2015-08-29T03:03:43.217Z
I'm reluctant to share this secret sauce, but I've had pretty good luck having a fixed maximum bounce count and having a stack of a fixed size (and a loop with a fixed number of iterations) to handle this. Also (and this is the real secret sauce imo!) I have my materials be either reflective or refractive but never both, which makes it so rays don't split when they bounce. The end result of all this is recursive type raytraced rendering, but through fixed size iteration, not recursion.
Alan Wolfe
CC BY-SA 3.0
2015-08-31T20:34:32.567Z
Like tail recursion?
Tanmay Patil
CC BY-SA 4.0
2019-07-06T18:46:35.430Z
You wouldn't need a stack to perform tail recursion, since tail-recursive functions can be converted to iterative functions. Does the OpenCL compiler not do this automatically?
Anderson Green
CC BY-SA 4.0
2024-02-11T17:39:20.410Z
I've implemented [recursion in GLSL](https://stackoverflow.com/a/77470186/975097) by macro expansion, and this should be possible in OpenCL as well.
Anderson Green
CC BY-SA 4.0
2020-05-28T05:07:04.800Z
It is also possible to implement ray tracing algorithm using a `while` loop if the color contribution of each ray can be modeled linearly. This would eliminate the need for call stack, thus effectively eliminating the need for a hardcoded bounce count in shader code. Then you can set the bounce count from the host program
Kaan E.
CC BY-SA 3.0
2015-08-29T02:17:36.830Z
2015-08-29T02:17:36.830Z
Nathan Reed
<p>I'd like to use OpenCL to accelerate rendering of raytraced images, but I notice that the <a href="https://en.wikipedia.org/wiki/OpenCL#OpenCL_C_language">Wikipedia page</a> claims that recursion is forbidden in Open CL. Is this true? As I make extensive use of recursion when raytracing, this will require a considerable amount of redesign in order to benefit from the speed up. What is the underlying restriction that prevents recursion? Is there any way around it?</p>

CC BY-SA 3.0
2015-08-29T02:04:27.370Z
GPUs work in a different way. (Some architectures) don't have the concept of a global "program stack", so recursive function calls are not possible in those. OpenCL probably adopts the lowest common denominator, thus disallowing it completely to remain portable across GPUs. Newer CUDA hardware seems to have introduced support for recursion at some point: http://stackoverflow.com/q/3644809/1198654
glampert
CC BY-SA 4.0
2020-05-28T04:59:30.253Z
I recently suggested a non recursive implementation of ray_color function of the book Raytracing in One Weekend, it might help to get you started: https://github.com/RayTracing/raytracing.github.io/issues/624
Kaan E.
<raytracing><opencl><gpgpu>
Why is recursion forbidden in OpenCL?
trichoplax is on Codidact now
# Why is recursion forbidden in OpenCL?

(Asked by: username_0 on 2015-08-28)

I'd like to use OpenCL to accelerate rendering of raytraced images, but I notice that the [Wikipedia page](https://en.wikipedia.org/wiki/OpenCL#OpenCL_C_language) claims that recursion is forbidden in Open CL. Is this true? As I make extensive use of recursion when raytracing, this will require a considerable amount of redesign in order to benefit from the speed up. What is the underlying restriction that prevents recursion? Is there any way around it?

**Tags:** raytracing, opencl, gpgpu

> **Comments:**
> **username_1**: GPUs work in a different way. (Some architectures) don't have the concept of a global "program stack", so recursive function calls are not possible in those. OpenCL probably adopts the lowest common denominator, thus disallowing it completely to remain portable across GPUs. Newer CUDA hardware seems to have introduced support for recursion at some point: http://stackoverflow.com/q/3644809/1198654  
> **username_2**: I recently suggested a non recursive implementation of ray_color function of the book Raytracing in One Weekend, it might help to get you started: https://github.com/RayTracing/raytracing.github.io/issues/624  

---

## 1 answers

### Answer by username_3 on 2015-08-29. Score: 24 | Accepted answer

It's essentially because not all GPUs can support function calls—and even if they can, function calls may be quite slow or have limitations such as a very small stack depth.

Shader code and GPU compute code may appear to have function calls all over the place, but under normal circumstances they're all 100% inlined by the compiler. The machine code executed by the GPU contains branches and loops, but no function calls. However, recursive function calls cannot be inlined for obvious reasons. (Unless some of the arguments are compile-time constants, in such a way that the compiler can fold them and inline the entire tree of calls.)

In order to implement true function calls, you need a stack. Most of the time, shader code doesn't use a stack at all—GPUs have large register files and shaders can keep all their data in registers the whole time. It's difficult to make a stack work because (a) you would need a lot of stack space to provide for all the many warps that can be in flight at a time, and (b) the GPU memory system is optimized for batching together a lot of memory transactions to achieve high throughput, but this comes at the expense of latency, so my guess is stack operations like saving/restoring local variables would be awfully slow.

Historically, hardware-level function calls haven't been too useful on the GPU, as it has made more sense to inline everything in the compiler. So GPU architects haven't focused on making them fast. Probably some different tradeoffs could be made, if there is a demand for efficient hardware-level calls in the future, but (as with everything in engineering) it will incur a cost somewhere else.

As far as raytracing is concerned, the way people usually handle this sort of thing is by creating queues of rays that are in the process of being traced. Instead of recursing, you add a ray to a queue, and at the high level somewhere you have a loop that keeps processing until all the queues are empty. It does require significant reorganization of your rendering code if you're starting from a classic recursive raytracer, though. For more info, a good paper to read on this is [Wavefront Path Tracing](https://research.nvidia.com/publication/megakernels-considered-harmful-wavefront-path-tracing-gpus).

> **Comments:**
> **username_4**: I'm reluctant to share this secret sauce, but I've had pretty good luck having a fixed maximum bounce count and having a stack of a fixed size (and a loop with a fixed number of iterations) to handle this. Also (and this is the real secret sauce imo!) I have my materials be either reflective or refractive but never both, which makes it so rays don't split when they bounce. The end result of all this is recursive type raytraced rendering, but through fixed size iteration, not recursion.  
> **username_5**: Like tail recursion?  
> **username_6**: You wouldn't need a stack to perform tail recursion, since tail-recursive functions can be converted to iterative functions. Does the OpenCL compiler not do this automatically?  
> **username_2**: It is also possible to implement ray tracing algorithm using a `while` loop if the color contribution of each ray can be modeled linearly. This would eliminate the need for call stack, thus effectively eliminating the need for a hardcoded bounce count in shader code. Then you can set the bounce count from the host program  
> **username_6**: I've implemented [recursion in GLSL](https://stackoverflow.com/a/77470186/975097) by macro expansion, and this should be possible in OpenCL as well.  

---

