1 Replies - 10042 Views - Last Post: 09 October 2007 - 10:01 PM Rate Topic: -----

#4 spullen  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 10
  • View blog
  • Posts: 356
  • Joined: 22-March 07

Re: Tail Recursion vs. Tree Recursion

Posted 09 October 2007 - 10:00 PM

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.
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!!!
Was This Post Helpful? 1

#5 skyhawk133  Icon User is offline

  • Head DIC Head
  • member icon

Reputation: 1858
  • View blog
  • Posts: 20,275
  • Joined: 17-March 01

Re: Tail Recursion vs. Tree Recursion

Posted 09 October 2007 - 10:01 PM

Quote

BTW, ruby tutorial section!!!


You gonna write the first few tutorials for it? :) If so, I'll make it right now.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1