Wtf how does this recursion work?

>what is a stack

Recursion is really easy once you understand how to use it.

Your code handles two cases, a problem that's really easy to solve and breaking up a problem into parts until it becomes easy to solve

if you think maintaining your own stack is more efficient than using recursion, you are retarded

I literally have never used recursion in my professional life
What are some real life applications of it?

I'm quite sure it takes fewer CPU cycles to do most if not all things iteratively.
Feel free to prove me wrong though.

you can use it to solve some maths related problems such as sorting, but for the most part if you don't know why you need recursion you don't need recursion

As a quick example imagine a binary tree where the nodes consist of one data part and two child pointers.
If you now want to print the data in this tree to the standard output, you have to traverse the tree. Let's go with in-order traversal (left child, data, right child):
doing this recursively can be done in a few lines without much thought, since the formal definition of this traversal method is recursive already.
void printTreeInOrder(Treenode node){
if(node.left != null) printTreeInOrder(node.left); //print left child if it exists
system.out.println(node.data); //print self
if(node.right != null) printTreeInOrder(node.right); //print right child if it exists
return;
}

Now this can of course be done with some clever loops as well, and in some languages, like java, you should use a loop to prevent stack overflows on large trees.
The iterative approach requires at least some brain grease, though, and it will not be as readable as this one.

Is there any problem that can be solved with only recursion? I don't remember anything that can't be beat by writing loops

Recursion is functional programming wank. It has absolutely no place outside the academic sector.

any recursive function can be rewritten as an iterative function

recursion is literally usless, its only uses are to make code hard to read and to destroy your stack

Turing machine has neither.

>its only uses are to make code hard to read
now that depends entirely on the situation.
if your data structure is recursive too, then accessing it by recursion is more readable, see >destroy your stack
that's more the case, though languages with tail-recursion can optimise recursion away, so it behaves like a regular loop.

An example of recursion is file tree walking.

Enter directory, print contents, enter printed directory, print contents, enter printed directories, print contents...

>TCO
Doesn't work if you use results from the next steps.

Towers of Hanoi is a bitch to do iteratively

and no
your shitty manual stackframe implementation is still essentially recursion

>retard pajeet only uses control structures instead of using recursion. Maybe learn a non pajeet language like Haskell and you'll start to appreciate recursion faggot cunt. I bet your colleagues are all shitskins.

Haskell masterrace, the only reason you should need to start learning haskell is because it's inaccessible to all the retards polluting the computer science community.

False

Some problems are easier to solve by using recursion. You would know this if you have done anything with trees.

>computer science community
You mean all the NEET sitting in a basement scratching their asses without a job?

this

imo recursion only helps learning stuff
mostly useless in real world applications

but Cred Forums is also mostly trolling if you ask them about recursion
so don't waste your time itt

What are you then? Are you interested in technology or making money? You're just as bad as a dumb pajeet if all you care about is money. Go code your java shit.

>maintaining your own stack
wew lad

recursion is bad if your language wasn't made for using recursion.
If you're using one of those esotheric functional languages, then recursion can be great, because in some cases it can be come much more readable than an iterative solution.
and readable code is code that your dumb coworker won't fuck up due to a misunderstanding.

To understand recursion you need to understand recursion.

that is true

Iteration is literally implemented using recursion

any loop can be written as a goto+label

loops are literally usless, its only uess are to make code hard to read and to destroy your stack

Are you literally retarded?

What do you think running over the same instructions again and again until a certain case is reached is called?

You are literally retarded, off yourself

iteration

wow that image looks trippy if you move your eyes, almost like the lines dissolve and become wavy

it's like one of those optical illusions

It's recursion.

>It doesn't agree with me so it can't be recursion!
There's a beautiful world of low level programming out there that doesn't think everything is about function calls

Iteration and recursion are both high-level concepts for describing algorithms. They're equivalent, and can be freely converted between each other.

Neither of them have anything to do with implementation details. In fact, the implementation will essentially be the same.

Recursion is defined by self-reference, and iteration is defined by repetition. Both are strategies for dealing with problems that have inherent self-similarity.

recursive code is almost always more clear to read than iterative code. if you struggle to read recursive code and have programmed for any significant period of time you're probably retarded.

A: ...
...
mov eax, ...
JNZ A

void fun() {
...
...
if (cond) then
fun();
}

while (cond) {
...
}

void fun() {
if (cond) {
...
fun();
}
}

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a

that is a shit diagram that doesn't accurately model reality

use filter you dumbass, it's clearer, more likely to be optimised and a damn site less hideous

>implying in the case of quicksort comprehension isn't more beautiful than filter
Come on now.

It isn't. Look at your fucking hideous code: Not only is this a dumb example (it's not in place, even if it is lazy) but the actual example is a lot better looking

quicksort [] = []
quicksort (x:xs) = quicksort (filter (x) xs)

No need for fucking ugly let bindings or pointless comprehensions
You could even use fucking a where, jesus let bindings are ugly.

tl;dnr use filter

>your
You got meme'd user, this is from LYAH.
Goes to show how shit that book is.

>haha it's not actually my code! fooled you! i was just pretending to be retarded!
Yeah, sure you didn't actually believe any of what you said

quicksort [] = []
quicksort (x:xs) = subsort ( x)
where subsort c = [ x | x

>you
I'm not but I can just google obviously copypasted code.

You can use (smallerSorted, biggerSorted = partition (

shitSort :: Ord a => [a] -> [a]
shitSort [] = []
shitSort (x:xs) = ls ++ [x] ++ rs
where (ls, rs) = partition (

Get on my level OP

...

Cry more while you're writing Sick OOP (TM)

...

>it has to be function calls

bahaha

>how does this recursion work?
Easily.

However in order to understand recursion you first need to understand recursion.

To whoever took my months-old post severely out of context, the argument was specifically about recursive functions, not recursion as a general concept (e.g. a recursive graph)

Of course there is a concept of a function in assembly.

No, there simply isn't. Assembly has labels, jumps, branches, stacks and calls - but no functions.

Functions are a high-level construct that you can compile down to assembly in a certain way (e.g. by following a specific calling convention and using higher-level metadata to figure out what to call in which way), but assembly itself has no inherent/native concept of a function.

Let's not rehash this retardation again.

That depends on the instruction set. x86 very much does have a concept of a function in that high level sense and can be written as such.
Functions in the sense that they are just chunks of reusable code accessed via long jumps, operate on data, and then return to the calling position have pretty much always been used.

The simple matter that you dismiss it as “retardation” goes to show that you haven't given it any amount of thought at all. You desperately cling on to your C-centric world view in which everything is to be treated a certain way and thinking outside the box is impossible.

What's next, would you argue that NAND logic gates have a concept of a function call? What about natural numbers?

What kind of calling convention does the number 3 use?

There's nothing wrong with recursion if you make proper tail calls.

>x86 very much does have a concept of a function in that high level sense and can be written as such.
You're probably thinking of the ‘call’ instruction, which is a misleading name at best.

‘call’ is simply an instruction pushes the address of the next instruction followed by a jump. It has about as little to do with a function call in something like C or Java as the ‘add’ instruction has to do with rendering this text.

A function in C is defined by a signature, a name, and an implementation plus its corresponding scope. Assembly has none of these.

A good example of the distinction would be to look at branches as a more easily digestable example. Whether you write ‘if’, ‘while’, ‘do .. until’, ‘for’ etc. as a high-level construct has absolutely no relevance in assembly. In assembly, your C compiler will just compile it down to a series of labels, checks and conditional jumps. There's no correlation between the high-level code flow structure and the low-level instructions that are used to realize it in hardware, except in as such as you can read the original intent out of a certain pattern if you are versed in x86/C RE.

Functions are much a similar deal. How your C compiler uses branches, stacks, ‘call/ret’ and function preludes to simulate the semantics of a function call in C are but a single example of how these fundamental building blocks can be used to implement high-level logic.

A compiler for a different, perhaps very different high-level language like Haskell might implement function calls very differently (e.g. indirect jumps and continuation trampolines)

At the end of the day, call, ret, push, pop etc. are just low-level primitives. Assembly does not know nor does it care about what high-level constructs you simulate using them.

Using a hydrogen atom to make an apple does not automatically make the hydrogen atom itself be apple-like in any way.

A nand gate performs a function.

I'm quite an experienced with C and multiple dialects of assembly and humbly disagree with your sentiment.
I believe that the concept of a function is exactly that. A concept, and can be carried across to any platform and implemented at a very low level.
At the end of the day this isn't a technical topic though, and more a matter of computer philosophy.

>What about natural numbers?
You know that the set of natural numbers is defined by application of a function right?

Anything that mathematics can model has sets and applications of sets.

That's true, but also completely irrelevant to the discussion.

Yes, NAND is a function in as much as addition is a function, stack operations are functions, and literally everything else in existence is described by a function.

But we were talking about functions in the sense of a higher-level programming language construct, not in the sense of a mathematical function. As usual, “function” here is a terrible misnomer. Something like “subroutine” would be better.

>I'm quite an experienced with C and multiple dialects of assembly and humbly disagree with your sentiment.
You're fine to disagree, just don't try to argue based on experience. I have a working knowledge of MIPS/x86 assembly, reverse engineering and have been programming C for about a decade as well. It should go without saying that I'm basing my admittedly controversial stances on lots of thought.

>I believe that the concept of a function is exactly that. A concept, and can be carried across to any platform and implemented at a very low level.
I think the problem is that the concept of a function isn't portable. You have functions in C, functions in Haskell, functions in Java, etc.; but they all have vastly different semantics. They are also syntactic constructs in their respective languages.

I can show you where in the C standard, the Haskell report, and the Java specification the concept of a function as a syntactical and semantical element is introduced. They are well-defined objects, with well-defined forms, which are referenced as such throughout the specificaiton.

I cannot, however, show you where in the definition of x86 assembly the concept of a function is introduced. For x86, functions are purely made up.

I can show you the syntactical definiton of a label, or of a ‘call’ instruction. But these are just building blocks. The semantics they describe are very limited.
(cont)

>Completely irrelevant
You brought it up so...

(cont)
There's no definition of what a “parameter” is. There's no definition of what a “return value” is. This is where the whole concept of an assembly “convention” comes in to play.

For example, the very fact that we use ‘A’ to pass return values is merely that: a convention, for enabling compatibility between high-level languages. Assembly does not know nor does it care about what you do with its ‘A’ register. To assembly, ‘A’ is simply a register, nothing more.

>At the end of the day this isn't a technical topic though, and more a matter of computer philosophy.
I agree fully. Like most discussions that I tend to have very controversial opinions on, it is a purely semantical/philosophical debate.

No, you seem to have misunderstood my point. My point is that a NAND gate has nothing to do with a C function (or subroutine as it should be rightfully called).

Whether or not NAND computes a mathematical function is irrelevant, and only you brought that up.

>You know that the set of natural numbers is defined by application of a function right?
That's not even technically true. Natural numbers are defined by an axiom scheme of recursion. Functions don't even “exist” in the universe in which natural numbers are defined, a priori.

In ZF, functions are themselves constructs formed out of sets (specifically, associations between sets - i.e. sets of pairs). They are not an inherent construct in ZF. The inherent constructs are those of comprehension and recursion.

Also, we're getting even further off-track. None of this has to do with C functions.

>I can show you where in the C standard, the Haskell report, and the Java specification the concept of a function as a syntactical and semantical element is introduced. They are well-defined objects, with well-defined forms, which are referenced as such throughout the specificaiton.
>I cannot, however, show you where in the definition of x86 assembly the concept of a function is introduced. For x86, functions are purely made up.
>There's no definition of what a “parameter” is. There's no definition of what a “return value” is. This is where the whole concept of an assembly “convention” comes in to play.
>For example, the very fact that we use ‘A’ to pass return values is merely that: a convention, for enabling compatibility between high-level languages. Assembly does not know nor does it care about what you do with its ‘A’ register. To assembly, ‘A’ is simply a register, nothing more.
>I agree fully. Like most discussions that I tend to have very controversial opinions on, it is a purely semantical/philosophical debate.

Holy mother of autism

Nobody cared about C functions specifically in the first place

who cares

just use python

Don't make me take more screenshots of you

The context that started this was from , which was about whether or not assembly had “recursive functions”, with functions here being understood in the sense of a recursive function in C, Haskell or Java.

You're right in that C is just an example, but it's important to distinguish between a “function” in programming and a “function” in mathematics, is my point.

The former is more rightfully called “subroutine”, really.

You're free to take as many screenshots of me as you like. Just because you fail to understand something does not make it wrong.

A recursive function is a function that refers to itself.

A function takes input and returns an output, that's it. That's why you're wrong.

>A recursive function is a function that refers to itself.
Yes, which assembly doesn't have.

>A function takes input and returns an output, that's it. That's why you're wrong.
Again, which assembly also doesn't have. Even if you want to misconstrue assembly labels as subroutines, they still don't have a concept of “input” or “output”.

Regurgiating basic definitions does not a point make.

bitrev anop
beq .2
pha
asl
jsr bitrev
plx
cpx #$80
rol
.2 rts

Assembly doesn't have a "concept" of anything. Stop saying that. I can create a function in assembly, so assembly does have functions.

Daily reminder that iterative programming does not translate well to quantum computing at all, while functional-ish programming does.

To be fair, neither do. Quantum computers don't handle any form of conditional looping well. If-like conditionals are possible but expensive. Usually what you do in algorithms like Grover search (find element of array in O(sqrt(N)) ) time is to use superposition instead of if-cases to get things done.

Yeah I'm sure it works with acupuncture too

Don't believe me? Here you go: en.wikipedia.org/wiki/Grover's_algorithm

Algorithm for search: no iterating through the array. Instead, apply a higher order function on it's accessor function sqrt(N) time.

>Assembly doesn't have a "concept" of anything. Stop saying that.
Yes it does. For example, it has a concept of a label. A branch. It has concepts of registers, of a stack, of indirect addressing modes. It has concepts of code flow, of operand sizes, etc. It simply does not have a concept of function.

>I can create a function in assembly, so assembly does have functions.
There is a difference between using X to implement Y and X having Y. Sure, you can write an image processing library in C, but that does not mean the C language has a concept of image processing.

Really makes you think...

Assembly calling conventions != assembly language

I am free to write assembly using my own calling conventions that completely disregard the rules set up by the linux amd64 ABI, for example.

Yes, rax etc. are used to hold function results when compiling aginst the amd64 Linux C ABI. Other languages, like Haskell, for example, may completely disregard these calling conventions. As may C compilers that do not need to maintain ABI compatibility with gcc.

>CPU designers write about how to use functions and calling conventions for functions
>Ignores them, saying they don't exist
You're special

>CPU designers make calling conventions
Simply not true. Calling conventions are made by compiler/OS developers, e.g. Microsoft (microsoft x64, fastcall, etc.), System V (linux amd64, etc.) and related.

I bet you think Windows and Linux follow the same calling conventions.

If functions don't exist, then how can a company make a book about assembly in MIPS and refer to functions? If they can, that means functions are a "concept" in assembly.

No, the company is shit and stupid.

Kek, you're so stupid.

this

>If functions don't exist, then how can a company make a book about assembly in MIPS and refer to functions?
If electrons and atoms don't have a flavor, then how can a company make a book about cooking and refer to delicious meals?

#include
#include
#include
#include

#define ITERATIONS 30

uint64_t fibr(uint32_t n);
uint64_t fibi(uint32_t n);

int32_t main(void) {
uint32_t i;
uint64_t ot;
struct timespec t, u;
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &u);
ot=u.tv_nsec;
for(i=1; i

The purpose of recursion is shorter and simpler code, almost never is it actually better code.