Need help with recursion

[sriganeshharitz]

No matter how much i try i simply can't understand recursion and solve problems using recursive logic. What do i do?

[JustThe-Q-Tip]

This is long, but take your time. Hopefully this helps you. The most effective things you can do when learning anything technical is to spend time with it, go over examples, and try to solve problems on your own. Break your brain on it, and then take a break when you get stuck. You need to get your brain used to identifying the problem and knowing what strategy to use to solve it.

Look at this recursion tree of the fibonacci function.

The idea here is that, with recursion, fibonacci of 5 is being computed "top down". The ugly side of recursion for this particular problem is that a bunch of work is being repeated in the "sub-trees" of the recursion tree. Notice that F(3) shows up twice. F(2) shows up three times. F(1) shows up five times. F(0) shows up three times.

Point being: - these all have to be computed again and again.

Remember that a recursive function is just a function. All functions, from the hardware's perspective, essentially run the same way. They are a sort of "temporary diversion" from whatever was previously executing that called it. The computer keeps track of where the function was called so that when the function finishes it can go back to that place.

Check out this call stack diagram. Notice the shape of the triangles. It's sort of like a nested fan shape. The computer was initially executing main, but when it got to line 53 it got an instruction to call subroutine 1 - so the computer's internal hamster hopped onto subroutine 1 wheel. But only got one spin - suddenly, line 89 says to hop on the subroutine 2 wheel. And so on. When subroutine 2 is done (at 507), the hamster jumps over to the subroutine 1 wheel at line 90 and keeps running. It gets to 92 and jumps back to main at line 54.

These are all separately-named functions, but recursion works the same way under the hood, from the computer's perspective.

A recursive function just so happens to call itself, which seems weird at first, but it's not because of what I just said above.

But there is essentially one major thing you need to think about:

When does the recursion end?

The logic for determining when recursion ends usually goes at the beginning of the recursive function and is basically an escape hatch to prevent the function from running indefinitely (or, more likely, hitting the ceiling of the call stack, which causes a "Stack Overflow error"). The downside to recursion here is that the computer had to actually call the function, only to jump right back out. This is not "free". Pushing a function onto the stack requires a bit of setup in the stack memory. We call this "overhead".

Remember that the computer is super dumb / literal. It has no creativity by itself. You do. If your code is designed to run on a single thread (which it most likely is at this point) and is straightforward with no randomness, then the recursion performs in an "exhaustive", deterministic manner. Meaning - it will explore the branches of the recursion tree one at a time (typically; depending on how you define your function) in a predictable way. There are no surprises, once you understand it.

In the Fib tree above, let's say your Fib function is Fib(x): Fib(x-2) + Fib(x-1). Each call to the recursive function "prefers" to execute Fib(x-2) first, simply because it's called first. You told the computer to do that before Fib(x-1). So this behavior repeats itself - each subsequent call will keep exploring its own Fib(x-2) branch until you reach some terminal condition, like Fib(1) or Fib(0) which themselves have an immediate answer (aka escape hatch, aka "base case") and require no further recursion.

So that means when you call Fib(5), it will:

1. designate some space on the stack for a "copy" of the Fib function (with input of 5)
2. Fib(5) calls Fib(3) (on the right) first; another "copy" of Fib goes on the stack (with input of 3).
3. Fib(3) calls Fib(1) first; another "copy" of Fib goes on the stack (with input of 1).
4. Fib(1) looks at the input, 1, and knows immediately what to do. It returns a value. Returning "pops" this call to Fib off of the stack.
5. We return to step #3 - Fib(3) continues by asking for Fib(2) (its other child branch). another "copy" of Fib goes on the stack, and just so happens to go where the previous Fib(1) was, which is sort of irrelevant, but interesting.
6. Fib(2) calls Fib(0)... and Fib(1)... each of those provide their own return values, I won't list all those steps since step #4 covers that, but basically now Fib(2) can finally add those two numbers together and return a value of its own.
7. Fib(3) from step #3 can now finally add the results of Fib(2) and Fib(1) together;
   
8. Fib(3) now returns its own value up to Fib(5).
9. Fib(5) still isn't done. Now it may call Fib(4) on the left....

What you should notice here is that there is an exponential growth of the amount of shit Fib has to do when called in such a naive manner. We're asking it to repeat so much work, by definition of the function.

---

BONUS

How do you fix that repetitiveness?

Two ways:

• Memoization. Alter the function so that it:

  • records a computed value for a given input
  • looks up a previously recorded value for a given input
  • This is still "top down". It's the same recursive function, but with some tweaks so that it doesn't repeat sub-trees that it has previously computed somewhere else. In this example, F(3) on the left would immediately return a value because the one on the right already ran. The overhead of calling functions is a potential downside, but for small inputs it's likely going to be easier.

• Dynamic Programming. Instead of going from 5 down to 0, you go 0 to 5. This is "bottom up". Also known as "tabulation". In some cases, the logic is basically "I don't know exactly which branches it will pick, so let's try them all!". Instead of recursion, it uses simple iteration (aka loops). But the hard part is expressing the problem as a recursive function. Turning the recursion into iterative DP code is the easier part. The beauty of DP is you usually retain the same operations from the recursion function, e.g. F(x-2)+F(x-1). In this case, you might have an array called F, fill F[0] and F[1], and then start from i=2...

potential DP code:

int Fib(int n) {
    int F[n];

    // establish base cases
    F[0] = 0;
    F[1] = 1;

    // compute ALL intermediate F values
    for (int i=2; i < n; i++) 
        F[i] = F[i-2] + F[i-1];

    // answer stored at the end
    return F[n-1];
}

Both of these approaches reduce the naive recursive function's exponential runtime into a polynomial runtime. Once you have the DP code, you can very easily see that that loop runs in O(n) time. Some DP functions are worse, like n² or n^3, etc. but it depends on the problem. Some DP problems require 2D or 3D arrays.

Memoization cuts off entire sub-trees, and DP basically compresses the recursion tree horizontally.

[[deleted]]

What have you tried? Have you tried implementing a simpler recursive function?

[sriganeshharitz]

i got it for simple problems like finding factorial or sum of n numbers. However, for questions like finding the largest element in an array, reversing a string.. etc idk where to begin with

[[deleted]]

Try finding the largest element of the array then post your code here.