@Michael Depending on the teacher taking the CS101. I am
pretty much sure every one in my batch would have written a recursive function over an iterative
solution
@Saurabh, Michael Recursive function for Fibonacci will be very inefficient. Its running time will grow exponentially
with X. :) Watch this video : http://www.youtube.com/watch?v=GM9sA5PtznY
I hope someone noticed the point of this post and which in
my view is that the more you know things, the more constrained your view becomes, instead of thinking
in a straightforward manner, we think of all the ways something could go wrong and more often than
not, it holds us back from doing anything.
This is sooo true and really funny.. i have been there and
done that for all the different roles [Excpet the cat ofcourse ;)] .... code written at a large
comany is the best.. ROFL!
The Math PhD's closed-form answer is less efficient than
the basic iterative/recursive solution. It requres 2n (or for the rounding version, n) multiplications
to do the exponentiation, while the brute-force solution requires n additions, which on most processors
are faster than multiplications.
so no one gives a sh!t about the computational complexity.
All the recursive implementations have exponential complexity. And I seriously have no clue what
the author tried to prove with the totally gibberish large company or math PhD code.
How about the following: int fibonacci(int x){ if (x <= 2) return 1; else { int sum = 1, oldsum = 1, tmpsum; for (int a = 3; a <= x; a++) { tmpsum = sum; sum = sum + oldsum; oldsum = tmpsum; } return sum; } }
When I took my bachelor degree, I used "cat" species code
for my homework. The code worked, but guess what? Got 0 because my teacher didn't understand any
sh*t I wrote :))
Here we go, complete imagination of author went to a toss.
And post has become dead ground for recursive algo complexity discussion. Screw you coding wannabes.
And code written by a student, that paid attention during
algoritms, knows how to google and did remember to trust only reliable sources of information...
Just to be pedantic for my CS/math bros: The CS101 code doesn't need recursion or memoization, and that would occur to most students, since
that's how people do it by hand: they take the last two numbers, add them together, and get a new
number. Then they can forget the oldest number. A simple for loop takes care of that. Admittedly,
this is explicit memoization.
But worse, the code by a "math phd" isn't any faster than that, and is inexact if there is rounding
error, unless it uses an overcomplicated math framework that handles sqrts symbolically.
Still, if you change the (math phd?) exponentiation function to do successive squaring, you get
the best running time so far, O(log n). A CS101 student could even work out how to do it without
a heavyweight math library, since all of the intermediate computations are on numbers of the form
(a+b*sqrt(5))/2^n where a,b, and n are integers. So you only need integer arithmetic.
There other O(log n) algorithms, such as ones exploiting the recurrences
F_(2n-1) = (F_n)^2 + (F_(n-2))^2 and F_(2n) = (2F_(n-1) + F_n)F_n
My most beloved school of coding is so called 'Weimar school'.
It used by Germans for writing embedded code, mainly safety critical code. It goes something like
this:
#define ONE 0U #define TWO 1U #define E_OK 0U #define THRE 16U #define HUNDRED 100U uint8_t UDS_tx_buff_au8[HUNDRED + ONE]
arguing that: (a) tail recursion would take care of recursion costs, and (b) why bother with control
flow if we only need the values.
Reminds me of Perlis' quip: C programmers know the cost of everything and value of nothing, while
Lisp programmers know the value of everything but the cost of nothing. :-)
Code written by CS 101 student has too much indentation and
looks too clean. In reality, the code would be flush against the left margin, no indents, no whitespace
between operators/operands, and would probably have redundant comments on every other line (to please
the prof), e.g. "//This is for the case x = 1 //This is for the case x == 2"
Funny because I am a CS 101 student and I did in fact write
a recursive function without the help of outside resources for one of the functions needed in a
project.
Code written by a type theorist. (It calculates Fibonacci
numbers in the Haskell type system.)
{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies, FlexibleInstances, UndecidableInstances
#-} data Zero data Succ n class Add a b c | a b -> c instance Add Zero b b instance Add a b c => Add (Succ a) b (Succ c) class Fibb a b | a -> b instance Fibb Zero Zero instance Fibb (Succ Zero) (Succ Zero) instance (Fibb a r1, Fibb (Succ a) r2, Add r1 r2 b) => Fibb (Succ (Succ a)) b
To calculate, you need to create placeholder values with appropriate types, and ask the interpreter
what type the combination of the two would have.
*Main> let fibb = undefined :: (Fibb a b) => a -> b *Main> let six = undefined :: Succ (Succ (Succ (Succ (Succ (Succ Zero))))) *Main> :t fibb six fibb six :: Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))
The real Math Ph.D. wouldn't use `one()` or `add(one(), one(),
one(), one(), one())` when there is already a `zero()` defined. Rather he would write it using induction,
like `succ(zero())`, or `succ(succ(succ(succ(succ(zero())))))`. Hope that helps ;)
