# Tail Recursion vs. Tree Recursion

Page 1 of 1

## 1 Replies - 11355 Views - Last Post: 09 October 2007 - 10:01 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=35002&amp;s=fe437704ca2eb1efd1cabe97d51cb07e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #4 spullen

• D.I.C Regular

Reputation: 10
• 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!!!

### #5 skyhawk133

Reputation: 1900
• Posts: 20,331
• 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.