Tail Call Optimization

Ruby
1

Just curious about the state of tail call optimization in Ruby… I tried a few examples on the internet and kept getting stack overflow errors when the calls exceeded 10000…

BTW my Ruby implementation is:

ruby 2.5.1p57 (2018-03-29 revision 63029) [x86_64-linux-gnu]

2

Hey @G4143,

Would you please share the code that you tested? Meanwhile, I would recommend this article regard to this topic: Recursion, Tail Call Optimization and Recursion.

3

Please note that I just want to know if Ruby supports(my implementation of Ruby supports) tail call optimization.

If it does, then I’ll use it. If it doesn’t, then I’ll stay away from deep recursion,

4

I don’t have the code anymore but I know I couldn’t get the code on these links to work either.

Tail Call Code
Tail Call Code

5

Here’s a quick example which fails when the recursion gets deep…

#! /usr/bin/env ruby

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

def fact(n, acc = 1)

	if n < 1
		acc
	else
		fact(n - 1, acc * n)
	end

end

if __FILE__ == $0

	print "Enter number: "
	num = gets.to_i
	puts "The fact is: #{fact(num)}"

end
6

Just an opinion, you should stay away from recursion. The reason is that it can introduce new bugs to your programs and lead to headache. Recursion can’t even provide an extra speed, here’s my simplest factorial methods and their benchmark:

Screenshot%20from%202019-09-04%2012-44-15
Screenshot from 2019-09-04 12-44-15.png668×930 649 KB

You see that recursion introduces bugs while it doesn’t give you something more than a program with loops. It’s good to learn recursion, but I think you shouldn’t use it often in your professional programs. If you made a mistake in the fact, it will use a huge amount of memory ultimately freezing your system. It’s dangerous…

7

I have to respectfully disagree. The problems with recursion is typically people who don’t understand recursion.

A simple inspection of the current state of software will expose that recursive data structures are everywhere(webpages, abstract syntax trees, markup languages, AI, etc). To brush-off recursion is to brush-off a big chunk of the software industry.

When you step away from the introductory recursion examples, you’ll find a whole world of possibilities that includes elaborate solutions that embraces recursion and lambdas and closures.

I would consider that whole languages(OCaml, Haskell, Elm, PureScript, Scala, lisp(and derivatives), etc) prefer recursion over looping constructs.

8

Yeah that’s true. Even many basic sorting algorithm uses recursion… You can do those stuffs with loops, and I am pretty sure about that, but the code will get larger…
Here’s a post…

Anyways, I would consider loops when you are calculating something depending on the value given by the user.

Pardon my ignorance, but is there any benefit of recursion over loops (except recursion makes the code simpler)?

9

In my experience, recursive solutions become easier(usually much easier) when the recursive problem becomes more complex and looping solutions become unmanageable when the recursive problem becomes more complex.

Generally speaking, the more complex the recursive problem is, the more you should be reaching for recursion as a solution. Its just a natural fit for the problem.

disclaimer… Most languages which promote recursion over looping are designed to handle recursion with convenient features like type deconstruction and pattern matching built right into the language.

1 Like