Wrox Programmer Forums

Need to download code?

View our list of code downloads.

Go Back   Wrox Programmer Forums > Other Programming > BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition
Password Reminder
Register
Register | FAQ | Members List | Calendar | Search | Today's Posts | Mark Forums Read
BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition
This is the forum to discuss the Wrox book Programming Interviews Exposed: Secrets to Landing Your Next Job, 3rd Edition by John Mongan, Noah Kindler, Eric Giguere; ISBN: 978-1-118-26136-1
Welcome to the p2p.wrox.com Forums.

You are currently viewing the BOOK Programming Interviews Exposed: Secrets to Landing Your Next Job 3rd Edition section of the Wrox Programmer to Programmer discussions. This is a community of tens of thousands of software programmers and website developers including Wrox book authors and readers. As a guest, you can read any forum posting. By joining today you can post your own programming questions, respond to other developersí questions, and eliminate the ads that are displayed to guests. Registration is fast, simple and absolutely free .
DRM-free e-books 300x50
Reply
 
Thread Tools Display Modes
  #1 (permalink)  
Old April 24th, 2013, 07:14 PM
Registered User
Points: 5, Level: 1
Points: 5, Level: 1 Points: 5, Level: 1 Points: 5, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Apr 2013
Posts: 1
Thanks: 0
Thanked 0 Times in 0 Posts
Default Is the tail-recursion example really tail-recursive?

On page 108 you first present this function:

Code:
int factorial(int n){
    if (n > 1) { /* Recursive case */
        return factorial(n-1) * n;
    } else {     /* Base case */
        return 1;
    }
}
You then write:

Quote:
Note that when the value returned by the recursive call is itself immediately returned, as in the preceding definition for factorial, the function is tail-recursive.
But, the call to factorial is not immediately returned, it has to wait for it to be multiplied with n and can thus not discard this stack frame, as far as I can tell...
Reply With Quote
  #2 (permalink)  
Old April 26th, 2013, 08:19 AM
Wrox Author
Points: 51, Level: 1
Points: 51, Level: 1 Points: 51, Level: 1 Points: 51, Level: 1
Activity: 0%
Activity: 0% Activity: 0% Activity: 0%
 
Join Date: Oct 2012
Posts: 10
Thanks: 0
Thanked 1 Time in 1 Post
Default

You are correct, that example is not really an example of tail recursion. For it to be true tail recursion it would have to call itself as the very last operation and do nothing else.

You can make it tail recursive by splitting it into two functions:

Code:
int factorial(int n){
    return factorial(n, 1);
}

int factorial(int n, int counter){
    if( n == 0 ){
        return counter;
    }
    return factorial(n-1, n * counter);
}
(Well, technically you only need the second function -- the first is a convenience function.)
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Open Source GUI Tail Tool madanuuk Linux 1 September 27th, 2006 11:03 AM
Recursion lincsimp XSLT 1 August 16th, 2005 05:26 PM
recursion yui0329 C# 6 April 28th, 2005 10:36 AM
Recursion shan9 JSP Basics 0 November 17th, 2004 09:29 PM
recursion nulogix PHP How-To 1 June 28th, 2004 04:58 PM



All times are GMT -4. The time now is 05:06 AM.


Powered by vBulletin®
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
© 2013 John Wiley & Sons, Inc.