|
<chuckle>
Hmm, I have written many, many recursive functions. None that break out of recursion however. Well maybe in VB a long time ago, using goto labels. Loop: and Exit:. It was still considered bad form then. My Java mentor from Sun was crazy about recursive logic. For this problem a simple for loop would have been a much eligant solution. I good at identifying eligance and implimenting it, but it is just not logical to do otherwise. Microsoft actually considered removing recursive funcion from C# when they ported it from MS Java. I think they are about as bad as mutiple class inheritance. Powerful, easy to abuse, rairly needed.
|
|
|
|
|
No worry, just checking!
I was wondering why you could not write the recursive function he asked!
I guess now it was a psychological blockage!
Next time, don't stress too much about the purity of the algorithm. Perfectionism is over hyped!
I am not saying we should not be perfectionist, this is an important quality for an engineer.
However perfectionism often become stubbornness, which is obviously not good hey!? 
To stretch it a lot, that remind me of a yahoo science / psychology article about terrorists.
They did some psychology profiling on terrorist and, to everyone surprise, terrorist are more likely to be engineer. They explored many conjecture as to why but the best candidate seems to be that the engineer doesn't think with nuance. Things work or don't. Ideas are good or not. Engineer are often less good at compromise. I found the idea interesting. Noticed myself I do tend to be stubborn sometimes on point of detail!
Hey, don't worry, I am not implying anything about you, just let my mind wander quite a lot and thought aloud!
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Hmm,
Being a x-military anti-terrorism super freak, I understand the subject very well. My daily exersize druing my life in the millitary was to figure out how to take control of the work in 24 hours with a team of Seven. After 9/11 I was terrified at how close my anti-terrisim counter measures were to what is possible. My job, run three miles to jump on an airplane and blow up the world.
|
|
|
|
|
Fun Bio by the way!
Those evil MVP are sneaky bastard! 
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Evil MVP a.k.a DrDotNetSky
|
|
|
|
|
The point about interview questions is not to pose real world problems, but to see if candidates have the knowledge required for the job. Our interview questions can be similarly "odd", and will vary depending on the specialisation being interviewed for. What we're looking for is the ability to solve problems, and apply knowledge.
What you should have done is written the algorithm, then gone on to explain why the recursive version is not as good as the iterative one - that would probably have impressed the interviewers more than someone who just wrote the code with no further explanation.
TheArchitectualizer wrote: Microsoft actually considered removing recursive funcion from C#
I think that's a myth. There are plenty of cases where recursion is in fact the easiest and best way to implement things.
There are three kinds of people in the world - those who can count and those who can't...
|
|
|
|
|
Super Lloyd wrote: As a rule recursion IS NOT bad. In fact it is use very much often!
I am still thinking about recursion. I really don't think it's a good thing.
MSDN: Is there any situation where recursion is useful?[^]
My thought is if you can do it with out recursion, then do.
~My 2¢
|
|
|
|
|
Are you one of those religious warrior?
Maybe I should tell you that I wrote 1 or maybe 2 goto this last year!
I am not interested in religious war!
I am interested, eventually, in well explained idea.
Please do tell me why not recurse!
So I will know when I should not...
In the case of Fiboonacci it's easy, it requires "2^N" operation recursively and "N" in a non recursive fashion. But you statement was much more general, so please provide general argument against recursion.
So that I know, according to you, when to avoid it.
Well, I decided to participate in religious war after all....
And to challenge you, without waiting for your arguments, with some counter examples.
How do you write structure recognizer in a non recursive fashion?
i.e. how do you write thing such as a "Language compiler" or an "Object graph deserializer"?
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Super Lloyd wrote: Are you one of those religious warrior?
No! I am still investigating it. I had a mentor from Sun whom was crazy about it. I used it alot on that job. But after leaving I think I might have only used it twice.
Super Lloyd wrote: How do you write structure recognizer in a non recursive fashion?
i.e. how do you write thing such as a "Language compiler" or an "Object graph deserializer"?
Heck, I couldn't even do the easy example of getting all the widgets in the visual tree for WPF. I will do some research for you and get back to you. But I leave you with this thought.
'How did they do this before the invented recursive functions?'
~TheArch
“Make love, not war”
American Proverb quotes[^]
|
|
|
|
|
Super Lloyd wrote: How do you write structure recognizer in a non recursive fashion?
i.e. how do you write thing such as a "Language compiler" or an "Object graph deserializer"?
Just getting back to you Super Lloyd. I read the Wikipedia on recusion. Seems not all problems can be solved with out recursion. Case: Ackermann function[^]
A funny from the Wiki:
'"In order to understand recursion, one must first understand recursion." Or perhaps more accurate is the following, from Andrew Plotkin: "If you already know what recursion is, just remember the answer. Otherwise, find someone who is standing closer to Douglas Hofstadter than you are; then ask him or her what recursion is."'
Also from the Wiki:
'In computability theory, primitive recursive functions are a class of functions which form an important building block on the way to a full formalization of computability. These functions are also important in proof theory.
Most of the functions normally studied in number theory are primitive recursive. For example: addition, division, factorial, exponential and the nth prime are all primitive recursive. So are many approximations to real-valued functions. (Brainerd and Landweber, 1974) In fact, it is difficult to devise a function that is not primitive recursive, although some are known (see the section on Limitations below). The set of primitive recursive functions is known as PR in complexity theory.'
'I guess when you really get to the salt; everything is recursive.'
|
|
|
|
|
Well, mm..
You haven't told me yet why I should abstain from recursion!
Further, how about more mundane cases....
Why would getting the list of all control in a hierarchy this way be any bad?
pseudo C# below!
IEnumerable<Control> GetUITree(Control c)<br />
{<br />
yield return c;<br />
foreach(Control c in c.Children)<br />
foreach(Control c2 in GetUITree(c))<br />
yield return c2;<br />
}
Another "theorical" question as you might seems to like.
IF I can call a user (developer) defined function in a user defined function.
Any function call is potentially recursive!
After all when I wrote
void f()<br />
{<br />
g();<br />
}
Maybe g() enumerate a list of function pointer one of them being f(), doesn't that means you should stop calling user defined function in user defined function?
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
modified on Sunday, July 19, 2009 4:28 AM
|
|
|
|
|
Super Lloyd wrote:
Why would getting the list of all control in a hierarchy this way be any bad?
In this case, it's bad because for every control in the innermost layer, it has to be passed up N levels on the stack (once for each yield return). This means iterating through the tree will be O(N^2) worst-case.
But this can be easily solved using CPS (continuation passing style):
void IterateUITree(Control c, Action<Control> listener)
{
listener(c);
foreach(Control child in c.Children)
IterateUITree(child, listener);
}
But if you actually need a IEnumerable<T>, you need to give up recursion and manage the stack yourself (this also means manually repeating the foreach-magic):
public static IEnumerable<T> Flatten<T>(this IEnumerable<T> input, Func<T, IEnumerable<T>> recursion)
{
Stack<IEnumerator<T>> stack = new Stack<IEnumerator<T>>();
try {
stack.Push(input.GetEnumerator());
while (stack.Count > 0) {
while (stack.Peek().MoveNext()) {
T element = stack.Peek().Current;
yield return element;
IEnumerable<T> children = recursion(element);
if (children != null) {
stack.Push(children.GetEnumerator());
}
}
stack.Pop().Dispose();
}
} finally {
while (stack.Count > 0) {
stack.Pop().Dispose();
}
}
}
Usage:
Control[] roots = { control };
var flatList = roots.Flatten(c=>c.Children);
|
|
|
|
|
Actually there is much more simple and readable and maintainable than this complicated flatten method, and you should have thought of it. Except it's recursive of course... (meaning that you should get rid of your mind block with recursivity!)
void IEnumerable<Control>IterateUITree(Control c)<br />
{<br />
var result = new List<Control>();<br />
result.Add(c);<br />
foreach(Control child in c.Children)<br />
IterateUITree(child, result);<br />
return result;<br />
}<br />
void IterateUITree(Control c, List<Control> result)<br />
{<br />
result.Add(c);<br />
foreach(Control child in c.Children)<br />
IterateUITree(child, result);<br />
}<br />
I used that occasionally.
It avoid the "performance" problem (of both my example code and your complicated flatten code) and is much easier to read / understand / maintain.
And even better performant than your flatten method, although not by much (but anyway its main advantage is readability, so I would use it even if it were less performant).
Anyway, I was just talking about recursion in general and this double foreach was my 1st idea.
Now you replace a very simple (and presumablye costly) nested foreach with a way more complicated (hence bug prone) code.
it's not obvious it's going to be more performant or efficient.
It will probably depends on the shape of the data.
Also it is potentially buggy (another sign that complicated code is not a good idea, even if you *think* it's more performant)(you should do performance test to check that).
Anyway, if I'm not mistaken, the GetEnumerator() method sometime return IDisposable object (it's how the Finally block of enumerator are executed I believe, as well as removing some event listeneners), so you should check that the IENumerator in your code are IDisposable or not and dispose of them...
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Yes, often passing a list around and adding to it works fine.
But it's not exactly equivalent to your nested "yield return". In my case, I really needed a enumerator that was being lazily evaluated.
And yes, you need to dispose enumerators. My Flatten method does that.
Of course I realize that recursion is a lot cleaner than manually messing with a stack. That was the point of my two code snippets.
But unfortunately, due do the language's implementation of "yield return", it's unavoidable in this specific case. To efficiently support recursion in iterators, the language would need something like a "yield foreach" statement - see http://blogs.msdn.com/wesdyer/archive/2007/03/23/all-about-iterators.aspx[^] ("The Cost of Iterators").
|
|
|
|
|
cool link hey!
And, mm.. while I wouldn't like to write the Flatten method on a daily basis (unlike the iterators) it has some merit as a library utility! 
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
I just paid more attention to your flatten method as, convinced by your argument and the re-usability of this method (as opposed to its re-implementability!), I decided to put in my utility library.
It's indeed cool and well implemented, and it does dispose all the enumerators, my mistake!
A train station is where the train stops. A bus station is where the bus stops. On my desk, I have a work station....
_________________________________________________________
My programs never have bugs, they just develop random features.
|
|
|
|
|
Nifty!
Would you mind if I added this coolness to the experimental test lib in my Big O Algroythm analyzer?
If so let me know if you want your name in lights or not.
I am adding the much needed Computer Science heurstics to the code base, so I would like to add a test for this as well.
~TheArch
|
|
|
|
|
But RFibonnaci, the recursive version, has to perform approximately 2^(index-1) method call.
If you do it right, the number of method calls will precisely equal the result. In any case, a naive approach is going to take O(phi^n) calls to complete (since the ratio of adjacent Fibonacci numbers approaches phi, i.e. (1+sqrt(5))/2 aka the Golden Mean).
An alternate recursive approach is to write a method which returns two adjacent Fibonacci numbers (either as a structure, or using pass-by-reference). Starting with having an input with n<=1 yielding (0,1), and otherwise having the code for n read the values for (n-1) into (x,y) and return (y,x+y), the recursion runs nicely in linear time.
|
|
|
|
|
Hmm, it is a small world. While researching ML on another thread I found three F# implimentations:
<br />
(* Fibonacci Number formula *)<br />
let rec fib n =<br />
match n with<br />
| 0 | 1 -> n<br />
| _ -> fib (n - 1) + fib (n - 2)<br />
<br />
(* An alternative approach - a lazy recursive sequence of Fibonacci numbers *)<br />
let rec fibs = seq {<br />
yield! [1; 1];<br />
for (x, y) in Seq.zip fibs (Seq.skip 1 fibs) -> x + y }<br />
<br />
(* Print even fibs *)<br />
[1 .. 10]<br />
|> List.map fib<br />
|> List.filter (fun n -> (n mod 2) = 0)<br />
|> printlist<br />
<br />
(* Same thing, using Comprehension syntax *)<br />
[ for i in 1..10 do<br />
let r = fib i<br />
if r % 2 = 0 then yield r ] br />
|> printlist<br />
It's also recursive...
|
|
|
|
|
If you want a terrifying interview question try this beast on for size
From the command line take in two numeric strings, determine how you would have to create an equation out of the numbers given in the first string to result in the second or display that it is impossible.
Sample input: 12 3
1+2 = 3
34 12
3*4 = 12
Only, there was one of these samples roughly 20 characters long. You either had the four typical operators or perhaps just addition and multiplication to cover.
Do this in C, with no libraries, in under 6 hours, time also split doing a sodoku solver(which is a pain for those of us who'd never done one of the puzzles before, did it in two hours including learning the game).
That said, if this is some how as easy as a Fibonacci sequence I would love to be proven an idiot, this thing has been bugging me for a while now. And I may have finally figured the thing out writing this, I'll have to see if my idea works once I'm out of work.
|
|
|
|
|
I have no idea, in a simular post I offered the use of lambda functions and red black trees to solve the problem.
'I am a mathimatician suffering from Pseudo-Intellectual Academia.'
modified on Monday, July 6, 2009 1:41 PM
|
|
|
|
|
For me it would depend on the circumstances.
This is an easy bit of code just a few lines long.
Sitting here under no pressure I had it working in a couple of minutes. I would be happy to tackle it using pencil and paper.
In a interview, if they said go sit in the corner for 10 minutes and see what you can come up with, I'd likely be OK. But if the interviewer sat close and watched every move of the pencil then I might go blank if I was not previously at ease. Then it becomes as much about self-confidence and ability to think under pressure as it does about coding.
|
|
|
|
|
i agree with you. Some time interviewer make matter worst. I also cant code when some one watching me. Its really confuse me. 
|
|
|
|
|
I wonder,
if recursion = spogitta then how do you enumerate directories?
It feels good to learn and achieve
|
|
|
|
|
I would use LINQ to Objects:
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Linq
{
class Program
{
static void Main(string[] args)
{
ListFiles(new DirectoryInfo("c:\\"));
}
static void ListFiles(DirectoryInfo dir)
{
var Directories = from dirs in dir.GetDirectories()
orderby dirs.FullName
select dirs;
foreach(DirectoryInfo directory in Directories)
{
Console.WriteLine("Directory: <" + directory.FullName + "> contains the following files:");
var Files = from file in directory.GetFiles()
orderby file.FullName
select file;
foreach (FileInfo file in Files)
{
Console.WriteLine("---" + file.FullName);
}
}
}
}
}
If the system had multi core I would use PLINQ to Objects...
modified on Saturday, July 18, 2009 11:12 AM
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
