Issues with understanding recursion

[fuicious]

Okay as the title suggests, I'm having some problems getting my head around recursion. I've been over a couple of tuts, articles and tasks that involve recursion but the explanations are kinda alike and don't help me very much. And for the tasks I've solved using recursion I would have never gotten the idea to use it if it wasn't suggested as a solution to the problem.

I've searched for it on the forum but there's only a general explanation of what a recursion is and I do understand that. I'm sorry if there is something I didn't find.

So what I'm asking is if there's any resource you guys would recommend that helped you really understand recursion. Does it come naturally to you to approach a certain problem recursively? Because I don't really see a point in using just for the sake of doing so. So if anyone got some tips, they would be more than appreciated.

[Phage]

My simple reply: http://stackoverflow.com/questions/717725/understanding-recursion

Get on IRC if you want an in-depth talk about it.

[vinci]

Recursion is for repetitive tasks, or functions that call themselves. Imagine two mirrors facing each other. That's recursion. Unless you have some condition to break the loop it is infinite. You should look up factorials. That is one application of recursive calls

[Trevor]

So what is recursion ?

When a function calls itself, it is called a recursive function. Some problems by nature are recursive.
 
Lets take the case of Fibonacci numbers, it's a series of where every number is the sum of the preceding two numbers. The first and second numbers of the series are 0 and 1 respectively by definition since they do not have two preceding numbers.

Thus the series looks like:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

We can define the n^th term of the fibonacci series by,
t₀ = 0
t₁ = 1
t_n = t_n-1 + t_n-2

Now suppose we need to calculate the 15th term i.e. t₁₅ of the series.
How would you go about ?

Now,
t₁₅ = t₁₄ + t₁₃

To calculate t₁₅ we need the values of t₁₄ and t₁₃.
Similarly, to calculate t₁₃ we need the values of t₁₂ and t₁₁

Hence, you can see each term of the fibonacci series is defined by the preceding two fibonacci numbers; and again each of the two preceding numbers is defined by their respective predecessors.

This is a called recursive definition.

In a hypothetical language, we can write a function to calculate the nth of the series as:

Code: [Select]

function Fibonacci(n: Integer)
    if (n = 0) return 0  //first term is zero
    else if (n = 1) return 1 //Second term is 1
    else return Fibonacci(n-1) + Fibonacci(n-2)
end
The first two if statements are called base cases. Without them the function would call itself endlessly. In every recursive problem we need base cases to prevent an infinite loop.

Hope this explanation clears thing up a bit

[fuicious]

@vinci and @Trevor,
I appreciate your answer, but as I've already mentioned I do understand what recursion is and I can manage those simple examples you mentioned.
However, the problem is that I would always choose to do this iteratively instead of recursively, but I do admit that recursion here looks much better in my opinion, that's why I'm trying to understand it.
Yesterday I wanted to write a function that prints out permutations of string. Didn't really have much success so I looked it up on the internet and there I had learned an algorithm that uses recursion and in the end I managed to write it in code. But not in a million years would it have occurred to me to try to approach that particular problem recursively...

@Phage, thanks for your input, I'll check it out. I don't really wanna bother you on IRC, reading material is enough I think.

[techb]

Maybe your instructor isn't teaching it a way you understand.

Here is a lecture from MIT that might help.

http://video.mit.edu/watch/recursion-11036/

[TheWormKill]

@vinci and @Trevor,
I appreciate your answer, but as I've already mentioned I do understand what recursion is and I can manage those simple examples you mentioned.
However, the problem is that I would always choose to do this iteratively instead of recursively, but I do admit that recursion here looks much better in my opinion, that's why I'm trying to understand it.
Yesterday I wanted to write a function that prints out permutations of string. Didn't really have much success so I looked it up on the internet and there I had learned an algorithm that uses recursion and in the end I managed to write it in code. But not in a million years would it have occurred to me to try to approach that particular problem recursively...

@Phage, thanks for your input, I'll check it out. I don't really wanna bother you on IRC, reading material is enough I think.

As a functional programmer, I deal a lot more with recursion, so I guess I might add my grain of salt here.
The basic concept behnd recutsion is, as already pointed out, dividing up your problem in small, simple-to-reason-about parts. In principle, every loop you write can be transformed in a tail-recursive function (which is just a function that performs some work and recurses afterwards and obv. has a base case which terminates recursion). However, in imperative languages, you'd rather not do that, because calling a function involves allocating space on the stack, which can in turn lead to an overflow. However, in mathermatics, as well as functional programming, recursion is much more common. This is due to a multitude of factors, but I believe there are two main reasons: First of all, many definitions of "natural structures" (real world objects, number series, ...) are recutsive by definition, because it is a much more concise and short form of describing a problem, thus easier to reason about (in theory). Secondly, you can implement recursion (and function calls) in a different manner without relying to heavily on the stack (which is what compilers for functional languages do), but that's another topic.

So to conclude, recursion and iteration are concepts that are practically interchangeable, where recursion is just more declarative and powerful (you can branch using recursion in ways that a loop doesn't permit), and iteration is more oriented towards an algorithmic thinking, whereas recursion is a more general, versatile and less constrainted approach, which leads to disadvantages: being harder to grasp to a novice and being harder to implement efficiently.

I hope that cleared up your question.

[fuicious]

Maybe your instructor isn't teaching it a way you understand.

Here is a lecture from MIT that might help.

http://video.mit.edu/watch/recursion-11036/

A nice lecture, thank you.

@TheWormKill, I think it's a little clearer to me now. I just need more practice I guess.

[iikibT]

To learn more about recursion, see this post.