Any helpful explanations of recursion?

[Maximilian]

Its doing my head in, ive written a simple recursive program to add numbers in an ArrayList entirely by myself but the kicker is I don't fully understand why it works heh. I gather a new stack?? is created each time the method addNumbers calls for itself and it dosent finish the current stack until the last ones done....then it comes back and finishes them... i dunno its pretty hazy.

How does it add the numbers without resetting runningTotal to 0 each time? Why dosent it just return 0 when numberList has nothing left in it?

public static void main(String[] args)
{
List<Integer> numberList = new ArrayList<Integer>();
numberList.add(5);
numberList.add(10);
numberList.add(10);
numberList.add(3);
System.out.println(addNumbers(numberList));
}

public static int addNumbers(List<Integer> numberList)
{
Integer runningTotal = 0;
if (numberList.isEmpty())
{
return runningTotal;
}
else
{
runningTotal = runningTotal + numberList.remove(numberList.size()-1);
return addNumbers(numberList) + runningTotal;
}
}

 

[masteryoda34]

It may help you to start with a simpler example of recursion:

int fibonacci (int n)
{
     if(n == 0) return (0);
     else if(n == 1) return (1);
     else return (fibonacci(n-1) + fibonacci(n-2));
}

The function above calculates the n'th Fibonacci number, recursively. All recursive functions have a "base case". The base cases here are n=0 and n=1. The base case does not recursively call itself, and thus acts as the terminating call. All other cases (non base cases) make a recursive call, until a base case is hit.

On a side note: this is a highly inefficient implementation of Fibonacci sequence computation (but a good recursion example).

 

[eLiu]

I think in all cases, recursion can be written in an iterative loop. Sometimes it's actually easier and/or faster (in running time and/or programming time) to do so. But other times it'll require a lot of work to unravel the recursion. In this case, switching to a loop is quite simple.

To help you understand this case, I would suggest doing the following... execute the program code by hand. There's only 4 numbers being added so it shouldn't be that hard. Draw a 'recursion tree': the root node will be the very first call to AddNumbers. Nodes of the tree represent function calls. In each node, you should list out the values taken by all the local variables so you can determine what is returned. Connect nodes with a branch where the function call occurs (i.e., addNumbers with 4 numbers in the list calls addNumbers with 3 numbers in the list).

Typically, you use recursion when solving a problem of size N involves solving smaller problems of "identical" structure. Any time you can apply induction, you can apply recursion--so you need 1) "identical" structure across different problem sizes; and 2) a set of base case(s). For example, in this case, the goal is to add N numbers together. Say I tell you I have an algorithm that can add N-1 numbers together & report the value in SUM. Can you use my algorithm to add N numbers together? Of course! return SUM + Nth number. What's the base case? Well if there are 0 numbers, the sum is 0.

The fibonnaci case works the same way. Fibonacci numbers are defined as f(n) = f(n-1) + f(n-2). The base case are f(0) = 0, f(1) = 1. So if I give you a function that can compute f(n-1) and f(n-2), you should be able to compute f(n) quite easily. Try drawing the recursion tree for this example (easily google-able if you get stuck). Looking at the recursion tree should help you figure out why recursion is such an expensive way of solving this problem.

Your question about why "runningTotal" isn't reset to 0 each time is a different matter. Each time you call a function, you can imagine that function setting up its own "scope". If it declares LOCAL variables, the value of those variables are local to the owning function. When the function's return statement executes, all these local values are lost. These local variables can be communicated to other parts of the program by copying their value or sending that data along or by passing a reference (a pointer to a location in memory). The latter method can be dangerous if the function returns and somewhere else, you still have reference(s) to its local variable(s).
So the key here is... (btw the text below gives away how to draw the recursion tree if you haven't thought that through, so try that first.)
return addNumbers(numberList) + runningTotal;
Say I call addNumbers with numberList = {2,3} (just 2 numbers in it). On the first call, addNumbers() sets its local copy of runningTotal = 3, removes the last entry of numberList, and calls:
return addNumbers({2}) + 3; (*)
On this second call, addNumbers() sets its local copy of runningTotal = 2, removes the last entry of numberList, and calls:
return addNumbers({empty}) + 2; (**)
On the third call to addNumbers will see that the list is empty, and return 0. Thus, the statement labeled (**) above resolves to:
return 0 + 2; (=2)
and the return of the call above it (labeled (*)) resolves to:
return 2 + 3; (=5)
and we're done.

Each function call gets its own, separate copy of runningTotal that has no bearing on the other calls' runningTotal value.

 

[dwell]

See this post.

 

[Merad]

Maybe try an even easier function to start with (this is just pseudocode because I'm posting from my phone):

void Countdown(int count)
{
  Print(count);
  PrintNewline();

  if (count > 0)
  {
    Countdown(count - 1);
  }
}

Do you understand whats going on there and why that works? If not, step through it in a debugger, watch the call stack and the value of count every time the function is called.

 

[PhatoseAlpha]

See this post.

Beautiful.

 

[Maximilian]

Aha i understand it now, I understood the concept of recursion, a method calling itself with a different value each time eventually resulting in a terminator condition that evaluates to true and it stops calling itself, similar to a while loop in a way. The missing piece of the puzzle was me not understanding that it was a bunch of return statements that give the final answer and no return statement actually ever executes until the terminator line in the recursive method is reached which is when the chain of returns begins and each return waiting on its answer gets its answer in turn, adds it to its instance of runningTotal then returns that. Thanks guys eLiu your explanation was a big help :thumbsup:

I drew a paint diagram to help me visualize whats going on

Every return statement is waiting on another return statement except the final one which gets an answer to return immediately, when they get their return they then execute and make a return themselves all the way back to the calling line which was System.out.println()

 

[iCyborg]

Its doing my head in, ive written a simple recursive program to add numbers in an ArrayList entirely by myself but the kicker is I don't fully understand why it works heh. I gather a new stack?? is created each time the method addNumbers calls for itself and it dosent finish the current stack until the last ones done....then it comes back and finishes them... i dunno its pretty hazy.

How does it add the numbers without resetting runningTotal to 0 each time? Why dosent it just return 0 when numberList has nothing left in it?

public static void main(String[] args)
{
List<Integer> numberList = new ArrayList<Integer>();
numberList.add(5);
numberList.add(10);
numberList.add(10);
numberList.add(3);
System.out.println(addNumbers(numberList));
}

public static int addNumbers(List<Integer> numberList)
{
Integer runningTotal = 0;
if (numberList.isEmpty())
{
return runningTotal;
}
else
{
runningTotal = runningTotal + numberList.remove(numberList.size()-1);
return addNumbers(numberList) + runningTotal;
}
}

Oh, boy. This goes to show how poor naming can completely confuse someone (me) at first sight.

Your runningTotal *is* reset to 0 at each call, it *does* return 0 when empty, and it only ever contains the last element removed. Its name is completely misleading, because it does not accumulate anything in it, there's no total, just a single value, it's the function call that has the "running total" to which you add the last element represented by your variable runningTotal.
You may just as well change:
runningTotal = runningTotal + numberList.remove(numberList.size()-1);
to
runningTotal = numberList.remove(numberList.size()-1);

Or even put it all into the same return line with some rearranging, assuming C# evaluates from left to right (so you first remove, before calling recursively).
You should call it lastElt or something.

 

[masteryoda34]

See this post.

Nicely played

 

[Markbnj]

Nicely played

Ha Ha!

 

[Net]

set a break point at Integer runningTotal = 0; and step through this:

	public static void main(String[] args) {
		List<Integer> numberList = new ArrayList<Integer>();
		numberList.add(10);
		numberList.add(3);
		System.out.println(addNumbers(numberList));
		
	}
	public static int addNumbers(List<Integer> numberList) {
		Integer runningTotal = 0;
		if (numberList.isEmpty()) {
			return runningTotal;
		} else {
			runningTotal = runningTotal
					+ numberList.remove(numberList.size() - 1);
			Integer value = addNumbers(numberList);
			System.out.println("value: " + value + " runningTotal: " + runningTotal);
			return value + runningTotal;
		}
	}

 

[Train]

Really helps to think of an actual FILO (First In Last Out) stack of all the returns, which is actually how the CPU keeps track of where it is in the code. Every time you call a function, it puts the current address on the stack, then goes to that function. Every time a function returns, it pops what ever is on top of the stack to know where to go back to. The CPU also pushes all local variables onto the stack as well.

 

[tatteredpotato]

NM i see I'm too late

 

[eLiu]

Aha i understand it now, ... Thanks guys eLiu your explanation was a big help :thumbsup:

Happy to help

Recursion is a super powerful tool. If you get into programming or algorithm design, you'll find tons of places to apply recursion, so it's best to get comfortable with it ASAP. And somewhere in there you'll have to figure out how to do it without recursion too--by managing the stack manually. Function calls are a bit overkill to track the program state info that you actually care about when performing recursive operations, but they're very convenient. From the diagram you drew, you should be able to see the stack-like structure there.