0

When you use recursion to solve a problem, why does the recursion method need to call itself to solve a smaller version of the original problem?

Jason D
  • 11
  • 1
  • 3
    Because if it doesn't call itself, then it's not recursion? The word "recursion" *literally means* a method calling itself. – user253751 Aug 12 '15 at 21:58
  • It doesn't need to. Imagine you make separate functions that solves just one step and as default case calls a different method to solve the rest. It will still work, but you'd have a lot of similar looking methods that look exactly the same but with different names to the defautl case method. Since the methods look the same you migth as wellrecurse and save a lot of code. It's not like the process will be different since every call to the same method is handles separately so it's just like calling any other method really. Recursion isn't that special. – Sylwester Aug 12 '15 at 22:35

3 Answers3

0

By definition, a recursive function calls itself.

If you are asking when or why you would use recursion, it is well suited for problems that resemble a fractal. IOW, when small parts of the problem look similar to larger versions of the problem.

Kevin Seifert
  • 3,494
  • 1
  • 18
  • 14
0

The general idea behind solving a problem recursively is to find a way to break the problem down into smaller copies of itself, solve those smaller copies, then combine the results together to solve the overall problem.

So let's suppose that you're trying to write a function solveProblemX that solves a problem X recursively. You break the problem down into smaller copies of problem X, and now you need to solve each of them. How do you do that? Well, you're currently writing a method called solveProblemX that specifically is designed to solve problem X, so one option would be to recursively call solveProblemX on those smaller problem instances. After all - if solveProblemX really is supposed to solve problems of type X, there's nothing wrong with doing this!

What changes from problem to problem is how you break the problem down into smaller copies of itself and how you combine them back together. In each case, though, just keep in mind that the function you're writing is designed solve problems of one type, so there's nothing concerning about calling the method you're writing to solve smaller problems of that type.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

I'll try to explain the way that I had it explained to me.

Say you're in a line at a coffee shop. The line is really long, and you're all the way at the back. You want to know how many people are in front of you, but you can't see the front, so you can't count everyone yourself. You instead ask the person in front of you "How many people are in front of you?". He then follows your same logic, and asks the person in front of him. Everyone asks the person in front of them until they get to the person at the register. Once the person in front is asked, they answer with 0. That would be the base case. After the person in front responds, the second person in line responds with 0+1, so 1. That continues all the way back to you until you know how many people are in line.

I'm paraphrasing something from somewhere, but I don't remember where I originally saw it.

carterw485
  • 798
  • 1
  • 7
  • 13
  • But it's better to pass a piece of paper to each person where he will increase the current count by one. The last person will increase counter and loudly shout the sum). In Scala it's called a *tail recursion* and optimized to regular loop by compiler not to get stackoverflow. – ka4eli Aug 12 '15 at 22:32