[Rekmesh]

Hello all,

I've been programming for quite a while and haven't had any problems except one: Recursion. I just don't know how to implement things using recursion. Whenever I get an assignment where I know recursion could solve a problem, I don't know how to go about doing it. Now I know what recursion is; method calling itself and having a base case and all that good stuff, but being able to actually solve a problem using it is not possible for me... I've tried thinking about recursion by visualizing as a stack of plates and that has helped for some simple problems. But even trying to reverse a string is difficult (I tried for an hour before I gave up and looked up the answer) and binary searches are out of the question. Maybe I'm thinking to hard or something...

I've looked around on the internet for tutorials on this subject but they have not helped.
Can anyone help me?

This post has been edited by Rekmesh: 17 March 2009 - 12:20 AM

[cfoley]

I can sympathise. Although I am able to write recursive code, it doesn't come naturally to me. I was originally a self-taught programmer and didn't really come up against recursion until I had been bashing out code for 9 or 10 years. If I start to write an algorithm, I'll write an iterative one by default unless someone asks me to write a recursive one.

Fortunately, most (I think all) algorithms can be implemented iteratively, just with more lines of code. On the upside, Iterative code tends to be more efficient and there's no chance of overloading the stack. (is that an issue these days?) Unless you need the marks in class, writing iterative code should never be a problem.

To take one of your examples, string reversal. I would always do this with a for loop. However, recursion uses the same logic as while loops, so I wrote some iterative code to reverse a string with a while loop. The thing is, that's a recursive algorithm, just written iteratively. Check out the proper recursive method below and see the similarities.

Maybe that step of writing code with a while loop first will help you see how to convert it to recursive code.

package bleh;

public class StringReversal {

	public static void main(String[] args) {
		String startString = "Dream in Code";
		System.out.println(iterativeReversal(startString));
		System.out.println(recursiveReversal(startString));
	}

	private static String iterativeReversal(String startString) {
		String reversed = "";
		while (startString.length() > 0) {
			reversed = startString.charAt(0) + reversed;
			startString = startString.substring(1);
		}
		return reversed;
	}

	private static String recursiveReversal(String startString) {
		if (startString.length() > 0) {
			return recursiveReversal(startString.substring(1)) + startString.charAt(0);
		} else {
			return "";
		}
	}

} // class String Reversal

[baavgai]

We had a fairly lengthy discussion on this a while back. I remember drawing pictures.

It may help, diagrams toward the end: http://www.dreaminco...wtopic63302.htm

[Rekmesh]

thanks for the replies cfoley and baavgai

Writing code iteratively before writing it recursively sounds like a good idea. I'll start trying that. Unfortunantly baav, the link didn't help me much Although drawing diagrams about the flow of recursive helps a bit.

I guess I'll get it eventually with a bit more work.

[mostyfriedman]

i don't really recommend writing the code iteratively first then recursively since recursion uses a completely different way of thinking..

[Tom9729]

http://www.dreaminco...mp;hl=recursive

Please vote in my poll, though I can't say I remember starting that thread.

[cfoley]

mostyfriedman, sure, if I'd written a string reversal method with a for loop, the recursive method would look a lot different. But because recursive logic is similar to while loops, I think writing your algorithm out using a while loop and then a recursive method could open your eyes to the types of things you can code recursively.

[mostyfriedman]

i kinda disagree, if you think in terms of loops when working on a recursive method then you will probably feel like pulling your hair out because both ways are different

[cfoley]

That's your prerogative. What would you recommend instead?

[baavgai]

Recursion is a trick. It allows you to dynamically allocate space ( the vars declared in the function ), maintain a local state, and easily terminate at a dead end. If it's just a loop, then it's either an exercise or you're waisting your time. There are a few things it's a good option for, like traversing trees. The problem is, those things can get real complex real quick. Recursion is ideal for game engines, the kind that consider lot's of different possibilities. ( Though, in practice, the big guys prune those trees with funky probability functions. )

I tried writing the Towers of Hanoi once as an iterative function. It can be done, the the recursive one is so much simpler.

Scanning a directory structure... this is pretty classic for recursion. I've used a stack for this, but a recursive implementation is always easier, in any language.

Strangely, two classic examples of recursion, the Fibonacci series and a power function, are really bad. I mean, they look pretty. They'll also suck up resources faster than a vampire on a bender. The iterative versions of these functions are nearly as simple and much more computer friendly.

I'd suggest writing a file finder. It's a good use of the methodology. Or any kind of unknown depth node traversal.

[AdamSpeight2008]

By Iteration

Private Sub StrRev_ForLoop(ByVal InString As String) As String
 Dim OutputStr As String=""
 For i As Integer=InString.length-1 To 0 Step -1
  OutputStr =OutputStr & Instring(i)
 Next i
Return Outputstr
End Function

And by recursion

Private Sub StrRev_Recursive(ByVal InString As String, ByVal Depth As Integer) As String
If Depth<0 Then Return ""
Return StrRev_Recursive(Instring,Depth-1) & InString(Depth)
End Function

It is better to use an iterative method where possible, as it doesn't use up the stack space (with the function call) and the compilers can optimize them.

[thursdayniac]

I dont have much of a problem with the mathematics of recursion... It's when I have to apply it in a computer program that it becomes difficult for me. I always had problems with understanding when the code under the function call was going to be executed. Taking assembly language and understanding how function calls are handled on the stack really helped me.

[BlakeJustBlake]

Recursion is like Recursion.