ITT: Write correct algorithms with comically bad in as few lines of code as possible

ITT: Write correct algorithms with comically bad in as few lines of code as possible.

Other urls found in this thread:

infoworld.com/article/3055885/microsoft-windows/its-time-for-microsoft-to-fix-the-windows-7-update-slowdowns.html
reddit.com/r/compsci/comments/29lgtz/can_the_ackermann_function_be_rewritten_so_that/
youtube.com/watch?v=Mv9NEXX1VHc
youtube.com/watch?v=i7sm9dzFtEI
twitter.com/SFWRedditGifs

for (int i = 0 ; i < MAXN ; i++) {
for (int j = 0 ; j < MAXN ; j++) {
if ( a[i] > a[j] ) {
swap(a[i], a[j]);
}
}
}

function comicallyBad(int) {
/*'REM This has comically bad*/
return;
}

>ITT: Write correct algorithms with comically bad in as few lines of code as possible.

AKA every recursive program ever

This desu senpai

template
void permutation_sort(ForwardIterator begin, ForwardIterator end)
{
while (std::next_permutation(begin, end))
{
// -- this block intentionally left empty by the drunken programmer --
}
}

Lel.

Although while all recursive programs might be comically bad with minimal LOC, I would not say all comically bad minimal LOC algorithms are recursive.

What a discusting language.

Just look at any existing python code

How has the choice of algorithm got anything to do with the chosen language?

This is what code monkeys actually believe.

while not isInOrder(deck):
shuffle(deck)

Recursion has no place in production code.

y tho. it's the best shit ever

Recursive code gave me cancer

i honestly dont understand, why dont you like it? it makes life so much easier

ex:
>infoworld.com/article/3055885/microsoft-windows/its-time-for-microsoft-to-fix-the-windows-7-update-slowdowns.html
>Their supersedence function is un-optimized, now that we have more supersedence than in the past (see KB3035583 & KB2952664, no SP2) this poorly optimized function is causing havoc.
>Called recursively, 20+ layers deep:
>They called this function about 3,270,000 times during the 2 hour check for updates. Microsoft says "Only call this once, it won't change between boots", Microsoft calls it 3.27 MILLION times. Windows update is slow.

It's been awhile since I've programmed anything but isn't this effectively useless?

Computing the 40th Fibonacci number takes 331,160,281 recursive function calls.

Yes it is.
>ITT: Write correct algorithms with comically bad in as few lines of code as possible.

it is correct sorting algorithm, it is comically bad and is only 4 lines of code (You can skip the brackets)

That's true if the coders aren't very good, or the software they are working with is big/messy or they don't have enough time to thoroughly optimize. This is admitidally most of the time, but to unilaterally call recursive programming bad is absurd. Most 'pretty' algorithms are recursive.

There are problems which you can not solve without recirsion

memoization?

>CS majors actually believe this

any recursive statements can be written as loops, any loops can be written as recursive statements but why would you do that because you're overloading memory

True... but then the algorithm actually being implemented by the computer isn't a recursive algorithm.

Hey buddy, you should try to write a simple Merge-Sort/tower of hanoi script with just iteration, then think about how you could have wrote it with recursion without any difference in runtime.

This was meant to be a response to this not the one quoted.

That's as silly as saying a rock falling in a vacuum implement the algorithm speed = 9.8 meters per second per second, technically true, but it misses the point of computation.

Sure, write an Ackermann function without recursion

Oh. Never mind about this then

No it no at all. If you store prior values then it is no longer a true recursive algorithm.

I am so confused.

Could you imagine actually having to do that?
How fucking boring would that be

f a 1 = a
f a n
| n % 2 == 0 = f (2 * a) (n / 2)
| otherwise = a + f a (f a (n - 1) + a - 1)

Guess what this does.

>Not having an argument
Better shitpost

It wasn't supposed to be an argument. I'm just saying it would be really fucking boring, there is no further point

It may be boring and pointless but it shows that there are algorithms that can't be solved without recursion

Ok, i'm not the person you were arguing with and I don't disagree.

is the year 1977? any computer/mobile device comes with >2GB of ram. I don't give a fuck if my stack's gonna be 1M big instead of 400K.
Tail recursion optimizations are also a thing and make recursive code as memory efficient as iterative, if you do it right

Doing things with recursive functions is pretty good for analysis, as you can tend to make the code match the structure of an inductive proof of its required properties...

That said, highly recursive code isn't fast.

multiplies

>you're overloading memory

Maybe if you don't know how to use recursion

any recursive algorithm can be written as an iterative algorithm making use of a stack...
cfr
reddit.com/r/compsci/comments/29lgtz/can_the_ackermann_function_be_rewritten_so_that/

>any recursive statements can be written as loops

Please write a loop that can traverse a tree to any arbitrary depth.

inb4 sleepsort

>recursion

>iterative algorithm making use of a stack
But how is that different from recursion? You're basically doing part of the compiler's job manually.

(define o+
(lambda (n m)
(if (zero? m) n
(o+ (add1 n) (sub1 m)))))

(define o-
(lambda (n m)
(if (zero? m) n
(o- (sub1 n) (sub1 m)))))

(define o*
(lambda (n m)
(if (zero? m) 0
(o+ n (o* n (sub1 m))))))

(define o>
(lambda (n m)
(cond ([zero? n] #f)
([zero? m] #t)
(else (o> (sub1 n) (sub1 m))))))

(define o<
(lambda (n m)
(cond ([zero? m] #f)
([zero? n] #t)
(else (o< (sub1 n) (sub1 m))))))

(define o=
(lambda (n m)
(nor (o> n m) (o< n m))))

some simple math functions built using primitives add1, sub1, and zero?. This sort of thing is fun to think about even if it is impractical.

(positive integer only)

Doing so requires more math than cs majors can handle :^)

>smiley with carat nose
kys

Applied Math major here, I guess you haven't learned anything about recursion.
>youtube.com/watch?v=Mv9NEXX1VHc

>youtube.com/watch?v=i7sm9dzFtEI

>mfw half my classmates don't know what the Ackermann function is
>graduating in a few months

With comically bad what?

most likely asymptotic time complexity, possibly also asymptotic space complexity

Hey OP here. It was meant to be time-complexity

Ideally, but the odd number case fucks it up. Came upon it while messing with discrete logarithms.

q = new queue()
q.push(root)
while not q.empty():
node = q.pop()
do_thing(node)
for c in node.children():
q.push(c)

Laffd

def fib(n, a=0, b=1):
if n == 0:
return a
else:
return fib(n - 1, b, a + b)

It stores that stack in heap, not in program's stack(which is only 8MB by default).

Not guaranteed to finish.

...

The average time will be n!

This is not really being calculated recursively though — the Haskell compiler is smart and is using memoization.

It will almost surely finish in finite time... and yes, I mean "almost surely" in the technical sense. Also, depending on who you perform the shuffling it may even be guaranteed depending on the RNG used for the shuffling.

is_negative(number):
return (str(number)[0])=='-'

tower of hanoi is actually incredibly easy to do iterative

You all are retarded. I'd like to remind you that iteration (as in while (cond), and successfully in for (int i=0;i

public int getnumber(){
Return getnumber();}

In this comment:


>call everyone retarded.

>make some irrelevant point about for loops.

>state some obvious shit that isn't relevant to the discussion about recursion.

>call people pajeets.

>shill imperative languages for muh functional paradigm

>Repeat irrelevant point.

>finish with another obvious point but at least relevant point

Also learn to fucking paragraph.

Neo-Sup Forums everyone

This is like saying that cars are bad because a trained monkey at microsoft once took a bicycle and crashed it into a car.

Can we please stop with the shitty analogies. I agree with the sentiment but was that really the best analogy you could come up with?

I did so in assembly for my programming intro class..

fucking REKT

managed to find the code

#include "asm_regnames.h"

.data
prompt: .asciiz "Input n, m:\n"
.text
.globl entry

entry:
addiu sp, sp, -4
sw ra, 0(sp)

la a0,prompt
jal writestring

jal readdec // n = readdec()
move t0, v0
jal readdec // m = readdec()

move a0, t0
move a1, v0
jal ackermann

move a0, v0
jal writedec

lw ra, 0(sp)
addiu sp, sp, 4
jr ra

ackermann:
beqz a0, n0 // if (n==0) { goto n0 }
beqz a1, m0 // if (m==0) { goto m0 )

addiu sp, sp, -8 // int tmp, ra
sw a0, 4(sp) // tmp = n
sw ra, 0(sp) // ra = $ra

addiu a1, a1, -1 // v0 = ackermann(n, m-1)
jal ackermann

lw a0, 4(sp) // return ackermann(tmp-1, v0)
addiu a0, a0, -1
move a1, v0

lw ra, 0(sp)
addiu sp, sp, 8
b ackermann

n0: addiu v0, a1, 1 // return m+1
jr ra

m0: addiu a0, a0, -1 // return ackermann(n-1, 1)
li a1, 1
b ackermann

I was trying to use a nonsensical analogy for a nonsensical statement. Given by your reaction, I assume I have succeeded in picking a nonsensical analogy but failed in conveying my intent.

2016 and firefox/Sup Forums/whatever still can't handle tab characters, sad.

#include "asm_regnames.h"

.data
prompt: .asciiz "Input n, m:\n"
.text
.globl entry

entry:
addiu sp, sp, -4
sw ra, 0(sp)

la a0,prompt
jal writestring

jal readdec // n = readdec()
move t0, v0
jal readdec // m = readdec()

move a0, t0
move a1, v0
jal ackermann

move a0, v0
jal writedec

lw ra, 0(sp)
addiu sp, sp, 4
jr ra

ackermann:
beqz a0, n0 // if (n==0) { goto n0 }
beqz a1, m0 // if (m==0) { goto m0 )

addiu sp, sp, -8 // int tmp, ra
sw a0, 4(sp) // tmp = n
sw ra, 0(sp) // ra = $ra

addiu a1, a1, -1 // v0 = ackermann(n, m-1)
jal ackermann

lw a0, 4(sp) // return ackermann(tmp-1, v0)
addiu a0, a0, -1
move a1, v0

lw ra, 0(sp)
addiu sp, sp, 8
b ackermann

n0: addiu v0, a1, 1 // return m+1
jr ra

m0: addiu a0, a0, -1 // return ackermann(n-1, 1)
li a1, 1
b ackermann

Okay, thank fuck haha!! I was like 'what in the fuck... this guy must be smoking some heavy doobies'.

But that's recursive.

He just wanted to show off that he knows mips32

please point out where in that code a recursive function call happens

addiu sp, sp, -8 // int tmp, ra
sw a0, 4(sp) // tmp = n
sw ra, 0(sp) // ra = $ra

addiu a1, a1, -1 // v0 = ackermann(n, m-1)
jal ackermann


Right here, you grow the stack and you call ackermann again without having freed the stack.

hmu when you can do a real architecture like ARM64, kid

Even in the comments it's stating it's recursive

this is disgusting

I love it.

>using a stack automatically makes it recursion
Oh, you're one of those people who will twist the definitions of words far enough to win any semantic argument. But your argument is still invalid, and I'll tell you why:

There is no recursion in assembly since there is no concept of a function in assembly.

>you're one of those people who will twist the definitions of words

You're literally the one doing that.

The comment shows the assembly was conceptualized as functions.

By your logic, recursion doesn't exists at all in an executable program since it's all machine code without "the concept of a function"

>the comments to a piece of code define the piece of code
The comment is meant to help understand what the code does. In this case, the comments are written in a recursive manner because the recursive explanation is the easiest to understand.

Note how the actual code deviates from the comments. For example, it overwrites the registers and jumps directly into the target function instead of using a jal whereas the comments (if translated naively) would call a subfunction and then jr the result of this.

Oh my

nice b8

>By your logic, recursion doesn't exists at all in an executable program since it's all machine code without "the concept of a function"
Yes, this is a fully correct statement. Assembly has no concept of recursion, neither do many other machine languages.

Recursion is only a thing that exists in high-level languages which are sophisticated enough to have a concept of self-reference. But just because there exists SOME high-level language in which a recursive code is translated by SOME compiler into assembly X does not somehow magically make the assembly ‘X’ recursive itself.

Case in point: An imperative code could have resulted in the exact same assembly. In fact, assembly is pretty much *the* proof of why imperative and recursive are equivalent; since both imperative and recursive code have to be translated by the compiler into a sequence of labels and jumps - the only form of control flow that exists in assembly.

You could semantically decompile the assembly presented into an imperative program that only uses only labels, goto, a handful of variables and a single data structure that permits LIFO access. (i.e. some stack)

...

You do know that the simpler and more predictable a function call is, the more optimizations can be made by the compiler, right?
If the code is formulated in an obscure and unpredictable way for muh code aesthetics, the compiler cannot take advantage of instruction level parallelism.
It is much more than a GOTO m8.

>recursion doesn't exist
Nice, I guess that's what you'll tell your boss next time a car navigation program you wrote kills someone.

>sophisticated enough to have a concept of self-reference

But Assembly does have that.
See how the ackermann *FUNCTION* references itself though its label?
See how it uses the JAL instruction AND SAVES A REFERENCE TO ITSELF?

Can we have a CS degree meme thread going?

A worked example:

Both this imperative program
f(int x, y) {
while (y != 0) {
x *= x;
y -= 1;
}

return x;
}


and this recursive program
f x 0 = x
f x y = f (x*x) (y-1)


might be translated by their respective compilers into this assembly fragment:

loop:
test B
jz end
imul A, A
dec B
j loop
end:
ret


So is this piece of assembly imperative or recursive?

for (int i=0; i 3; fizz-=3);
for (buzz=I; buzz > 5; buzz-=5);
if (fizz == 0 && buzz == 0) print("FizzBuzz");
else if (fizz == 0) print("Fizz");
else if (buzz == 0) print("Buzz");
else print(i);
}