I need help in trying to fully understand the concept of recursion

Question

Before you get started, I have used google countless times in hopes of searching for a very brief and simple explanation of how recursion works when it has a return type. But I guess I'm not as bright as I thought since i still cant understand it quite well.

Take the following code snippet (in java) as an example

public static int recursion(int num)
{  
 int result;   

if (num == 1)
    result = 1;

else           
     result = recursion(num - 1) + num; 

return result;

}

I grabbed this code from my professors lecture slide and he said this will return 1 + 2 + 3 + ... + num.

I just need someone to explain how the process works in the method that i provided. Maybe a step by step approach might help me understand how recursion works.

Check out this question it should help ;) http://stackoverflow.com/questions/44055646/i-need-help-in-trying-to-fully-understand-the-concept-of-recursion — Persixty, May 18 '17 at 18:48
Tip: When your professor introduces some concept ask him what you didn't understand. Always. They are there to help you, so if you didn't understand you need to ask them to explain the concept again. Regarding your code, I think debugging it step by step will make it really easy. — BackSlash, May 18 '17 at 18:48
best I can do is suggest writing out what each of the variables in the function evaluates to when you plug in some concrete numbers. So, say, you start with a call `int result = recursion(4)`. Write out what and how execution is going to look like till it returns a final value with a pencil and paper. I think it'll help to answer your question. — C0D3LIC1OU5, May 18 '17 at 18:51
To understand recursion you need to understand recursion. But for this specific example take a look at http://stackoverflow.com/a/26204779. — Pshemo, May 18 '17 at 18:51

score 8 · Accepted Answer · answered May 18 '17 at 18:51

recursion(5) = recursion(4) + 5, let's figure out recursion(4) and come back to this later

recursion(4) = recursion(3) + 4, let's figure out recursion(3) and come back to this later

recursion(3) = recursion(2) + 3, ...

recursion(2) = recursion(1) + 2, ...

recursion(1) = 1, we know this!

recursion(2) = 1 + 2, now we can evaluate this

recursion(3) = (1+2) + 3, and now we can evaluate this

recursion(4) = (1+2+3) + 4, ...

recursion(5) = (1+2+3+4) + 5, the answer to our original question

Note: Without knowing recursion(1), we'd have gone to 0, -1, -2, and so on until forever. This known quantity is called the base case and it is a requirement for recursion.

Step by step debugging, the most powerful way to understand how some code works. Amazing! — BackSlash, May 18 '17 at 18:56

score 0 · Answer 2 · answered May 18 '17 at 18:53

Basically when there is a stack buildup for each item that is created beyond the last iteration. (Where num=1)

When n>1 the if statement kicks the iteration to the else which 'saves' the result in a stack and calls the same funtion again with n-1

what this effectively does is keep calling the same function until you hit your designated 'base case' which is n=1

score 0 · Answer 3 · edited May 23 '17 at 10:31

Going by the classic code example you posted. if you call your method like so with number passed in as 5:

recursion(5);

In layman terms just to understand, your function will create & call another copy of your function in the else block as below:

recursion(4);

and then

recursion(3);
recursion(2);
recursion(1);

as the number keeps decrementing.

Finally it will call the if part in the final copy of the method as num will satisfy num == 1. So from there it starts unwinding & returning each value to the previous call.

As each method call has its own stack to load method local variables on, there will be n number of stacks created for n calls. When the deepest call in recursion is made, then the stacks start unwinding. Hence recursion achieved

The most important thing however to note is that there is a base-most call in your code, which is done at 1 just because you have the check if (num == 1). Else it would be infinite recursion & of course a fatal & wrong program to write. The base-most call is from where its called as stack unwinding in recursion terms.

Example: Finding the factorial of a number is the most classic examples of recursion.

Performance: Do look into recursion vs iteration and recursion vs looping to see what are the performance impacts of recursion

score 0 · Answer 4 · answered May 18 '17 at 18:55

Recursion is all about solving a problem by breaking it into a smaller problem. In your case, the question is "how do you sum the numbers from 1 to n", and the answer is "sum up all the numbers from 1 to n-1, and then add n to it". You've phrased the problem in terms of a smaller or simpler version of itself. This often involves separating out a "base case"—an irreducibly simple problem with a straightforward answer.

public static int recursion(int num)
{  
 int result;   

if (num == 1)
    result = 1;   // Base case: the sum of the numbers from 1 to 1 is 1.

else           
     result =
         // This is the sum of numers from 1 to n-1. The function calls itself.
         recursion(num - 1)
         // Now add the final number in the list, and return your result.
         + num; 

return result;

}

You're defining the unsolved problem in terms of itself, which works because the solution always involves either the base case or a simpler version of the problem (which itself further involves either the base case or an even simpler version of the problem).

I'll close with one of my favorite jokes:

How do you explain recursion to a five-year-old?

You explain recursion to a four-year-old, and wait a year.

I need help in trying to fully understand the concept of recursion

4 Answers4