Jump to content





Recent Status Updates

  • Photo
      16 Apr
    Kadence

    If you're reading this, you're on my profile and I know you're on my profile because I'm probably viewing yours.

    Show comments (6)
  • Photo
      10 Apr
    Poe

    Finally (and hopefully) i'm getting a team together that knows a little of this and a little of that; and maybe all my open source projects that are half written can begin to be released. :)

View All Updates
Photo
- - - - -

Tail recursion

recursion

  • Please log in to reply
12 replies to this topic

#1 Chinmoy

Chinmoy

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 365 posts

Posted 12 June 2008 - 10:28 PM

Tail Recursion



A recursive function is said to be tail recursive if all recursive calls within it are tail recursive. A recursive call is tail recursive when it is the last statement that will be executed within the body of a function and its return value is not a part of an expression. Tail-recursive functions are characterized as having nothing to do during the unwinding phase. This characteristic is important because most modern compilers automatically generate code to take advantage of it.

When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack. The compiler can do this because the recursive call is the last statement to be executed in the current activation; thus, there is nothing left to do in the activation when the call returns. Consequently, there is no reason to keep the current activation around. By replacing the current activation record instead of stacking another one on top of it, stack usage is greatly reduced, which leads to better performance in practice. Thus, we should make recursive functions tail recursive whenever we can.

To understand how tail recursion works, let's revisit computing a factorial recursively. First, it is helpful to understand the reason the previous definition was not tail recursive. Recall that the original definition computed n! by multiplying n times (n - 1)! in each activation, repeating this for n = n - 1 until n = 1. This definition was not tail recursive because the return value of each activation depended on multiplying n times the return value of subsequent activations. Therefore, the activation record for each call had to remain on the stack until the return values of subsequent calls were determined. Now consider a tail-recursive definition for computing n!, which can be defined formally as:



This definition is similar to the one presented earlier, except that it uses a second parameter, a (initially set to 1), which maintains the value of the factorial computed thus far in the recursive process. This prevents us from having to multiply the return value of each activation by n. Instead, in each recursive call, we let a = na and n = n - 1. We continue this until n = 1, which is the terminating condition, at which point we simply return a. Figure 3.4 illustrates the process of computing 4! using this approach. Notice how there is no work that needs to be performed during the unwinding phase, a signature of all tail-recursive functions.


int facttail(int n, int a) 
{

	if (n < 0)
	   return 0;
	else if (n == 0)
	   return 1;
	else if (n == 1)
	   return a;
	else
	   return facttail(n - 1, n * a);
}


  • -2

God is real... unless declared an integer

my blog :: http://techarraz.com/


#2 Guest_Jordan_*

Guest_Jordan_*
  • Guest

Posted 13 June 2008 - 05:01 AM

It seems that this article comes from IBM Press - 1565924533 - Mastering Algorithms with C

And once checked most of your other articles are copied from websites. We don't allow copying of tutorials and articles. You need to post original tutorials please. Please PM with an explanation otherwise I am going to delete the tutorials that have been found copied.
  • 0

#3 Xav

Xav

    CC Mentor

  • VIP Member
  • PipPipPipPipPipPipPipPip
  • 8,356 posts

Posted 13 June 2008 - 09:55 AM

Did you get a PM?
  • 0
If you enjoy reading this discussion and are thinking about commenting, why not click here to register and start participating in under a minute?

#4 Chinmoy

Chinmoy

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 365 posts

Posted 13 June 2008 - 10:56 PM

Yes, Xav. I did send a PM. My point is that the articles have to have a source! There are many articles i posted at codecall which i have received from my friends in the course of various discussions, debates and such...But they are compiled by a friend who gives it to us at the end of the discussion.
Now, how can i have any idea if it already exists somwhere else! From now on i'll check over the internet and then post anything! Thats the best I can do!

The -rep hurts...
  • 0

God is real... unless declared an integer

my blog :: http://techarraz.com/


#5 TcM

TcM

    CC Mentor

  • VIP Member
  • PipPipPipPipPipPipPipPip
  • 7,563 posts

Posted 14 June 2008 - 07:04 AM

Do you participate in a group (maybe at school) and the teacher/leader give you these as notes? And you thought it would be a good idea to post them here?

Maybe the leader/teacher copied them from other sites rather than making them himself...
  • 0

#6 Chinmoy

Chinmoy

    CC Addict

  • Just Joined
  • PipPipPipPipPip
  • 365 posts

Posted 14 June 2008 - 07:15 AM

Well, Tcm, Im not in school. And These are not notes given by teachers.
We have overnight discussions in the hostel, and one of my friends compiles these notes and gives them back to us. I have a fair understanding of anything I post. And I did not copy! There are my fair contribution in the discussions. And I apologize to all the codecall members if it has violated any rule or offended anyone.
  • 0

God is real... unless declared an integer

my blog :: http://techarraz.com/


#7 TcM

TcM

    CC Mentor

  • VIP Member
  • PipPipPipPipPipPipPipPip
  • 7,563 posts

Posted 14 June 2008 - 08:17 AM

I didn't say that you copied.

Your friend finds the information online and distributes it to you, and you submitted some of the notes here.. I didn't blame you.. nor your friend.
  • 0

#8 Xav

Xav

    CC Mentor

  • VIP Member
  • PipPipPipPipPipPipPipPip
  • 8,356 posts

Posted 14 June 2008 - 08:47 AM

Then who is to blame?
  • 0
If you enjoy reading this discussion and are thinking about commenting, why not click here to register and start participating in under a minute?

#9 TcM

TcM

    CC Mentor

  • VIP Member
  • PipPipPipPipPipPipPipPip
  • 7,563 posts

Posted 14 June 2008 - 08:51 AM

I don't blame anyone. I just asked him a question.
  • 0

#10 TkTech

TkTech

    The Crazy One

  • Retired Mod
  • PipPipPipPipPipPipPip
  • 1,144 posts
  • Location:Ottawa, Ontario

Posted 14 June 2008 - 08:53 AM

Technically, he's still copying off of his friend -> Its not original no matter what.
  • 0
Helpful CODECALL Links: Join Us, Guidelines, FAQ, Post a Tutorial

#11 Guest_Jordan_*

Guest_Jordan_*
  • Guest

Posted 14 June 2008 - 09:18 AM

I think it is fine. In the future Chinmoy, ensure that the notes don't exist anywhere on the internet before you post them.
  • 0

#12 TcM

TcM

    CC Mentor

  • VIP Member
  • PipPipPipPipPipPipPipPip
  • 7,563 posts

Posted 14 June 2008 - 09:31 AM

Yeah... that doesn't mean he can't use his friend's notes. Google doesn't know that :D

@Jordan: You finished mowing the loan finally? Lol
  • 0





Also tagged with one or more of these keywords: recursion