wtf how does this recursion work?

>>56743266
Actually that picture is pretty self-explanatory, just imagine each rectangle as a function, or read about recursion anywhere on the internet you lazy dumb fuck.

File: better.jpg (90KB, 720x540px) Image search: [Google]

90KB, 720x540px

>>56743266
it depends how it's nested but the concept is fundamentally identical to all recursion anon

recursion works because of stack frames and base cases

>>56743266
>be absurdly bad programmer
>use recursion in any project
That's pretty much all there is to it

>>56743605
>implying there aren't situations where you want to use recursion
it can be more efficient and simpler

>>56743808
>more efficient
Most likely not.

>>56743808
depends on the language
on poo stuff like java you want to avoid recursion like the plague because very few recursion steps may cause a stack overflow already.

>be absurdly bad programmer
>never use recursion in any project
Ftfy

>>56743882
>iterative DFS

Shut the fuck up

>>56743928
>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

>>56743936
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?

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

>>56744042

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

>>56744042
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.

>>56744128
>>56744230
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

>>56744246
Turing machine has neither.

>>56744291
>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 >>56744230

>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...

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

>>56744246
Towers of Hanoi is a bitch to do iteratively

and no
your shitty manual stackframe implementation is still essentially recursion

>>56743605
>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.

>>56744291
False

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

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

>>56744054
this

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

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

>>56744496
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.

>>56743978
>maintaining your own stack
wew lad

>>56744513
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.

>>56743266
To understand recursion you need to understand recursion.

>>56746061
that is true

>>56744291
Iteration is literally implemented using recursion

>>56744291
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

>>56746130
Are you literally retarded?

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

>>56746453
You are literally retarded, off yourself

>>56746453
iteration

>>56743266
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

>>56746488
It's recursion.

>>56746487
>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.

>>56744291
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();
   }
}

>>56743882

quicksort :: (Ord a) => [a] -> [a]  
    quicksort [] = []  
    quicksort (x:xs) =   
        let smallerSorted = quicksort [a | a <- xs, a <= x]  
            biggerSorted = quicksort [a | a <- xs, a > x]  
        in  smallerSorted ++ [x] ++ biggerSorted  

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

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

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

>>56747480
It isn't. Look at your fucking hideous code: >>56747386

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) ++ [x] ++ 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

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

>>56747558
>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) ++ [x] ++ subsort (> x)
  where subsort c = [ x | x <- xs, c x, then quicksort]

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

>>56747386
You can use

(smallerSorted, biggerSorted = partition (<= x) xs

instead of your two list comprehensions.

Also, your pivot selection is crap. This is barely quick sort - it's a bastardization of it.

>>56747527

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

this is how I'd write it. Also, it's a shit sort. Use mergesort or heapsort

File: 1474635508339.png (15KB, 720x540px) Image search: [Google]

15KB, 720x540px

>>56743266
Get on my level OP

File: o.jpg (64KB, 750x751px) Image search: [Google]

64KB, 750x751px

>>56747726
>>56747706
>>56747615
>>56747582
>>56747558
>>56747527
>>56747386

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

>>56748135
>it has to be function calls

bahaha

>>56743266
>how does this recursion work?
Easily.

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

>>56748196
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)

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

>>56748709
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.

>>56748209
>>56748764
Let's not rehash this retardation again.

>>56748764
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.

>>56748788
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.

>>56748851
>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.

>>56748869
A nand gate performs a function.

>>56748969
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.

>>56748869
>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.

>>56749062
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.

>>56749116
>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)

>>56749195
>Completely irrelevant
You brought it up so...

>>56749195
(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.

>>56749224
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.

>>56749119
>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.

>>56749195
>>56749247
>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

>>56749274
Nobody cared about C functions specifically in the first place

who cares

just use python

>>56749247
>>56749195
Don't make me take more screenshots of you

>>56749324
The context that started this was from >>56748135, 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.

>>56749395
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.

>>56749413
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.

>>56749847
>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.

>>56748764

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

>>56749933
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.

>>56750222
Yeah I'm sure it works with acupuncture too

>>56750260
Don't believe me? Here you go: https://en.wikipedia.org/wiki/Grover%27s_algorithm

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

>>56750027
>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.

File: Screenshot_20160923-145713~2.png (437KB, 1080x1176px) Image search: [Google]

437KB, 1080x1176px

>>56750395
Really makes you think...

>>56750734
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.

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

>>56750887
>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.

>>56750968
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.

>>56751097
No, the company is shit and stupid.

>>56751187
Kek, you're so stupid.

>>56743388
this

>>56751097
>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?

>>56747386

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#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<=ITERATIONS; ++i) {
        printf("%lu\n", fibr(i));
    }
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &u);
    printf("Recursive: %lunsec\n", u.tv_nsec-ot);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &u);
    ot=u.tv_nsec;
    for(i=1; i<=ITERATIONS; ++i) {
        printf("%lu\n", fibi(i));
    }
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &u);
    printf("Iterative: %lunsec\n", u.tv_nsec-ot);
    return EXIT_SUCCESS;
}

uint64_t fibr(uint32_t n) {
    if(!n||n==1) return n;
    return fibr(n-1)+fibr(n-2);
}

uint64_t fibi(uint32_t n) {
    if(!n) return n;
    uint32_t i=0;
    uint64_t j=i, k=1;
    for(; i<n; ++i) {
        k+=j;
        j=k-j;
    }
    return j;
}

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