|
Hmm,
Sorry, it's an identity inthe proof of the ∞ for this sequence. It is based on Eulclidian Geometry and Hilbert's Tenth Problem. I could not find the article on it, something to the effect of:
xn+1n + xn-1n = √xnn
Seems the article was deleted. 
|
|
|
|
|
Computafreak wrote: The Fibonacci sequence doesn't have that formula.
Well it has, but it's not a point of your post I suppose. I had a task on a math exam to derive a closed form expression of a given sequence defined by a linear recursion. It's quite easy when you know something about generating functions. That task killed me, though. 
Greetings - Jacek
|
|
|
|
|
However there is nothing wrong with a little bit of algo interview I believe.
Heck you could have impressed them by doing a non recursive version!
from the top of my mind here is a decomposition of an input number in a sum of fibonnaci number (which is unique)(pseudo code,i.e. might not compile, run and/or be full of error, use at your own risks!)
public struct FibonacciNumber<br />
{<br />
public FibonacciNumber(int i, int v) { Index = i; Value = v; }<br />
public int Value;<br />
public int Index;<br />
}<br />
class Foo<br />
{<br />
static List<FibonacciNumber> Decompose(int number)<br />
{<br />
var allf = AllFibonacciTo(number);<br />
var result = new List<FibonacciNumber>();<br />
for (int i = allf.Count; i-- > 0; )<br />
{<br />
var f = allf[i];<br />
if (f.Value <= number)<br />
{<br />
result.Add(f);<br />
number -= f.Value;<br />
}<br />
if (number == 0)<br />
break;<br />
}<br />
result.Reverse();<br />
return result;<br />
}<br />
<br />
static List<FibonacciNumber> AllFibonacciTo(int number)<br />
{<br />
var result = new List<FibonacciNumber>();<br />
result.Add(new FibonacciNumber(0, 1));<br />
result.Add(new FibonacciNumber(1, 2));<br />
int last = 2;<br />
while (last < number)<br />
{<br />
var fn = new FibonacciNumber();<br />
int N = result.Count;<br />
fn.Index = N;<br />
fn.Value = result[N - 1].Value + result[N - 2].Value;<br />
last = fn.Value;<br />
result.Add(fn);<br />
}<br />
return result;<br />
}<br />
<br />
static void Main()<br />
{<br />
int N = 78;<br />
Dump(AllFibonacciTo(N));<br />
Dump(Decompose(N));<br />
}<br />
<br />
static void Dump(List<FibonacciNumber> lf)<br />
{<br />
foreach (var item in lf)<br />
Console.Write("({0}, {1}) ", item.Index, item.Value);<br />
Console.WriteLine();<br />
}<br />
}
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 Monday, July 6, 2009 7:10 AM
|
|
|
|
|
Maybe more in line with what they asked....
static int RFibonacci(int index)<br />
{<br />
if (index < 1) return 1;<br />
if (index < 2) return 2;<br />
return RFibonacci(index - 1) + RFibonacci(index - 2);<br />
}<br />
static int DFibonacci(int index)<br />
{<br />
if (index < 1) return 1;<br />
if (index < 2) return 2;<br />
int u = 1;<br />
int v = 2;<br />
int N = 1;<br />
while (N < index)<br />
{<br />
int tmp = u + v;<br />
u = v;<br />
v = tmp;<br />
N++;<br />
}<br />
return v;<br />
}
But RFibonnaci, the recursive version, has to perform approximately 2^(index-1) method call.
End result, the recursive method is so ungodly slow compare to DFibonnacci that it is tearful...
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,
Nice! I told them it was a bad idea and offered to do it no recursive. What made matters worse was the algroythm was supose to break out after finding sequence 'x'.
He told me that he thought I was the man for the job untill I couldn't complete this simple recursive routeen.
|
|
|
|
|
well, that's the thing!
if you can't write a simple recursive it's suspicious!
I hope you can, can you?
I hope your mind block was just psychological (this will perform so badly, I should not!)
I hope it's not something again recursion in general, is it?!?
The fact that recursion *might be* problematic and *might be* improved with a non recursive fashion is a completely different issue.
As a rule recursion IS NOT bad. In fact it is use very much often!
he asked you that to checked if you know and understand recursion, to check if you are really a programmer and not a bluffer.
Now if you can't write it because *insert reason here* you are a bluffer.
Next time do it.
It doesn't matter if it's a bad idea, this is not the purpose of the exercise!
However, adding some explanation on why it is bad in this case and how to improve it! Here you just gain free bonus point!
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.
|
|
|
|
|
<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...
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
