June 7th, 2015, 11:18 am
Yes, this is mildly common interview question, usually asked in the context of:Write a function to calculate N! recursively.Then they ask:Do it for FibThe hole many candidates fall in is the one zumsl the original poster seems to have found (but possibly not fallen into).like any good interview question and like any recurive exploration of a domain, it can go deep in several directions.The correct answer is of course an O(N) recursion, which is a good trick, but zumsel is looking at tech limits...It is always worth remembering (and in an interivew saying out loud) that recursion is an illusion, that computers simply can't do itand emulate "recursion" by a form of iteration where much of the book keeping effort like managing multiple instances of a a stack variable with the same name are done for you. It follows that anything that can be done recursively may be done iteratively since it is being done iteratively. The difference is notational convenience, which is an important thing in expressing yourself to a computer, but ultimately is just syntactic sugar.May people believe stack size is a function of the memory of the computer it is running on, which is very rarely the case.C++ compilers allow you to set a max stack size for various reasons, one of which is that if you allow a function to recurse forever, it will use up all virtual memory and the system will either go so slowly it looks like it has crashed or simply crash.Other languages either follow the C/C++ convention or set it in a way you can't change or of course just let hte system consume itself.In C++, the exact semantics of f(n-1) + f (n-2) are tightly defined, which means that some of the obvious optimisaitons may not happen, functional languages may not be, so the calculation will not necessarily take the number of steps or depth of recursion you might think.