Software Development and Programming Careers (Official Discussion Thread)

[OCCAMS_RAZOR]

Recursion is something I've been trying to figure exactly what it is. I know essentially a function calls itself, creating a sort of loop, but where and why is it used?

where it's used? think of fibonacci numbers. write a function that allows you to determine the nth fibonacci number. problems that are of a recursive nature like fibonacci lend themselves very well to a recursive algorithm. however, in most cases recursion is expensive.

as for why it's used, that's not a question i can fully answer.

algorithms and big oh is a staple of things. if you cant analyze algorithms, you cant really program lol. its quite easy too, nothing complicated as long as you can do medium-level math.
I wouldnt put it as a way of meeting deadline, its just one of those things you use all the time to make design decisions. its really a building block of things that you just kinda have to know. I dont think theres a way around it once you write code that resembles real-world projects

cool. i like your attitude. as an engineer / programmer you should never at any point say that this piece of knowlege is not necessary. you should always be hungry to know more.

 

[Spatial Paradox]

Recursion is something I've been trying to figure exactly what it is. I know essentially a function calls itself, creating a sort of loop, but where and why is it used?

A recursive function is one that calls itself within its definition. Recursion tends to be used for problems where the results can be found by solving smaller subsets of that same problem.

i.e. Calculating the fibonacci number for n. You can calculate it using a loop. But if you know the fibonacci number for n - 1 and for n - 2, you can just add those two results together

A (very naive) fibonacci function using recursion:

int fibonacci(int n)
{
    if n < 2
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

[OCCAMS_RAZOR]

why is [recursion] used?

as for why [recursion] is used, that's not a question i can fully answer.

recursion is just much more easy and elegant in certain cases which include nodes, children and nesting

it really is elegant. if you can wrap your head around recursion, the algorithms are just

 

[yseJ]

recursion is hard to explain, Im sure theres some very good explanations online. its basically dividing up the algorithm into more smaller solutions and have a 'memory' where you can store intermediate results (a stack)
you can explain it mathematically, computational theory-wise or low-level lol.

theres tons of real life implications

 

[OCCAMS_RAZOR]

A (very naive) fibonacci function using recursion:

int fibonacci(int n)
{
    if n < 2
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

a buddy of mine was asked to write the algorithm for finding the nth fibonacci in an interview. dude was able to do it, but after he was done ...

interviewer: not bad. aaah, so what's the run-time ...

my bud: (fukk, if i know) Let me try at a guess ... O(n^2) ???

interviewer: (you know you done fukked up right?) Try again breh

my bud: O(n^3)

interviewer: nah breh ... O(2^n)

my bud:


i didn't even know the actual run-time when he was telling me the story but i was at him on the low because, exponential run-time is pretty much the worst it could ever get when it comes to algorithms. dude completely missed the mark.

take away from story? recursion algorithms are but the runtimes are

 

[Spatial Paradox]

a buddy of mine was asked to write the algorithm for finding the nth fibonacci in an interview. dude was able to do it, but after he was done ...

interviewer: not bad. aaah, so what's the run-time ...

my bud: (fukk, if i know) Let me try at a guess ... O(n^2) ???

interviewer: (you know you done fukked up right?) Try again breh

my bud: O(n^3)

interviewer: nah breh ... O(2^n)

my bud:

take away from story? recursion algorithms are but the runtimes are

That exponential run time

But this is actually a good example of why analyzing algorithms (or at least being familiar with them) is important. In this case, one could ask themselves why is the runtime so awful? If you visualize the recursive calls to the fibonacci function, you can see you're recalculating past values over and over again

I'd bet the interviewer might've been more impressed with this (pseudocode isn't really in a specific language):

Dictionary <int, int> fibMemo = new Dictionary<int, int>();

int fibonacci(int n)
{
    if (fibMemo[n] != null)
        return fibMemo[n];
    int result = fibonacci[n - 1] + fibonacci[n - 2];
    fibMemo[n] = result;
    return result;
}

By stashing past results for a given n, you don't have to keep constantly recalculating them. The run time drops to O(n), though you might be by making a tradeoff in terms of space

 

[kevm3]

thanks for the replies to the recursion question

I'm going to spend some time playing around with algorithms, starting off with various search algorithms.
this seems to be a fairly interesting page

http://bigocheatsheet.com/

 

[OCCAMS_RAZOR]

Dictionary <int, int> fibMemo = new Dictionary<int, int>();

int fibonacci(int n)
{
    if (fibMemo[n] != null)
        return fibMemo[n];
    int result = fibonacci[n - 1] + fibonacci[n - 2];
    fibMemo[n] = result;
    return result;
}

By stashing past results for a given n, you don't have to keep constantly recalculating them. The run time drops to O(n), though you might be by making a tradeoff in terms of space

Hmmm ... I like this ... very clever. However, it's really not that different from the naive implementation tbh. Supposing that we are allowed to run each algorithm once, then this new one will actually be worse than the naive implementation because now you have the overhead with dealing with the dictionary abstract data type, and also the space requirements would be atrocious. I mean imagine if someone requested the algorithm to spit out the 100,000th fibonacci ...


but you're right, over time this would be a better alternative. when you think about the amortized cost, each call would eventually whittle down to O(1) which is the runtime.

overall, i think when it comes to interviews, they don't really expect you to spit out the ideal answer all the time. but they do want you to be clever enough to know that your answer is non-ideal, and exactly why it is so. if you can be able to have an intelligent discussion with the interviewer regarding the problem at hand then you should be fine. i don't have a lot of experience with hardcore interviews though so you can take my advice with a grain of your finest salt.

 

[kevm3]

I've been spending all kinds of time messing around with javascript... it's fun doing these little experiments. I need to find a free web host so I can post these experiments up.

 

[keepemup]

a buddy of mine was asked to write the algorithm for finding the nth fibonacci in an interview. dude was able to do it, but after he was done ...

interviewer: not bad. aaah, so what's the run-time ...

my bud: (fukk, if i know) Let me try at a guess ... O(n^2) ???

interviewer: (you know you done fukked up right?) Try again breh

my bud: O(n^3)

interviewer: nah breh ... O(2^n)

my bud:


i didn't even know the actual run-time when he was telling me the story but i was at him on the low because, exponential run-time is pretty much the worst it could ever get when it comes to algorithms. dude completely missed the mark.

take away from story? recursion algorithms are but the runtimes are

Nah breh. The most important part of the story is 'did he get the job?' which you left out.

 

[keepemup]

Recursive algorithms are good when you've got a lot of ram to waste. Don't try that sh*t in embedded. Don't you dare. But then again those types of problems/algorithms usually don't have a use in an embedded system.

 

[OCCAMS_RAZOR]

Nah breh. The most important part of the story is 'did he get the job?' which you left out.

hell naaw man. that's why i used the mj smiley. dude fell on his face.

let the interview story be a lesson to you nikkaz who like to go into interviews with a swagger in ya step, on some 'I'm the next Q' 'The Next Zuckerburg' steez ...

know ya runtimes brehs. it could be the difference between being a Starbucks Barista and being gainfully employed.

 

[keepemup]

hell naaw man. that's why i used the mj smiley. dude fell on his face.

let the interview story be a lesson to you nikkaz who like to go into interviews with a swagger in ya step, on some 'I'm the next Q' 'The Next Zuckerburg' steez ...

know ya runtimes brehs. it could be the difference between being a Starbucks Barista and being gainfully employed.

Lol. But ol' boy should know his algorithm run times. Big O notation is easy once you have the algorithm.

 

[Spatial Paradox]

Hmmm ... I like this ... very clever. However, it's really not that different from the naive implementation tbh. Supposing that we are allowed to run each algorithm once, then this new one will actually be worse than the naive implementation because now you have the overhead with dealing with the dictionary abstract data type, and also the space requirements would be atrocious. I mean imagine if someone requested the algorithm to spit out the 100,000th fibonacci ...


but you're right, over time this would be a better alternative. when you think about the amortized cost, each call would eventually whittle down to O(1) which is the runtime.

Even for a single run, it makes a massive difference. On my machine (a laptop with a quad-core Core i7 w/2.3GHz base frequency), the naive implementation of the Fibonacci function in C# takes about 15 seconds when n = 45. For the modified version using a dictionary, I can't even tell you how long it takes because it completes almost immediately from my POV. The overhead of the dictionary has more of an influence on the space complexity, which ends up being O(n).

As an aside, I decided to look up the 100,000th Fibonacci number. It's as ridiculous large as it sounds

overall, i think when it comes to interviews, they don't really expect you to spit out the ideal answer all the time. but they do want you to be clever enough to know that your answer is non-ideal, and exactly why it is so. if you can be able to have an intelligent discussion with the interviewer regarding the problem at hand then you should be fine. i don't have a lot of experience with hardcore interviews though so you can take my advice with a grain of your finest salt.

C/S. You should at least be able to talk about why a given solution to a problem is or isn't ideal, and why.

 

[kevm3]

I'm having a blast with programming. This is one thing I love. I just wish I started earlier, but oh well. I'm finally starting to get a handle on node.js. Once I'm really able to ingrain using node js and talking to the database, my 'web apps' can really start to take off.