[a / b / c / d / e / f / g / gif / h / hr / k / m / o / p / r / s / t / u / v / vg / vr / w / wg] [i / ic] [r9k / s4s / vip / qa] [cm / hm / lgbt / y] [3 / aco / adv / an / asp / bant / biz / cgl / ck / co / diy / fa / fit / gd / hc / his / int / jp / lit / mlp / mu / n / news / out / po / pol / qst / sci / soc / sp / tg / toy / trv / tv / vp / wsg / wsr / x] [Settings] [Search] [Home]
Board
/g/ - Technology

You cannot reply anymore.

File: 1517429337730.png (105 KB, 645x729)
105 KB PNG
Dumb question: What is recursion and how it is applied into programming.

t. First year idiot
>>
`int recursion(int N){    if (N == 0)        return N;    return recursion(N-1);}`
>>
>>66703377
it exists for faggots who can't into loops
>>
>>66703377
a reduction of a problem onto itself. Some algorithms are expressed cleaner in recursive form.
>>
>>66703377
Say you have a box, and inside it are a potentially infinite number of boxes. Your goal is to get to an arbitrary number of boxes deep, called N, where something you're looking for exists.
You don't know what level it's at, and you don't know how many boxes within boxes there are.
So you start at the top, N = 0, and see if it's in there. All you see is the lid to another box.
So you open that one, N = 1. Yet another box.
You keep going for some amount of time, until eventually you open up a box, and there's the thing you needed.
This is recursion.
>>
>>66703377
Recursion is (more or less) solving a problem using a function that calls itself such as calculating a Fibonacci number by calling the Fibonacci function for both prior digits, which call it for both prior digits, on and on until you reach some base case (the two 1s in the case of Fibonacci).
It's beautiful/neat in theory but isn't enormously useful in practice because the way processors are architected can make it quite slow compared to solving the same problem with a loop.
>>
>>66703377
Signature fag OP
>>
>HURR DURR muh syntax imported from twitter
>>
>>66703836
>>
>>66703377
>literally copying the question from the exam paper
do you people still wonder why you can't get a job with your CS """"degree"""?
>>
>>66703853
You got me good anon
>>
>CS student
>First year
>Doesn't know recursion

The fuck negro, are they teaching you ANY math?
>>
>>66703377
>Dumb question: What is recursion and how it is applied into programming.
>t. First year idiot
>>
>>66704069
who are you quoting
>>
>>66703400
By your hot opinion all professional compiler implementers are faggots that can't into loops.
>>
Recursion in 2018 is literally useless

Prove me wrong
>>
File: 1527986570158.png (16 KB, 691x597)
16 KB PNG
>>66703377
in terms you can understand are are familiar with:
recursion is like when you have a penis and you stick it into another guys butthole and your penis is so long it goes all the way to the other side so you're like using that guy's penis as your own and that penis is also really long, so long that you can use it to stick it in your own butthole and use your penis as a sleeve.
>>
>>66704172
>>66704194
>>66704223
stop it you failure
>>
>>66704277
Who are you quoting
>>
Make sure to memoize
>>
>>66704288
retard
>>
>>66704118
Yes, it literally should be

>>
>>66704203
>>
>>66703377
recursion is a bitchass function that calls itself
>>
>>66703377
>t. First year idiot
That's fine. You stop being an idiot after 5 years into the workforce. Until then just stay humble, learn a lot and do your best not to become a lolcow. Ideally stop browsing this board.
>>
>>66703400
Somethings can't be done with loops, you retard, at least no elegantly.
>>
>>66703391
Why are you returning N if you know it is 0?
You're wasting time accessing memory.
>>
>>66704069
twitter syntax signature faggot
>>
>>66705843

Not the guy who posted it, but the point of the function is to demonstrate how to make a function execute say 10 times by feeding it a 10. It's not actually designed to return useful information.

A real world example would be a Bezier curve... which Interpolates between the result of 2 more interpolations to make a smoother line.

Technically that can be simplified with math to a non-recursive method that takes up less memory and operations, but that's 1 handy example:

https://www.desmos.com/calculator/cahqdxeshd
>>
>>66703377
It's a way to calculate Fibonacci sequence.
>>
>>66704938
Excellent quality bait
>>
File: hoshimitsu.png (493 KB, 614x420)
493 KB PNG
>>66703400
>tower of hanoi iteratively
>>
The best time to use it is when you see yourself writing more than like 4 nested for loops, if you go that deep then recursion will probably be more readable and easier to write, but it's especially good since you can kind of "create" infinite nested loops, where obviously writing 150 nested loops is fucking ridiculous, recursion just kind of does it.
>>
>>66703400
t. 1st year CS student who thinks he's hot shit when he actually has no clue and will cringe at this opinion in 2 years time
>>
>>66703377
say you want to write a function that evaluates the factorial of a number
In JS
`function factorial (num) {if (num <= 1) {return 1;} else {return  num * factorial (num-1);}}console.log("10! equals " + factorial(10));`
>>
>>66703400
It's awfully convenient when implementing algorithms though
>>
>>66703400
>>66706539
with a for loop lmao
`var total; function factorial (num) {  total = 1;   for (var i = num; i>0; i--) {     total *= i;  }  return total;}`

JavaScript handles taking functions as arguments really well, but if you try recursion in another way (without using trampoline functions) for big numbers you exceed the maximum call stack and your browser crashes.
This is because JS doesn't support tail call optimisation (is this correct?).

What languages do support tail call optimisation? Does anyone know?
also, are there any languages other than python that support arbitrary length integers (rather than 64 bits or whatever)?
I really want to learn another language and right now I'm tossing up between Java and Python
>>
>>66703377
Suppose you want to count how many things are in a list.
In this list, every thing is a thing and a reference to the next thing. The last thing in the list references null as the next thing, so you know it's the last one when you see it.
Now, you write a function that does the following:
- take the list
- look at the first thing in the list
- if you find a null, return 0
- if not, you remove the first thing in the list and call the function again, using your shortened list as the argument
- and add 1 to whatever that function is going to return

Suppose your list is three things long.
length(1,2,3); will become length(length(2,3)) and then length(length(length(3))) and length(length(length(length(null)))).
The last call to length() returns zero and all the other ones add 1 to it. Your length is 3.

The alternative is to use a loop to iterate through the list elements and keep a count of them in a variable. Recursion might be useful here if your lists are going to be longer than what you can store in a single variable.
>>
>>66704055
>>66704055
This.

I didn't even take full uni level courses nor do I go into CS but I even know what recursion is.

Is this the famous American Education I keep hearing of?
>>
>>66703377
It's something you use whenever a simple and readable iterative solution with for-loops stops being simple.

For instance - basically anything concerning trees. Without recursion you'd need some stack to manually track the nodes you still gotta visit.

> muh performance
> muh real world usecase
Whenever you call a function/method/subroutine/whatever you need to allocate memory. It's kind of a fixed price you gotta pay for the abstraction. If you do A LOT of recursive calls you might go out of memory quite soon; most of the modern programming languages optimize away this kind of memory pattern directly in the compiler (or interpreter) - it's called TCO(tail call optimization), look it up.

Still, some people here on /g/ who program in certain brainletlangs hiss at the recursion because their favorite brainletlang does not support it; or - more likely - they're too retarded to understand it themselves.

It is true, though, that, for the sake of readability you might sacrifice some performance. Always benchmark your shit when you implement it.

In the *actual* real world though an average programmer doesn't often finds himself implementing something that needs deep algoritmic knowledge, because 99% of his job is to glue up libraries together to please his hebrew overlord (AKA the CEO). So, don't overuse it. I'm a clojure (lisp on JVM) programmer, and I had to write manually recursive functions 2-3 times max so far; YMMV.
>>
>>66706056
What's Twitter syntax? I don't use Twitter and don't get the reference...
>>
>>66704318
>off by one each time
JUST
>>
>>66703377
LOGO.

Delete Post: [File Only] Style:
All trademarks and copyrights on this page are owned by their respective parties. Images uploaded are the responsibility of the Poster. Comments are owned by the Poster.