Carbon dioxide posted:

If that does cause problems, well every recursive function can be rewritten to not have recursion at all.

Beef posted:

I think you're confusing things here. Only tail-recursive functions can be rewritten to not have recursion. Try writing a BFS/DFS without using a queue or stack.

Soricidus posted:

The distinction is important because actual computers often impose limits on the depth of function calls even if there's plenty of memory available on the heap.

Beef posted:

Wait, you actually believe that because you use the heap instead of the built-in stack, you magically make something not recursive?

The whole point of something being not recursive is not taking extra space, regardless of how many iterations you are taking.


Your computer is not aware of any stacks, heaps or function calls, this is a convention used by compiler/runtimes. Also, there is just as much stack available as there is heap, they grow towards eachother: stack grows down, heap grows up.

edit: I get your point that language runtimes limit stack depth, yes. Rewriting a function to use a manual stack instead of language runtime stack does not change that you are writing a recursive function.

Beef posted:

Wait, you actually believe that because you use the heap instead of the built-in stack, you magically make something not recursive?

The whole point of something being not recursive is not taking extra space, regardless of how many iterations you are taking.


Your computer is not aware of any stacks, heaps or function calls, this is a convention used by compiler/runtimes. Also, there is just as much stack available as there is heap, they grow towards eachother: stack grows down, heap grows up.

edit: I get your point that language runtimes limit stack depth, yes. Rewriting a function to use a manual stack instead of language runtime stack does not change that you are writing a recursive function.

Beef posted:

Wait, you actually believe that because you use the heap instead of the built-in stack, you magically make something not recursive?

Beef posted:

Your computer is not aware of any stacks, heaps or function calls, this is a convention used by compiler/runtimes.

Carbon dioxide posted:

Of course, there are fine solutions for each of your examples in modern languages. In the first, replace goto feh either with whatever it needs to do right there or with a function call. Then put a break statement after it.
In the second, well if you don't have tail calls you can do a regular recursive call on the function - the optimization loss in minimal in most cases on modern systems. If that does cause problems, well every recursive function can be rewritten to not have recursion at all.

You have not convinced me that goto has any uses outside languages such as C and assembly that require/allow you to do low level memory manipulation yourself.

sunaurus posted:

So let me get this straight. You're saying that if I iterate over a stack in any algorithm, that means I'm using recursion?

Soricidus posted:

Yes, I actually believe that. That's because a recursive function is one that calls itself. That's what the word means. If your code does not involve functions that call themselves, it is not recursive. Nothing to do with memory usage.

SICP posted:

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

Soricidus posted:

if it was about non-constant memory then tail recursion wouldn't be recursion!

Soricidus posted:

But you also might like to read a processor manual some time. The CPU knows more about stacks and function calls than you think.

Carbon dioxide posted:

Of course, there are fine solutions for each of your examples in modern languages. In the first, replace goto feh either with whatever it needs to do right there or with a function call.

Carbon dioxide posted:

You have not convinced me that goto has any uses outside languages such as C and assembly that require/allow you to do low level memory manipulation yourself.

Beef posted:

The whole distinction between iteration and recursion is because of resource usage.

eth0.n posted:

The term "recursion" itself says nothing about "resource usage". It means self-referential definition.

wikipedia posted:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).[1]

[1]Graham, Ronald; Donald Knuth; Oren Patashnik (1990). Concrete Mathematics. Chapter 1: Recurrent Problems.

Beef posted:

You are conflating the english definition with the computer science terminology.

Beef posted:

Yeah, programming has nothing to do with computer science, nice.

Jabor posted:

Slightly hyperbolic, but essentially correct.

Computer science is an academic discipline. Programming is a trade skill.

xtal posted:

Good lord that's the last time I mention goto

nielsm posted:

You can just as well talk about recursive data structures, a canonical example being a singly-linked tree. If you want to operate on the tree structure your algorithm will by necessity require O(depth) working storage, regardless of whether you implement it by recursive function definition or a non-recursive manual stack.

Of course if you make the tree doubly-linked (nodes also point to their parent, not just their children) you can do away with recursion/stack-keeping, but that's just trading additional static storage away for saving some dynamic storage.

omeg posted:

I only write low level stuff in C nowadays. I've seen

code:

do {
   ...
   if (error) break;
} while (0); 

used for error handling. Thoughts?

TooMuchAbstraction posted:

Doesn't work for nested loops; goto is superior.

Beef posted:

Incidentally, the code at the bottom of that thread looks very similar as Apple's goto fail.

Beef posted:

quote:

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration).

Dylan16807 posted:

hobbesmaster posted:

It's as if an algorithm could be expressed either way!

Beef posted:

Yeah, I do, frequently. I work at the micro-architecture level. The push/pop in x86 used to be a bigger deal in the 80's, which is why most people still think that. Granted, there is still some extra call-stack hardware in some microarchitectures, but it will not give you a big performance boost compared to doing the loads/stores yourself. I was wrong to say that the processor knows nothing about the call stack, yes, but I say that because in practice there is very little left compared to what people think. There is the address-return push/pop, the optimization guide will tell you to avoid the other stack-related instructions (e.g. enter/leave, task switching).

hobbesmaster posted:

When you're implementing a flow control feature not in your language. For example, try/throw in C.

quote:

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose looping constructs "looping constructs" such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.31

JawnV6 posted:

Nah, setjmp/longjmp do this better.

JawnV6 posted:

or when the zero-length call optimization was put in?

Good Dumplings posted:

what is the "developer's definition" of the color red because holy poo poo I'm glad I don't have to work with you "my way or the highway" guys

dougdrums posted:

I have no idea what the answer to this is but I gotta wonder what's making all of these zero length calls? Like you're referring to the thing where you fetch rip right?

JawnV6 posted:

It's the only way on x86 to retrieve the current PC architecturally.

code:

  call L0
L0:
  pop [e|r]ax

Now, if you've got a polite interest in making call/ret performant, you store the return address for each call in the predictor somewhere. That call won't ever have a matching ret. But if you naively store that return address and predict it for the next ret, you'll get off by one and screw up every prediction after that.

Honestly this is the sort of thing I'd be surprised that software folk had any awareness of whatsoever, but anyone working at the "micro-architectural level" would surely have some hint of it.

JawnV6 posted:

What, pray tell, is work at the "micro-architecture level"? Like do you know when the CRSB was augmented with a RRSB or when the zero-length call optimization was put in? Or are you just referring to "i read a MSR and checked the value" as being some hot poo poo?

quote:

In the second, well if you don't have tail calls you can do a regular recursive call on the function - the optimization loss in minimal in most cases on modern systems.