Question about recursive programming

Ok when you have two or more recursive calls right next to each other in a program (like the method below), what exactly happens?


This is a method I'm writing (in java) to find the largest possible sum in a number triangle. I think I need two recursive calls because there are 2 possible directions it could go at every row in the triangle.

I like recursive functions, when they are written well they are very elegant. Many times an iterative function would run faster though, but sometimes simplicity of code is more desirable and the recursive function is well worth it.

Anyway, this is a case where you can use a vastly simpler function to find the answer, so I assume that the point of this is to teach you about recursion. I find it funny that the lecturers when trying to teach you how to use recursion always use examples where you never would use it.

Let's start with a linked list. If you recall, a linked list contains a number of nodes, each pointing to the next. You can print out the contents of the list using a recursive function, which goes something like this (in pseudocode)



Now in this function it starts at the head of the list, prints the value of that node, and moves to the next node. In other words, it prints out the items of the list from the first item to the last. The interesting thing here is if you put the print statement after the recursive call, the values are printed in reverse order. It is important to understand why that is.

If the function first moves to the next node and only prints that node's value when that recursive call has ended, obviously the last node will be printed first, and so on. The important thing here is that if you move the print statement around the recursive call you change the order the node values are printed.

It is the same with a tree. Your function has two recursive calls, and it forms a tree. If you were to print out each node's value you would easily see the order the nodes are visited. In fact, this is the best way to understand what is going on.

Do that, at each step print the value of that cell. Once you have done that, try changing the location of the print statement. First put the print statement before both recursive calls and see the order of the nodes. Then put the print statement between the recursive calls and view it, and lastly put the print statement after the two recursive calls and view the order.

This is the absolute best way to see the behaviour of the recursion.

Incidentally, the order of the nodes in these three cases is called pre-order, in-order and post-order.

Actually, I spoke too fast. In a triangle of nodes, each having some numeric value, the recursive method is quite a good way to find the sum of the nodes, as good as any other method. There is no vastly simpler algorithm, a recursive function would be the simplest.

Now that I look at your function in more detail, I see you do print the value of every node, I missed that as I glanced over it. Anyhow, your function has a serious problem. By the 3rd row it starts counting some nodes twice. I assume that the triangle you are talking about looks something like this:

1
23
456

As it stands, it will visit 1245356 and you will notice that node 5 was visited twice. This is because in this tree, each row has only one more node than the previous row.

To correct this you would have to say that only on the last column in a row should the function run the second recursive call.

I think I have said enough at this point. You have the information you need.

Actually, I also see that you are calculating a very strange sum indeed. Since I am feeling kind, and it is so grossly wrong, I will give you a hint. Make the function return an int and sum the branches.