Today I Learned

Some of the things I've learned every day since Oct 10, 2016

24: Tail Recursion

Tail recursion can be thought of a procedure making a recursive call at the tail end of itself. That is, once the result is returned from this recursive call, no more work has to be done with this result in order to obtain the result of the parent call. This means there is no need to maintain a stack of recursive instances of the procedure, and the final recursive call which reaches the base case can simply return the result directly, without passing it up through the stack.

This means that when a procedure is tail recursive, it can be performed in constant space instead of the typical linear space of a call stack.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: