Programming Recursion

Comprox · January 2005

Ok, I am trying to understand recursion, I have seen it on and off for a few years, but it still makes no sense to me.

In an attempt to understand it more, I'm doing some practice problems, one to calculate factorials (ie. 5!) and one to reverse strings of text in preparation for a forthcoming exam. I got the factorial one after some work, but am totally stumped on the string one. What is supposed to happen is it converts 'hello' to 'olleh' using recursion and substring calls, but I've gotten everything from 'ooooo' to 'eeehhhlllllllloooo'. Could anyone maybe get me off on the right foot here with some suggestions?

JHunz · January 2005

Basically what you want to do in this problem is write a function that takes the first letter of the string, makes a recursive call to itself with the string minus that letter, then adds that letter on the end of the result.

You should be able to figure it out from that.

[Edit]: From an implementation standpoint I believe it's easier to take the letter off the end rather than the beginning

Snidely · January 2005

I know recursion is the same idea for most languages, but it would help if you specified. C++? Java? Prolog?

I may have an old Java prog that does the string thing.

Comprox · January 2005

Jhunz approval++;

thanks <img src='http://www.unknownworlds.com/forums/html/emoticons/biggrin-fix.gif' border='0' style='vertical-align:middle' alt='biggrin-fix.gif' />

Thansal · January 2005

hehe, recursion, one of the greatest things on earth, and confusing as hell untill it finaly snaps for yah.

I learned it via doing a bubble sort in asembly language.

probably an easy way (though not %100 correct) to think about it is a string of commands, one of those commands being a GOTO 1 (bad programing, I know, but that is how I learned it)

It also dosn't have to be the last step, so often a good part of the recursion happens as you are steping out of the loop (so you do a string of actions as you step in, and then once the recursion is done you perform a different set of actions, in reverse order to the data)

NumbersNotFound · January 2005

The way i think about it is through a tree of sorts:

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>CODE</b> </td></tr><tr><td id='CODE'>

First we have all of the function calls. This means that whenever a piece of data needs further action, it calls itself.
factorial(5); Subtract1, send to itself.
|4
|_Factorial(4); Subtract1, send to itself.
|3
|_Factorial(3); Subtract1, send to itself.
|3
|_Factorial(2); Subtract1, send to itself.
|2
|_Factorial(1); STOP. This means that no further calls are needed. HERE is where the computation actually starts happening and numbers are returned rather than sent.

Now collapse the functions as such, working from bottom to top:

Return 24*5=96;
|
|_Return 6*4=24;
|
|_Return 2*3=6;
|
|_Return 1*2=2; (Based on the statement Return number*Factorial(number-1))
|
|_Return 1;
</td></tr></table><div class='postcolor'>

Recursion. Adj. Recursion.

(I may have messed up somewhere.)

Marik_Steele · January 2005

For once, <a href='http://bash.org/?444349' target='_blank'>a specific Bash.org quote</a> is both inoffensive <i>and</i> relevant!
</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Gentlemen... welcome to recursion club. The first rule is: you do not talk about recursion club. The next rule is: see first rule.</td></tr></table><div class='postcolor'>

Umbraed_Monkey · January 2005

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (Marik Steele @ Jan 19 2005, 06:06 PM)</td></tr><tr><td id='QUOTE'> For once, <a href='http://bash.org/?444349' target='_blank'>a specific Bash.org quote</a> is both inoffensive <i>and</i> relevant!
</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Gentlemen... welcome to recursion club. The first rule is: you do not talk about recursion club. The next rule is: see first rule.</td></tr></table><div class='postcolor'>  </td></tr></table><div class='postcolor'> 
As much as I enjoyed that as well, thats not a recursion.

(I dont wanna be an arse, but this may confuse people.)

[WHO]Them · January 2005

Remember, the stack is not a plaything.

funbags · January 2005

So who here knows C++ really well? I mean, enough to program for say...a half life 2 mod?

DOOManiac · January 2005

Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>Recursion is all about</td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'>

Hehe. Sorry, couldn't resist. :P

SoulSkorpion · January 2005

</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> (DOOManiac @ Jan 21 2005, 01:09 PM)</td></tr><tr><td id='QUOTE'>Hehe. Sorry, couldn't resist. <img src='http://www.unknownworlds.com/forums/html/emoticons/tounge.gif' border='0' style='vertical-align:middle' alt='tounge.gif' /></td></tr></table><div class='postcolor'>
You need a base case, otherwise it defeats the whole point of using recursion (unless your point is to crash the machine, of course).

Like a-this:

I think that</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think that</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think that</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think that </div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think that</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think that</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think that</div><table border='0' align='center' width='95%' cellpadding='3' cellspacing='1'><tr><td><b>QUOTE</b> </td></tr><tr><td id='QUOTE'>I think, therefore I am.</td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'></td></tr></table><div class='postcolor'>

Programming Recursion

Comments