Tricky staff
Write a program which prints numbers 1..million without using cycles.
If you feel you know how to do this easly with recusive call - try to write one.
- tigor's blog
- Login or register to post comments
Write a program which prints numbers 1..million without using cycles.
If you feel you know how to do this easly with recusive call - try to write one.
Comments
my approach: use threads. the nth thread prints the number n and creates a new thread with n+1.
why use threads when you can use recursion? :)
because recursing 1000000 times will overflow your stack. java doesn't do tail recursion optimization (yet. there's an implementation for jdk7 i think)
In addition to the ugly solution that I sent you by email, I want to tell that task definition is incorrect. If you write such program in java, it's executed by java VM using cycles, so who are we going to cheat? Cycles are performed using JUMP assembly instruction. So if I rephrase the task as "write this program in assembler so CPU executes instructions sequentially and does not perform any jumps" - this task is impossible to do without copy-pasting same code million times.
So your problem is really using tricks of high level language to hide cycles, not to eliminate them.
what mail? can you post as comment?
and yes, cycles are used, but not in code, which is how I interpreted it in the beginning...
was the question intentionally phrased in a vague way to hide this trickery? yarr!
Another approach: find out what the maximum stack trace is. Say it is 1000. Generate a function that given n prints n, n+1,...,n+999 and then calls itself recursively with n+1000
Ok, here is the solution for zero to 99, for million must be 6 functions. But this is a cheat as I explained
def print0(): print1("0") print1("1") print1("2") print1("3") print1("4") print1("5") print1("6") print1("7") print1("8") print1("9") def print1(digit1): print2(digit1, "0") print2(digit1, "1") print2(digit1, "2") print2(digit1, "3") print2(digit1, "4") print2(digit1, "5") print2(digit1, "6") print2(digit1, "7") print2(digit1, "8") print2(digit1, "9") def print2(digit1, digit2): print digit1+digit2 print0()niiiiiice,
(cheeky bastard :)
to make this more generic, for very large ns, define one function 'print' that accepts a list of digits. the function calls itself recursively adding one digit to the list each time log(n) times (so there's also a stop variable that starts with log(n) and decrements with each recursive call)
this is still not infinitely scalable. for large enough N, even log(n) will cause a stack overflow (i'm being very theoretical here of course)
I did not understand how your generic solution is going to print the line? I mean, if you don't know how many arguments you have how are you going to make?
print number1+number2+number3 - is possible because we know there are 3 numbers
print [number1, number2, number3] - how do you print an array?
Again, you are fighting against the syntax. For example do array comprehensions considered loops? What if some language has a feature for printing all the array in the form we need, is it allowed suddenly? The exercise definition is fundamentally broken, as I said earlier.
i print an array with recursion. since the array size is lon(n), i won't run into stack overflow for "normally large" n. e.g., for 10^100, the recursion will be 100 frames deep
If Arrays.fill() is allowed you can do something like this (pseudo-java-code):
class AutoInc { int i=0; public String toString() { return new String(++i); } } Object[] arr = new Object[1000000]; Arrays.fill(arr, new AutoInc()); System.out.println(arr);regarding the obvious recursion solution, the depth of the recursion can be log(n) and not n so it can work as well (javascript-pseudo-code):
function foo(bar) { if (bar.length()==6) print bar+1; else { foo(bar+"0"); foo(bar+"1"); foo(bar+"2"); foo(bar+"3"); foo(bar+"4"); foo(bar+"5"); foo(bar+"6"); foo(bar+"7"); foo(bar+"8"); foo(bar+"9"); } } foo("");