12 Replies - 3666 Views - Last Post: 28 April 2009 - 12:51 AM

#1 Rekmesh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 15-September 08

Understanding Recursion

Posted 17 March 2009 - 12:19 AM

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? :crazy:

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


Is This A Good Question/Topic? 0
  • +

Replies To: Understanding Recursion

#2 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Understanding Recursion

Posted 17 March 2009 - 02:39 AM

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


Was This Post Helpful? 0
  • +
  • -

#3 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5882
  • View blog
  • Posts: 12,761
  • Joined: 16-October 07

Re: Understanding Recursion

Posted 17 March 2009 - 04:43 AM

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

It may help, diagrams toward the end: http://www.dreaminco...wtopic63302.htm
Was This Post Helpful? 0
  • +
  • -

#4 Rekmesh  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 19
  • Joined: 15-September 08

Re: Understanding Recursion

Posted 17 March 2009 - 08:04 PM

thanks for the replies cfoley and baavgai :D

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 :crazy: Although drawing diagrams about the flow of recursive helps a bit.

I guess I'll get it eventually with a bit more work. :P
Was This Post Helpful? 0
  • +
  • -

#5 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Understanding Recursion

Posted 17 March 2009 - 08:07 PM

i don't really recommend writing the code iteratively first then recursively since recursion uses a completely different way of thinking..
Was This Post Helpful? 0
  • +
  • -

#6 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Understanding Recursion

Posted 17 March 2009 - 08:07 PM

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

Please vote in my poll, though I can't say I remember starting that thread. :P
Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Understanding Recursion

Posted 18 March 2009 - 01:35 AM

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.
Was This Post Helpful? 0
  • +
  • -

#8 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • Posts: 4,473
  • Joined: 24-October 08

Re: Understanding Recursion

Posted 18 March 2009 - 08:39 PM

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
Was This Post Helpful? 0
  • +
  • -

#9 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • Joined: 11-December 07

Re: Understanding Recursion

Posted 19 March 2009 - 11:45 AM

That's your prerogative. What would you recommend instead?
Was This Post Helpful? 0
  • +
  • -

#10 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5882
  • View blog
  • Posts: 12,761
  • Joined: 16-October 07

Re: Understanding Recursion

Posted 19 March 2009 - 12:50 PM

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. :P

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.
Was This Post Helpful? 0
  • +
  • -

#11 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2268
  • View blog
  • Posts: 9,482
  • Joined: 29-May 08

Re: Understanding Recursion

Posted 19 March 2009 - 12:57 PM

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.
Was This Post Helpful? 0
  • +
  • -

#12 thursdayniac  Icon User is offline

  • D.I.C Regular

Reputation: 6
  • View blog
  • Posts: 255
  • Joined: 26-April 09

Re: Understanding Recursion

Posted 27 April 2009 - 07:41 PM

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.
Was This Post Helpful? 0
  • +
  • -

#13 BlakeJustBlake  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 26
  • View blog
  • Posts: 441
  • Joined: 15-February 09

Re: Understanding Recursion

Posted 28 April 2009 - 12:51 AM

Recursion is like Recursion.

:D
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1