The Weird and The Wonderful

Computafreak wrote:

The Fibonacci sequence doesn't have that formula.

	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 />
	}

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 />
}

TheArchitectualizer wrote:

Microsoft actually considered removing recursive funcion from C#

Super Lloyd wrote:

As a rule recursion IS NOT bad. In fact it is use very much often!

Super Lloyd wrote:

Are you one of those religious warrior?

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"?

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"?

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 />
}

void f()<br />
{<br />
 g();<br />
}

Super Lloyd wrote:

Why would getting the list of all control in a hierarchy this way be any bad?

void IterateUITree(Control c, Action<Control> listener)
{
  listener(c);
  foreach(Control child in c.Children)
    IterateUITree(child, listener);
}

/// <summary>
/// Converts a recursive data structure into a flat list.
/// </summary>
/// <param name="input">The root elements of the recursive data structure.</param>
/// <param name="recursive">The function that gets the children of an element.</param>
/// <returns>Iterator that enumerates the tree structure in preorder.</returns>
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();
		}
	}
}

Control[] roots = { control };
var flatList = roots.Flatten(c=>c.Children);

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 />