Find limit of recursion: Difference between revisions

Content added Content deleted
(Add ZIg example with showcase of force-enabling and force-disabling tail-recursion elimination, thus making behaviour consistent in all optimization modes.)
Line 3,387: Line 3,387:
* The <code>CP</code> instruction only compares the accumulator to an 8 bit register, so to compare HL to BC we actually have to subtract them. If the result is zero, they were the same to begin with.
* The <code>CP</code> instruction only compares the accumulator to an 8 bit register, so to compare HL to BC we actually have to subtract them. If the result is zero, they were the same to begin with.
* If they're different, then the act of pushing AF clobbered the stack pointer we backed up in step 1. This means recursion is at its limit, so quit looping and halt the CPU.
* If they're different, then the act of pushing AF clobbered the stack pointer we backed up in step 1. This means recursion is at its limit, so quit looping and halt the CPU.

=={{header|Zig}}==
{{Trans|C}}

===Force-disable TRE===
'''Works with:''' 0.11.x, 0.12.0-dev.1381+61861ef39

To force-disable "simple tail recursion elimination" (STRE) for all optimize modes, we can use "never_tail" field of enum "std.builtin.CallModifier". It works not as hint, but as a hard requirement, so if it's impossible to fulfill, compile error is outputted.
<syntaxhighlight lang="zig">const std = @import("std");

fn recurse(i: c_uint) void {
std.debug.print("{d}\n", .{i});
// We use wrapping addition operator here to mirror C behaviour.
@call(.never_tail, recurse, .{i +% 1});
}

pub fn main() void {
recurse(0);
return;
}</syntaxhighlight>

Segmentation fault occurs at different values of "i", depending on running platform, but on my platform (with stack size reported by ulimit as 16384) both C and Zig versions (compiled without optimizations output last value in approximately [523500, 524000] range.

gcc compiler with -O2 flag eliminated tail recursion, as mentioned in second example from C section, but in this Zig example recurse function is never turned into loop, even when enabling different optimization modes — we explicitly prohibited compiler from doing it in any optimize/build mode!

===Force-enable TRE===
'''Works with:''' 0.11.x, 0.12.0-dev.1381+61861ef39

Similarly, we can force-enable mentioned optimization in all optimize modes by using enum field "always_tail". It's (again) a hard requirement and will emit compile error if this requirement is impossible to complete.
<syntaxhighlight lang="zig">const std = @import("std");

fn recurse(i: c_uint) void {
std.debug.print("{d}\n", .{i});
// We use wrapping addition operator here to mirror C behaviour.
@call(.always_tail, recurse, .{i +% 1});
}

pub fn main() void {
recurse(0);
return;
}</syntaxhighlight>

On my machine, segmentation fault never occurs, instead resulting in infinite loop in all optimize modes (as intended).


=={{header|zkl}}==
=={{header|zkl}}==
Retrieved from "https://rosettacode.org/wiki/Find_limit_of_recursion"