|
Very nice,
But i have visual studio 2003, 
I always liked the elegance of recursion...
I never understood why i learned this technique on fobenuca and not on directories,...
That was the point i wanted to make
.
It feels good to learn and achieve
|
|
|
|
|
$10 says thisDir.GetDirectories is recursive
|
|
|
|
|
Hmm I did have that thought. But the foundation of systems objects is actually exposed as database objects. So I wasn't sure. If the system uses a db, it totaly aviaods recursion.
|
|
|
|
|
Chris Losinger wrote: $10 says thisDir.GetDirectories is recursive
Okay I think you owe me $10! We can arrange for a friendly transfer thru paypal. LOL!
"If there are no subdirectories, this method returns an empty array. This method is not recursive."
MSDN: GetDirectories Method[^]
'If these guys don't use recursion here, I kinda wonder if they think recursion is a bad idea also.'
...And here at The Code Project...
'Hooray! No more memory exhaustive manual recursion for my disk traversals!'
Use LINQ to Create Music Playlists – Revisited[^]
~TheArch
modified on Wednesday, July 15, 2009 8:27 AM
|
|
|
|
|
so you only get immediate subdirs of the target dir ?
i thought the whole reason people were talking about directories here was that recursion is the natural way to get all subdirs, not just the immediate children. if you're not getting the full tree, what's the point of talking about it here ?
or am i misunderstanding something... ?
|
|
|
|
|
Chris Losinger wrote: so you only get immediate subdirs of the target dir ?
it is the full tree, if target dir = @"c:\"
The call to BaseDir is really unnecessary, if:
var TheDirectory = from dirs in thisDir.GetDirectories("*",SearchOption.AllDirectories)
orderby dirs.FullName
select dirs;
\\Where thisDir = new DirectoryInfo(@"C:\");
\\This gets the whole tree. No recursion.
I would decompile the System.IO class but microsoft doesn't really like it when you do that. I will take thier word that the method is not recursive.
If perhaps using the search option, does make the methods recursive (don't really understand MSDN on this) they do not have the same remark for this method using this option. But it would still be possible if you used the base method which states not recursive, then used a lambda to get all the childern. I would guess this is what the search option does.
My point is yes, recursion is a natural for humans and nature. However it's not natural for computers. We simply make computers do the things we think is natural because it describs our domain.
What is natural to humans is not necessarly natural to computers. Thinking like the computer using it's imposed domain, is how 99% of performance enhancments are made.
The interviwer imposed a domain on the problem which introduces the human factor. Adding the human factor to the problem causes bad things to happen. My point to the interviewer was this is not how to do things, esp. if performance is in question. Which performance was a big factor as I was to build a server application. I thought that it was a trick question. I thought the interviewer was testing my knowlege of how to correctly design server software. I didn't want the interviewer to think I was going to do a poor design. The interviewer did give me one thing to aid the problem. I was aloud to use a prototype language of my own design to solve the problem. So I designed a language which did allow for recursive logic, but I place a constraint on the language factored out the real recursion, so the expression of recursion was removed from the compiled code.
It's weird the prototype I designed, looks alot like F#. The prototype predated F#.
The interviewer's last comment to me was that there could be no justification to hire a lead engineer who didn't not understand recursion.
|
|
|
|
|
hmm. right you are.
cool. 
|
|
|
|
|
Thanks Chris! 
This thread has really helped my human factors. I didn't really know I had an unresolved resentment againts this interviewer.
It also helped me to lear something new: Big O Notation. This was another factor which came up in the interview. I did not go to an ivy leage college to study Computer Science, in fact I never went to college to learn computer science. I did study engineering and electronics in college at a technical college. The interviewer told me this would not be a factor in his assessment of my skill. However he did give me a problem first year Computer Science engineers study.
I sometimes wonder if the interviewer was really trying to factor me out of the equation.
|
|
|
|
|
Big O is cool. i learned it in college, but it was a decade before i really found a practical use for it (when i got into graphics programming).
|
|
|
|
|
Well, I think this is really a great question for an interview, becouse you can get a lot of conclusions depending on the answer.
If the answer was:
int BadFib(int n)
{
if (n == 1 || n == 2)
return 1;
else
return BadFib(n - 1) + BadFib(n - 2);
}
This answer means that the guy knows what recursion is, but he has no idea about algorithm complexity, and he does not mind performance at all. So, my next question would be: Can you do it better?
But now, if somebody came up with this solution:
public int GoodFib(int n)
{
return Fib(n, 1, 1);
}
private int Fib(int n, int n1, int n2)
{
if (n == 1 || n == 2)
return 1;
else if (n == 3)
return n1 + n2;
else
return Fib(n - 1, n1 + n2, n1);
}
This means that the guy knows what recursion is, he knows what algorithm complexity is, and he is worried about the performance of his code. So, my next question would be: When would yo be able to start with the job?
I guess the interviewer just wanted to know how skilled you were about programming.
modified on Tuesday, July 7, 2009 11:30 AM
|
|
|
|
|
In one of my interviews, I was asked to code a function to convert an string (char *, it was as C interview) into an int.
Considering that there are already a lot of functions that do it already, it looks stupid. Considering it was an way to know if I know how to solve problems, I did it.
Later, the interviewer was surprised, because I was the only one of the candidates to answer such question.
|
|
|
|
|
Paulo Zemek wrote: Later, the interviewer was surprised, because I was the only one of the candidates to answer such question.
That's sad. I wrote the pascal equivalent after roughly half a year of programming in high school, and then wrote the equivalent to convert a string into a float. 
I was writing custom numeric input handlers that rejected garbage keystrokes; offhand I don't recall why I didn't want to use the standard library validation/conversion functions.
The European Way of War: Blow your own continent up.
The American Way of War: Go over and help them.
|
|
|
|
|
That is exactly the point I wanted to reach.
|
|
|
|
|
Paulo Zemek wrote: In one of my interviews, I was asked to code a function to convert an string (char *, it was as C interview) into an int.
Considering that there are already a lot of functions that do it already, it looks stupid. Considering it was an way to know if I know how to solve problems, I did it.
Cool!
But how did you do it?
|
|
|
|
|
Initialized an int to zero.
Checked if the value started with a - (setting an isNegative boolean and, at the end, multiplying the value by -1).
At each char read, checked if it was an int (>= '0' && <='9'). If not, returned 0. (it was a requisite).
Multiplied the result by 10. If it was zero, nothing happened.
Got the real value of the char (c - '0'). Added this value to the integer result.
And thats it.
|
|
|
|
|
Okay after much testing I have a non recursive version:
using System;
namespace Test
{
class fib
{
double n = 0;
public double next
{
get
{
return n;
}
set
{
n = Math.Round(((Math.Pow(fib.golden(),value)) - Math.Pow((1-fib.golden()),value)) / Math.Sqrt(5));
}
}
private static double golden()
{
return (1 + Math.Sqrt(5)) / 2;
}
}
}
public static double MyFib(int n)
{
fib f = new fib();
f.next = n;
return f.next;
}
Like I said, 'recursive algroythms are a bad idea.'
GoodFib(6000)
-1142292160
MyFib(6000)
Infinity
GoodFib(1000)
1556111435
MyFib(1000)
4.3466557686938915E+208
If you change GoodFib to return a double:
GoodFib(6000)
Infinity
GoodFib(1000)
4.3466557686937428E+208
MyFib looses precision (I think):
public static double NotEqual()
{
double count;
double result1 = 0;
double result2 = 0;
for (count = 1;; count++)
{
result1 = GoodFib(count);
result2 = MyFib(count);
if (result1 != Math.Floor(result2))
break;
}
Console.WriteLine("Result1: [" + result1.ToString() + "]");
Console.WriteLine("Result2: [" + result2.ToString() + "]");
return count;
}
NotEqual()
71.0
Result1: [308061521170129]
Result2: [308061521170130] ?!?!
Not really sure which is correct. The online sources say GoodFib is right. If I was really to do something like this I would use Math Lab C# extensions. Guarinteed precision.
modified on Wednesday, July 8, 2009 2:42 AM
|
|
|
|
|
'Maybe the SS uses this formula...'
|
|
|
|
|
I think you have not got the point. What I mean is that when an intervewer asks you to solve a problem within some kind of restrictions, as "recursive way" to do "whatever", the really important thing here is not the problem itself, but the way you can solve it applying those restrictions.
That is why I have showed two possible ways to solve Fibonacci sequence in a recursive way. The first one is horrible because it has an exponential complexity, while the second one is linear. Sure, using golden proportion in this concrete case comes with a constant complexity algorithm, but you have not folowed the instructions. So, the problem here is not finding a Fibonacci number. The problem is to do it in a recursive way with a good performance. If the interviewer had asked you, for example, to find an iterative way to solve Hanoi's Tower problem, golden proportion would not be there to help you.
On the other hand, when you say recursion is bad, sorry, but you are absolutely wrong. Many abstract data types are recursive by definition, like trees or graphs. Just implement a non recursive way to find a file within a tree of folders. When you get it, do it recursive. When finished, analyze both of them, how they work and what they do under the covers. When you get finished, I think you will really appreciate the real value of recursion.
|
|
|
|
|
Yes I understand your point is valid. However, if the candidate tells the interviewer he understands recrusion and gives the text book definition and tells the interviewer that the problem is better solved using non-recrusive methods... If the interviewer does not trust the candidate it speaks bad for the company they represent.
Why are recursive algrythms bad:
IEEE Abstract - Recursive algorithms in computer science courses: Fibonacci numbersand binomial coefficients[^]
I did some BigO testing of the various algorithms, here are the results:
BadFib(40) LoopCount: [204668309] - SplitTimeMicro: [15042441.7069767]
GoodFib(40) LoopCount: [38] - SplitTimeMicro: [1171.09856140934]
MyFib(40) LoopCount: [1] - SplitTimeMicro: [6122.8452219486] - 'can be improved using the correct math lib.'
LinerFib(40) LoopCount: [41] - SplitTimeMicro: [652.317543151434]
Liner Fib:
public static double LinerFib(double n)
{
double previous = -1;
double result = 1;
double sum = 0;
for (double i = 0; i <= n; ++i)
{
sum = result + previous;
previous = result;
result = sum;
}
return result;
}
'Most solutions to problems which are inherintly recrusive in nature can be solved using liner proofs...'
|
|
|
|
|
|
Using infinite asymptotics...
MyFib(1477) Loops: [1477] Steps: [Approx:25109]
GoodFib(1477) Loops: [1088552] Steps: [6537220]
LinearFib(1477) Loops: [1092980] Steps: [8752702]
Even though Linerfib takes more steps, it out performs GoodFib in a clock test. In engineering we call this the 'Proof from the pudding...'
LinerFib(1477) LoopCount: [1478] - SplitTimeMicro: [44.6984183744023]
MyFib(1477) LoopCount: [1] - SplitTimeMicro: [48.8888950970026]
GoodFib(1477) LoopCount: [1475] - SplitTimeMicro: [507.047683434626]
modified on Wednesday, July 8, 2009 2:35 PM
|
|
|
|
|
Ok, guy. Which part of "the really important thing here is not the problem itself, but the way you can solve it applying those restrictions" is the one you have not understood?
|
|
|
|
|
_Erik_ wrote: Ok, guy. Which part of "the really important thing here is not the problem itself, but the way you can solve it applying those restrictions" is the one you have not understood?
I have all ready admited your point is valid! My problem with the interviewer was that I had expalined the problems with recrusion and how it causes bad things to happen like: heap pile up, stack overflow, huge thread stacks, and object over load due to the problem with not being able box objects for reuse. I also told the interviewer that I only had a basic understanding of the problem and that I knew it would be better solved with out using recursion. I did explain what recursion was and such. My biggest mistake was not asking the interviewer for a diffrent problem using the same constraints for which I completly undestood. We are human Eric, a knowlegable man learns from his own mistakes, a wise man learns from others. I was not trying to bash you in this thread, my honest appoligies if you though as much. My intent was to show how I arrived at my conclusions about the problem algroythm during the interview. Perhaps others reading this thread could gain wisdom from my mistake.
~TheArch
|
|
|
|
|
You don't know why you didn't get the job. It could have been for many reasons. I've been turned down for jobs even AFTER I passed the technical part. A lot of who gets hired has to do with the chemistry of the group you're interviewing with. Qualifications are overrated.
The second phrase is correct.
|
|
|
|
|
Well, I would have been thier Cheif Architect and Lead Developer.
I would have been the companies first hire besides the CTO which I was interviewing with.
He probibly didn't like me breaking the pencile into Four peices.
~TheArch
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
