Krautkanal.com

Veröffentlicht am 2016-04-15 14:39:54 in /prog/

/prog/ 8639: Is recursion used much in everyday programming?...

carlyson Avatar
carlyson:#8639

Is recursion used much in everyday programming?

wtrsld Avatar
wtrsld:#8640

No, also bad coding style.

syntetyc Avatar
syntetyc:#8642

Es ist kein schlechter Programmierstil, aber Rekursion ist meist langsamer als ein iterativer Ansatz. Aber es ist eine gute Abstraktionstechnik.

tereshenkov Avatar
tereshenkov:#8643

Wenn man LISP programmiert, dann ist es gerne gesehen.
Ansonsten nicht.

davidsasda Avatar
davidsasda:#8645

in funktionaler Programmierung ist Rekursion DIE Abstraktion der Wahl, d.h. ja.

Prozessoren sind aber iterativ, daher wird das nach Möglichkeit vom Compiler (ziemlich zuverlässig) in eine Schleife optimiert.

mactopus Avatar
mactopus:#8646

Wenn du einen iterativen datensatz hast, ist das ein muss. Es wird genau so "much in everyday programming" benutzt, wie es auch iterative datentypen werden.

donjain Avatar
donjain:#8649

>>8639
Das Bild war gestern auf der Hauptseite von Réddit (Strange Loop). Bernd verbrachte den ganzen Abend damit, Kurzfilme die von seltsamen Schleifen handeln zu gucken.

>Is recursion used much in everyday programming?

Sehr selten.

saulihirvi Avatar
saulihirvi:#8651

>>8645
Rekursion in eine Schleife zu verwandeln ist für den Compiler aber nicht unbedingt leicht. Jede Rekursion hat ihren gesamten Zustand auf den Stack gesichert. Wenn man jetzt nicht selbst den gesamten Stack in Anspruch nehmen will, dann muss der Datenfluss gut untersucht werden.

craighenneberry Avatar
craighenneberry:#8652

>>8642
dies

Iterative Ansätze sind meistens zu bevorzugen

mugukamil Avatar
mugukamil:#8654

>>8639

Yes, it's brilliant. I always use it to compute Fibonacci numbers.

ajaxy_ru Avatar
ajaxy_ru:#8655

>>8654

This. It's the most efficient way for large numbers.

urbanjahvier Avatar
urbanjahvier:#8656

>>8655
Nein

remiallegre Avatar
remiallegre:#8657

>>8654
>>8655
You're terrible

This approach is fucking bad because the number of times you have to recursively call the function increases for every additional number you want to generate.

Time complexity for computing fibonacci-numbers using recursion:
O(fib(n))
Time complexity for computing fibonacci-numbers using iteration:
O(n)

greenbes Avatar
greenbes:#8658

>>8657
oh, not to mention the massively increased space complexity caused by excessive function calls and added overhead

hampusmalmberg Avatar
hampusmalmberg:#8660

>>8657

It takes my laptop about 2 mins to compute fib(40) recursively. If you know how to do faster than that you've just solved NP = P and should go immediately to Sweden to collect your Noble prize.

joshhemsley Avatar
joshhemsley:#8661

>>8660
oh my god you're fucking retarded
see pic, especially the table, and stop posting here because you're full of shit and spread misinformation

kimcool Avatar
kimcool:#8662

>>8661

Of course it's going to be faster on a desktop computer, it means nothing. You still have to solve NP = P.

jeremyworboys Avatar
jeremyworboys:#8664

>>8662
>You still have to solve NP = P.

stop throwing around terms when you have no fucking idea what they mean

iterative algorithms being better than recursive for everyday situations is in no way related to PvsNP

>Of course it's going to be faster on a desktop computer
wtf are you talking about this is absolutely irrelevant

BrianPurkiss Avatar
BrianPurkiss:#8665

>>8664
>iterative algorithms being better than recursive for everyday situations is in no way related to PvsNP

LOL wut? Recursive functions can often be written with a single line if you use the tertiary operator. Iterative functions take about 10-20 lines at least. Solve NP = P and you might just be able to get it down to 2-3 lines but it will never be as efficient as a single line recursive function.

aadesh Avatar
aadesh:#8666

>>8665
wew lad

we rarely have that much failure on this board

how about you try out the code from the above example, and stop spouting shit?

also loc has absolutely nothing to do with runtime in that case

pic related: something you should read before coming back here

enjoy not being able to compute fib(100) like the retard you are

albertodebo Avatar
albertodebo:#8667

>>8665
also
> Solve NP = P and you might just be able to get it down to 2-3 lines but it will never be as efficient as a single line recursive function.
>implying that PvsNP problem is related to lines of code
>implying 1 loc translates to 1cpu operation

hahahahahahahahahaha

kinday Avatar
kinday:#8668

>>8654
>>8655
>>8660
>>8662
>>8665

8/10 good troll.

terpimost Avatar
terpimost:#8669

>>8660
>>8662
>>8665
Make it more subtle next time.

mylesb Avatar
mylesb:#8671

% time ghc -e 1
1
ghc -e 1 0.13s user 0.02s system 98% cpu 0.159 total
% time ghc -e 'let fibs = [0,1] ++ zipWith (+) fibs (tail fibs) in take 40 fibs'
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]
ghc -e 'let fibs = [0,1] ++ zipWith (+) fibs (tail fibs) in take 40 fibs' 0.15s user 0.00s system 97% cpu 0.159 total
% time ghc -e 'let fibs = [0,1] ++ zipWith (+) fibs (tail fibs) in fibs !! 100'
354224848179261915075
ghc -e 'let fibs = [0,1] ++ zipWith (+) fibs (tail fibs) in fibs !! 100' 0.16s user 0.04s system 98% cpu 0.200 total

zacsnider Avatar
zacsnider:#8672

Wenn ich einen rekursiven Algorithmus verwende.
Und ich entferne jeden rekursiven Funktionsaufruf und mach es iterativ mit einem eigenen Stack....Ist es dann rekursiv oder iterativ?

thehacker Avatar
thehacker:#8673

>>8665
> Solve NP = P and you might just be able to get it down to 2-3 lines but it will never be as efficient as a single line recursive function.

Do you even know what NP = P means?


Also some fun fact: NP != P is not proven yet, but there are a million reasons to believe that it is true. And by the way there is a proof that you cannot prove P != NP with any currently known proving technique.

sementiy Avatar
sementiy:#8674

>>8672
Ja, wenn man einen rekursiven Algorithmus in einen iterativen verwandelt ist er iterativ
hurr

canapud Avatar
canapud:#8676

>>8674

Fun fact: The compiler does the same thing. The CPU is processing code iteratively.

The difference is that if you write recursive code (in one of the common languages), the compiler will create a huge call stack. If you implement your own stack, you might get it done by only stacking the actual data.

If you search huge data structures, it is better to use the stack. You will make fewer mistakes and some overhead don't matter. If you run a calculation like Fibonacci, a call stack is just a waste.

ovall Avatar
ovall:#8680

>>8674
>Ja, wenn man einen rekursiven Algorithmus in einen iterativen verwandelt ist er iterativ
Dann kann ein rekursiver Ansatz keine "bessere" Zeitkomplexität haben, als ein iterativer. Weil ich ihn einfach in einen iterativen umwandle (Stack explizit implementieren) und dann läuft mein (iterativer) Algorithmus mit der gleichen Zeitkomplexität wie der Rekursive.

Jetzt müssten wir nur noch die andere Richtung zeigen: Also dass jeder iterative Algorithmus in einen Rekursiven verwandelt werden kann.

davidcazalis Avatar
davidcazalis:#8681

>>8680
> Also dass jeder iterative Algorithmus in einen Rekursiven verwandelt werden kann.
; als operator der alles was rechts von ihm ausführt und die welt als parameter übergibt. syntaktische konstrukte wie schleifen werden natürlich per rekursion behandelt (teil der ausführungsfunktion)
spezialfälle: programmanfang übergibt nil, termination hinterlässt eine welt an den aufrufer
QED
das kommt natürlich alles auf die syntax an aber denkt euch ; wo nötig einfach dazu

>>8676
> the compiler will create a huge call stack
stimmt nur wenn sämtliche optimierungen failen (schwanzrekursion, stack collapsing bei closure oder was auch immer der fachbegriff ist) und dann gibts noch semantiken wie setTimeout und requestAnimationFrame die auch wenn rekursiv keinen endlosstack aufmachen

herrhaase Avatar
herrhaase:#8687

>>8681
Also sind Rekursive und iterative Algorithmen (zumindest von der Komplexität her) gleich.

Neuste Fäden in diesem Brett: