Cheat Engine

[hcavolsdsadgadsg]

If I can't use inline asm can I write all the opcodes manually

or what if I only use intrinsics.

[Deltron Z]

[Polynomial]

Plain C++ only please, slugsnack.

[Slugsnack]

You should not dismiss recursion as inherently bad because it is not. There are cases when recursive code is a lot easier to write or a lot easier to read. Sometimes readability means more than efficiency. Increasing the efficiency by 10% on a non-speed critical part of a program but compromising the ease of development and productivity of all developers to look at your code in future is not a good tradeoff for example. For example, take a binary search tree. The code to traverse it and add an element recursively is trivial but it gets more complicated and would take you longer to solve as an iterative problem.

Yes, recursive functions do TEND TO BE less efficient because you have the CALL overhead as well as a stack which increases more and more. It is silly to say that non-sanitized input will cause it to randomly crash because that is simply not true. It is true in the same way that is true of any program. If the programmer does not handle these inputs, yes it would crash. A lot of the time input bound checking is checked as a wrapper to a recursive function. It is not sensible to do it within it because it means the input is checked on each iteration. It tends to be faster to do things all in 1 go. Stack overflow can be avoided pre-emptively by knowing what bounds your input is going to take and setting an appropriate stack size in your linker options.

Anything that can be done recursively can be done iteratively by replacing the function call with a 'while' loop and making basecase conditions 'break'. Also one of you two mentioned STL earlier in a context which was completely irrelevant to the points you were arguing. The STL stack is unrelated to the program stack other than that it might use it. But its implementation details are abstracted from the user of it anyway. STL stack is simply a container/abstract data type.

[Uzeil]

It isn't true that you can just change a recursion to a while and throw some breaks in there. In many of the cases where recursion is a good idea, it would be necessary to set up dynamic-length arrays left and right in a non-recursive formula, and wind up taking much more processing time(and sometimes more memory anyway) than a recursive algorithm would've.

Especially for someone who is trying to challenge others to create the 'most optimized' (debatable, considering the difference between readability, binary size, processing time, and the difference in processing time from different amount of data.), this should be understood.

Don't be stubborn just because you originally spoke out against it =S You're being told plenty of good advice, learn from it.

[Deltron Z]

Burningmace, what you said is just stupid!
"Rape your stack"?! and what do you think recursion does after it returns? it empties the stack. not only that, better than having an array and a loop - it's more like having a list and a loop - once the memory is no longer needed it is removed from the stack, and this way we can calculate bilions of different combinations (where a combination could take, let's say, 1KB) of, let's say, returning change with different coins. you don't have enough memory to do so with just an array becuase you don't have enough memory.
I'd like to see you beat 3-lines recursion with a loop and an array. can you make it more efficient? efficient would be short in code (a few lines, compared to 3-lines recursion), in memory (can you make an iterative code that uses the same amount of memory to your disposle to do the same thing a recursion does? using a list as I mentioned would basically turn it to something like recursion because you will basically do the exact same process as recursion... so - no lists too, because anything like recursion sucks!!! right?) and in speed. (run under a second)

I didn't even read Slugsnack's and Uzeil's comments yet, because you are too ignorant to admit you were wrong one time and learn a lot from other people's experience.
So, as I said before - just know this: every technology you use and love so much (Computers, TV, Cellphones, Calculators...) uses recursion half of the time.
I think you're just ashamed that you can't understand recursion so you're trying to prove it "sucks"... for your information: there is no place in the world that would even think of hiring someone that can't use recursion (or think it sucks), I bet most of these places would laugh in your face hard... I hope you've got other hobbies.

Edit: I forgot to mention, not only that it's not a problem to tell people to simply change the stack size manually - it can be done by code. (See #pragma directives...)

[Slugsnack]

Deltron Z : I think you may be a little confused here. What he means by rape the stack is that during the execution of the recursion the stack grows by many many factors due to it being extended for parameters + return addresses on every single call. That does not even take into account any local variables each call uses either. Also the stack is actually memory..

[Deltron Z]

You misunderstood me - I know that - what I meant is that everytime you return they are also being removed from the stack. so, you can't say it just gets filled because it also takes care of emptying at the same rate it fills it, there's no way the stack would be filled in 1KB and release only 512 bytes... it's just that removing these bytes from the stack might occur in different times, like 10 calls, 1 return, 20 calls and 29 returns. no problem with that.

[Uzeil]

The last sentence of slugsnack's being the important part, Deltron. While recursion can, in the right circumstances, get more speed, more readability, and even use less memory: a limitation it has(that you spoke the opposite of) is that it's bound by the memory your linker and operating system grant to running applications. Non-recursive loops have the added benefit that, if absolutely necessary, they can sacrifice speed(hugely) and use file io to expand their data size cap by the hundreds.


(Not that I want to, in any way, make it seem like the 'no recursion!' side is reasonable. At all.)

[Slugsnack]

A little extra info for interest. The stack is simply a block of memory that is defined by the program for specific use, ie. as the stack. Its main use is parameter passing and local variables. Now the interesting bit. The stack is actually extendable and can grow. If on a heavily recursive app, the stack commit size is exceeded, the next probe triggers a guard-page exception which causes the stack to extend and the guard page to increment to the next page.

[Deltron Z]

Ofcourse not every function should be recursive - it should be when it is needed!
Other than that, trust me, the operating system have more than enough spare memory for our disposle so we can create massive recursions with no problems at all.

You might want to take a look, for example, at [url=http://projecteuler.net/index.php?section=problems&id=15]Problem 15[/b] at Project Euler. notice there are (40!)/(20!20!) = 137,846,528,820 possiblities! personally, I solved this one in recursion. (it can be as easily and perhaps even more easily solved with loops, but that's not the point) and it didn't even tickle my computer's RAM nor CPU... Assuming we pass 4 bytes for the return address and 8 more bytes parameters, a total of 12 bytes. 137 billion * 12 = 1.644 trillion! that's 1.644 TeraBytes, 1644 Giga Bytes, 1644000 Mega Bytes!
You must understand it releases the memory too! obviously you can't allocate nearly 2 Tera Bytes on today's computers...

Edit: a quick look at the stickies...

[Slugsnack]

You realise just because it has that many permutations/combinations it does not mean you went through all of them. You just kept going till it stopped. Also it's likely your algo worked such that it never held that much all at once. Given each program only has a userspace region from 0x00000000 to 0x7fffffff and a specific sections of that are not usable as heap/stack memory ( eg. space needed for pe headers, minimum application address not starting from 0x00000000, etc. ) it is not possible you used 1644GB without writing to disk. 'Trust me', virtual memory is an abstraction such that each program thinks they have more memory.. but not that much.

http://en.wikipedia.org/wiki/Virtual_memory

That page - read.

[Uzeil]

Right, neither of us are saying that a recursion can't, by the time it's done, handle massive loads of memory. What the limitation here is that it can't hold as much at one time as non-recursive methods can, simply because of the additional options given to them using hard disk space. The reason I mentioned 'operating system' is just that some operating systems allow RAM to leak loads into the hard disk space(some more than others, some let you choose how much, etc).

And if you were replying to me on the "Ofcourse not every function should be recursive - it should be when it is needed!" -- I just put that bit in what I said for correctness.

[Deltron Z]

Ofcourse I did not use 1644GB - not at all... again you are misunderstanding me, I guess my English is too poor or I'm just explaining too bad.
What I was saying is that the total memory needed to calculate all the combinations is about 1 Tera Byte, alright? now, once one combination was found, since the function was recursive, it returned and thus released 8 bytes. next, it tried the other direction and there I've got another path, and still having a path of size 40 steps, assuming each step takes 8 bytes to reresent than it took 320 bytes at most at all times. you understand? once it reached the end, it only used 320 bytes to represent a combination, however it released the memory, then the memory released is free for another combination representation to use.
So, after getting a certain path with last step being both right and down, I can now return twice (and free 16 bytes) to generate the next path, down and then right and down again. once I'm done, I return once again (24 bytes) and then instead of last combinations begin right, x, x it would be down, x, x, so I have calculated path where the last steps are right, right, right and also right, right, down and right, down, right and right, down, down. now I have to calculate down, right, right, then down, right, down and so on... I don't have to explain.
So I just showed how I used 320 bytes to find all paths which is in total 1 tera byte in size.

I hope this clarifies everything!
I'm tired of explaining myself over and over... I get misunderstood a lot lately. maybe I just use bad examples...

[Polynomial]