Interview Questions : tail recursion for C/C++ programmers
my latest essay talking about a (hard) interview questions on
Tail Recursion for C/C++ Programmers
Tail Recursion for C/C++ Programmers
posted by dmh2000 at 8:41 AM
Thursday, June 29, 2006
Previous Posts
6 Comments:
I pretty much knew this, but I didn't know I knew it.
Great article! Very clearly explained. I knew how to do it intuitively but didn't realise the mechanical procedure until you showed me!
One oddity - after the definition for int sum2_cons, you explain about the compiler warning of not returning a value, and even say that "The compiler just isn't smart enough to figure out what is going on". But technically, you're returning garbage and aren't using it. sum2_cons should be declared void, and there would be no problem.
I'm a Scheme programmer, recovering from years of programming in C/C++. Still, there is no denying that Scheme would not be Scheme without C to implement it. Although, technically there are a few native Scheme to object code compilers, the vast majority utilize Scheme->C compilers and then let the decades of optimizations built into C compilers do their magic to get Scheme to be as fast as it is.
I thought your example was very clean and succinct. As it turns out I was after some information on how Scheme compilers got tail recursion to work in a non tail-recursive language like C. While I'm sure the pattern you found for turning recursive functions into iterative functions gets the gist of the idea, I'm not convinced that an optimizing Scheme->C compiler necessarily goes about it in that fashion. But it's an interesting paradigm to have had explained so well.
Very nicely done.
You have done a good job here,Keep it up.
This was nicely done for the most part.
The nonsense about the compiler warning and returning int needs to be cleaned up.
First off, you should really just return void.
Second, the execution will continue after the call to sum_cons and will just return garbage (as a previous commenter pointed out).
Sorry ... but I can't make out ... what if I don't know the "count", how can I iterate? Currently, working on a 3D engine and need to use recursive calls cause its impossible to know the dimension of the multi-dimensional array for the 3D objects. And I need to optimize!
Post a Comment
<< Home