I have been taking a course on programming paradigms and one thing that we have learned about is different types of recursion. I really never thought about a different way to write recursive functions until I saw tail recursion.
So here is a little test with Ruby and the differences between tree and tail recursion and the most basic recursive methods (factorial). Notice the execution times.
CODE
def tailFactorial(n, result)
if n == 1
return result
else
tailFactorial((n - 1), (result * n))
end
end
def factorial(n)
if n == 1
return 1
else
return n * factorial(n-1)
end
end
puts "Here is a tail recursive approach to the factorial problem\n"
puts tailFactorial(8, 1)
puts "\n"
puts "Here is a tree recursive approach to the factorial problem\n"
puts factorial(8)
puts "\nExecution times\n"
puts "Tree recursion: \n"
st = Time.now
result = factorial(8)
tt = Time.now - st
puts "Tree recursive approach, 8! = " + result.to_s + ", and was done in " + tt.to_s + "\n"
puts "Tail Recursion: \n"
st = Time.now
result = tailFactorial(8, 1)
tt = Time.now - st
puts "Tail recursive approach, 8! = " + result.to_s + ", and was done in " + tt.to_s + "\n"
The reason tail recursion has a faster execution time is because it doesn't have to pop anything off the stack to get the result. The result is just passed as a parameter into the method.
BTW, ruby tutorial section!!!
9 Oct, 2007 - 10:00 PM
If so, I'll make it right now.
|