• Create Account

## Function Recursion

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

14 replies to this topic

### #1nitishk  Members

162
Like
0Likes
Like

Posted 09 April 2013 - 05:49 PM

I am really having a hard time wrapping my head around function recursion. Why use it when you can use loops many times, what are the advantages to it? Also, I am lost as to how to solve this recursion practice problem I am trying:

"Though the program below does not necessarily require recursive solutions, it is good practice to create recursive methods so that you learn to program them.

A child is looking for 4 toonies.  He starts by randomly pulling 4 coins out of a bag that he cannot see into.  He can exchange one coin at a time; that is, he can put one coin back into the bag and then pull out another one. He never keeps more than 4 coins.  The possible coins that he can pull out of the bag are a penny, a nickel, a dime, a quarter, a half-dollar piece, a loonie, or a toonie.  His goal is to end up with 4 toonies.

Write a program called RecursionCoin that makes use of a recursive method to help him reach his goal.  Keep track of how many attempts it takes to reach his goal. "

Thanks

### #2Juliean  GDNet+

6211
Like
2Likes
Like

Posted 09 April 2013 - 06:16 PM

I am really having a hard time wrapping my head around function recursion. Why use it when you can use loops many times, what are the advantages to it? Also, I am lost as to how to solve this recursion practice problem I am trying:

Recursion is e.g. used when like in your example, you don't now how often you have to perform a certain operation - it can be 10 times, it can be hundered times, and there is no way to calculate it. Of course you could write a loop in most cases, but recursion is sometimes way handier. Like for every programming device, there is a time to use it, and a time not to use it. You will learn to destinquish between them with experience.

Though I do not know what exactly the requirements of your example are (is this all you've got here?), it might go like this:


class RecursioCoins
{
//this is our toonie coin
const int toonie = 7;

void Start(void)
{
//initialize our coins
int coins[4];
for(int i = 0; i < 4; i++)
{
coins[i] = GetCoin();
}

//this is our turn counter
int countTurns = 0;
//start checking the coins
CheckCoins(coins, &countTurns);
}

//this is our recursive function
bool CheckCoins(int coins[4], int* countTurns)
{
countTurns += 1;
//check all four coins
for(int i = 0; i < 4; i++)
{
//we want to see if our coin is a toonie
if(coins[i] != toonie)
{
//if not, we want a new coin for this
coins[i] = GetCoin();
//then we start checking again => recursion!
CheckCoins(coins, countTurns);
}
}
}

int GetCoin(void)
{
//we want a random coin, treated as values between 0-6
return rand()%7;
}

}


Note that this is written as basic as possible - I don't even know if it compiles, I'm tired, going to sleep now. Hopefully, if it fails, you are going to be able to pull of the rest yourself...

### #3slicer4ever  GDNet+

6358
Like
3Likes
Like

Posted 09 April 2013 - 06:37 PM

nitishk, on 09 Apr 2013 - 19:53, said:
I am really having a hard time wrapping my head around function recursion. Why use it when you can use loops many times, what are the advantages to it? Also, I am lost as to how to solve this recursion practice problem I am trying:
"Though the program below does not necessarily require recursive solutions, it is good practice to create recursive methods so that you learn to program them.[/size]
A child is looking for 4 toonies. He starts by randomly pulling 4 coins out of a bag that he cannot see into. He can exchange one coin at a time; that is, he can put one coin back into the bag and then pull out another one. He never keeps more than 4 coins. The possible coins that he can pull out of the bag are a penny, a nickel, a dime, a quarter, a half-dollar piece, a loonie, or a toonie. His goal is to end up with 4 toonies.
Write a program called RecursionCoin that makes use of a recursive method to help him reach his goal. Keep track of how many attempts it takes to reach his goal.[/size] "

Thanks

That, in my opinion is a really bad problem to introduce recursion to.

also, if you use Juliean's solution(which is probably the solution i'd come up with(although their's a couple issues in his code that prevents it from compiling atm)), their's the tiniest of tiny chances that you could overflow the stack because you never actually get the required number of toonies, the odds are astronomically small, but that solution does open up such possibility's.

Your instructor should have presented tree based searching as an introduction to recursion, as this is where recursion is not only the best option, but is pratically the only option.

for example, say you had this tree structure:
(N = Node):
          N
/      |      \
N      N      N
/ \   / | \   / \
N N   N N N   N N
|    / \
N    N N
|
N

each node has x number of children, and each child can also have any number of children, how would you reliable iterate over all the nodes?

That is where recursion shines, however the problem you have imo is safer/faster to solve using loops rather than recursion.

edit: actually, as it is now, Juliean's solution will cause a crash since you can never pick a toonie(change the value of toonie to 6)

Edited by slicer4ever, 09 April 2013 - 06:42 PM.

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

### #4nitishk  Members

162
Like
0Likes
Like

Posted 09 April 2013 - 06:39 PM

I am really having a hard time wrapping my head around function recursion. Why use it when you can use loops many times, what are the advantages to it? Also, I am lost as to how to solve this recursion practice problem I am trying:

Recursion is e.g. used when like in your example, you don't now how often you have to perform a certain operation - it can be 10 times, it can be hundered times, and there is no way to calculate it. Of course you could write a loop in most cases, but recursion is sometimes way handier. Like for every programming device, there is a time to use it, and a time not to use it. You will learn to destinquish between them with experience.

Though I do not know what exactly the requirements of your example are (is this all you've got here?), it might go like this:


class RecursioCoins
{
//this is our toonie coin
const int toonie = 7;

void Start(void)
{
//initialize our coins
int coins[4];
for(int i = 0; i < 4; i++)
{
coins[i] = GetCoin();
}

//this is our turn counter
int countTurns = 0;
//start checking the coins
CheckCoins(coins, &countTurns);
}

//this is our recursive function
bool CheckCoins(int coins[4], int* countTurns)
{
countTurns += 1;
//check all four coins
for(int i = 0; i < 4; i++)
{
//we want to see if our coin is a toonie
if(coins[i] != toonie)
{
//if not, we want a new coin for this
coins[i] = GetCoin();
//then we start checking again => recursion!
CheckCoins(coins, countTurns);
}
}
}

int GetCoin(void)
{
//we want a random coin, treated as values between 0-6
return rand()%7;
}

}


Note that this is written as basic as possible - I don't even know if it compiles, I'm tired, going to sleep now. Hopefully, if it fails, you are going to be able to pull of the rest yourself...

Great! The code you posted is in C but I can port to Java easily. I actually understood the code because of your commenting, thanks!

### #5nitishk  Members

162
Like
0Likes
Like

Posted 09 April 2013 - 06:41 PM

nitishk, on 09 Apr 2013 - 19:53, said:
I am really having a hard time wrapping my head around function recursion. Why use it when you can use loops many times, what are the advantages to it? Also, I am lost as to how to solve this recursion practice problem I am trying:
"Though the program below does not necessarily require recursive solutions, it is good practice to create recursive methods so that you learn to program them.[/size]
A child is looking for 4 toonies. He starts by randomly pulling 4 coins out of a bag that he cannot see into. He can exchange one coin at a time; that is, he can put one coin back into the bag and then pull out another one. He never keeps more than 4 coins. The possible coins that he can pull out of the bag are a penny, a nickel, a dime, a quarter, a half-dollar piece, a loonie, or a toonie. His goal is to end up with 4 toonies.
Write a program called RecursionCoin that makes use of a recursive method to help him reach his goal. Keep track of how many attempts it takes to reach his goal.[/size] "

Thanks

That, in my opinion is a really bad problem to introduce recursion to.

also, if you use Juliean's solution(which is probably the solution i'd come up with), their's the tiniest of tiny chances that you could overflow the stack because you never actually get the required number of toonies, the odds are astronomically small, but that solution does open up such possibility's.

Your instructor should have presented tree based searching as an introduction to recursion, as this is where recursion is not only the best option, but is pratically the only option.

for example, say you had this tree structure:
(N = Node):
          N
/      |      \
N      N      N
/ \   / | \   / \
N N   N N N   N N
|    / \
N    N N
|
N

each node has x number of children, and each child can also have any number of children, how would you reliable iterate over all the nodes?

That is where recursion shines, however the problem you have can, and imo is safer/faster to solve using loops rather than recursion.

edit: actually, as it is now, Juliean's solution will cause a crash since you can never pick a toonie(change the value of toonie to 6)

The analogy you presented, the child can have more children, kind of confuses me. If I am using recursion, I am making another call to the method I am in, so does that not mean that I am simply going back and forth between 2 children?

### #6superman3275  Members

2061
Like
1Likes
Like

Posted 09 April 2013 - 06:49 PM

Considering that Juleian has described recursion, I'll describe loops.

Let's look at a Project Euler practice problem:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Okay, so we could use some recursion:

(Code is in JavaScript because JavaScript is basically universally easy to read for people who have a background in almost any standard programming language. That doesn't make it good, though ).

function findSmallestNumber(currentNumber, currentFunctionCall, amountOfFactors) {
if(currentFunctionCall > amountOfFactors) {
return currentNumber;
} else if (currentNumber % currentFunctionCall === 0) {
++currentFunctionCall;
return findSmallestNumber(currentNumber, currentFunctionCall, amountOfFactors);
} else if (currentNumber % currentFunctionCall !== 0) {
++currentNumber;
currentFunctionCall = 1;
return findSmallestNumber(currentNumber, currentFunctionCall, amountOfFactors);
}
}

var amountOfFactors;
do {
amountOfFactors = prompt("How many factors are there (0 - ?)");
} while (amountOfFactors.isNaN);

console.log(findSmallestNumber(1, 1, amountOfFactors));


(What's awesome about learning recursion is that this makes sense )!

So, I tested this with 1-10 and it worked. However, try it with 1-20 (This link will bring you to a page with my code. Click the "run" button to see it in action!) You should get the error "Too much recursion". The compiler can't handle 25,000,000 function calls (I solved the code euler problem, obviously, so yeah, there's that many). So, we have to translate it into loops:

function findSmallestNumber(amountOfFactors) {
var currentNumber = 1;
var currentFactor = 1;

while(currentFactor <= amountOfFactors) {
if(currentNumber % currentFactor === 0) {
++currentFactor;
continue;
} else if(currentNumber % currentFactor !== 0) {
++currentNumber;
currentFactor = 1;
continue;
}
}

return currentNumber;
}

var amountOfFactors = 0;
do {
amountOfFactors = prompt("How many factors (1 - ?)", "");
} while (amountOfFactors.isNaN);

console.log(findSmallestNumber(amountOfFactors));


This is the same function, using loops. We see that it works the same, however it will work for an (almost) infinite amount of number.

(One more thing, don't try the script using a while() loop with the value "20". It will cause your browser to freeze because Javascript really isn't meant for this Because it's an interpreted language and was created for changing HTML / CSS with minor logic ).

Cheers !

Edited by superman3275, 09 April 2013 - 06:56 PM.

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

or Personal-Message me on here !

### #7nitishk  Members

162
Like
0Likes
Like

Posted 09 April 2013 - 06:53 PM

Considering that Juleian has described recursion, I'll describe loops.

Let's look at a Project Euler practice problem:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Okay, so we could use some recursion:

(Code is in JavaScript because JavaScript is basically universally easy to read for people who have a background in almost any standard programming language. That doesn't make it good, though ).

function findSmallestNumber(currentNumber, currentFunctionCall, amountOfFactors) {
if(currentFunctionCall > amountOfFactors) {
return currentNumber;
} else if (currentNumber % currentFunctionCall === 0) {
++currentFunctionCall;
return findSmallestNumber(currentNumber, currentFunctionCall, amountOfFactors);
} else if (currentNumber % currentFunctionCall !== 0) {
++currentNumber;
currentFunctionCall = 1;
return findSmallestNumber(currentNumber, currentFunctionCall, amountOfFactors);
}
}

var amountOfFactors;
do {
amountOfFactors = prompt("How many factors are there (0 - ?)");
} while (amountOfFactors.isNaN);

console.log(findSmallestNumber(1, 1, amountOfFactors));


(What's awesome about learning recursion is that this makes sense )!

So, I tested this with 1-10 and it worked. However, try it with 1-20 (This link will bring you to a page with my code. Click the "run" button to see it in action!) You should get the error "Too much recursion". The compiler can't handle 25,000,000 function calls (I solved the code euler problem, obviously, so yeah, there's that many). So, we have to translate it into loops:

function findSmallestNumber(amountOfFactors) {
var currentNumber = 1;
var currentFactor = 1;

while(currentFactor <= amountOfFactors) {
if(currentNumber % currentFactor === 0) {
++currentFactor;
continue;
} else if(currentNumber % currentFactor !== 0) {
++currentNumber;
currentFactor = 1;
continue;
}
}

return currentNumber;
}

var amountOfFactors = 0;
do {
amountOfFactors = prompt("How many factors (1 - ?)", "");
} while (amountOfFactors.isNaN);

console.log(findSmallestNumber(amountOfFactors));


This is the same function, using loops. We see that it works the same, however it will work for an (almost) infinite amount of number.

(One more thing, don't try the script using a while() loop with the value "20". It will cause your browser to freeze because Javascript really isn't meant for this Because it's an interpreted language and it's not actually that useful ).

Cheers !

Ah that makes sense! I think that is where I was struggling, failing to understand when to use which. Thanks for clearing that up

### #8nitishk  Members

162
Like
0Likes
Like

Posted 09 April 2013 - 06:55 PM

package mainPackage;

public class RecursionCoin {

final static int toonie = 6;

static int[] coin = {0,0,0,0};
static int turns = 0;

public static void main(String[] args) {
for(int i = 0; i < 4; i++){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
}
checkCoins(coin, turns);
System.out.println(turns);
}

private static void checkCoins(int[] coin, int turns2) {
turns = turns2 + 1;

for(int i = 0; i < 4; i++){
if(coin[i] != toonie){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
checkCoins(coin, turns);
}
}
}
}



I am going to try a few more problems on my own now just to make sure I fully understand this.
Can someone just skim through my code, see if this makes sense?

Thanks!

Edited by nitishk, 09 April 2013 - 06:56 PM.

### #9superman3275  Members

2061
Like
0Likes
Like

Posted 09 April 2013 - 07:02 PM

package mainPackage;

public class RecursionCoin {

final static int toonie = 6;

static int[] coin = {0,0,0,0};
static int turns = 0;

public static void main(String[] args) {
for(int i = 0; i < 4; i++){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
}
checkCoins(coin, turns);
System.out.println(turns);
}

private static void checkCoins(int[] coin, int turns2) {
turns = turns2 + 1;

for(int i = 0; i < 4; i++){
if(coin[i] != toonie){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
checkCoins(coin, turns);
}
}
}
}



I am going to try a few more problems on my own now just to make sure I fully understand this.
Can someone just skim through my code, see if this makes sense?

Thanks!

The parameters you pass in to different functions don't interfere with each other, look at java scope. So your "turns2" variable in checkCoins() can simply be "turns". When you pass in an array to a function, it's not a reference to an array, it's a copy. So you're never actually changing the coin array. This means you can never actually access the coin when it contains four toonies.

What if you wanted to do some more work with the array, and you expect it to contain the four toonies? You need to consider things like this so that in the future, if you're ever working on this again, you don't have to go back and change your already working code.

Cheers !

Edited by superman3275, 09 April 2013 - 07:03 PM.

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

or Personal-Message me on here !

### #10slicer4ever  GDNet+

6358
Like
1Likes
Like

Posted 09 April 2013 - 07:04 PM

...snip...

The analogy you presented, the child can have more children, kind of confuses me. If I am using recursion, I am making another call to the method I am in, so does that not mean that I am simply going back and forth between 2 children?

The recursive function operates on each node, which calls the recursive function on all it's children, i.e:
if we
  void Func(Node N){
for(int i=0;i<N.Children.Count;i++) Func(N.Children[i]);
return;
}

which allows you to operate on an indeterminable number of children.

package mainPackage;

public class RecursionCoin {

final static int toonie = 6;

static int[] coin = {0,0,0,0};
static int turns = 0;

public static void main(String[] args) {
for(int i = 0; i < 4; i++){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
}
checkCoins(coin, turns);
System.out.println(turns);
}

private static void checkCoins(int[] coin, int turns2) {
turns = turns2 + 1;

for(int i = 0; i < 4; i++){
if(coin[i] != toonie){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
return checkCoins(coin, turns); //Once this function returns succesfully, you know that you are done.
//returning here allows all your recursive functions to escape, instead of each doing potentially more work.
}
}
}
}



Made a small change for doing unnecessary work.

Edited by slicer4ever, 09 April 2013 - 07:06 PM.

Check out https://www.facebook.com/LiquidGames for some great games made by me on the Playstation Mobile market.

### #11superman3275  Members

2061
Like
2Likes
Like

Posted 09 April 2013 - 07:11 PM

...snip...

The analogy you presented, the child can have more children, kind of confuses me. If I am using recursion, I am making another call to the method I am in, so does that not mean that I am simply going back and forth between 2 children?

The recursive function operates on each node, which calls the recursive function on all it's children, i.e:
if we
  void Func(Node N){
for(int i=0;i<N.Children.Count;i++) Func(N.Children[i]);
return;
}

which allows you to operate on an indeterminable number of children.

>>>

package mainPackage;

public class RecursionCoin {

final static int toonie = 6;

static int[] coin = {0,0,0,0};
static int turns = 0;

public static void main(String[] args) {
for(int i = 0; i < 4; i++){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
}
checkCoins(coin, turns);
System.out.println(turns);
}

private static void checkCoins(int[] coin, int turns2) {
turns = turns2 + 1;

for(int i = 0; i < 4; i++){
if(coin[i] != toonie){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
return checkCoins(coin, turns); //Once this function returns succesfully, you know that you are done.
//returning here allows all your recursive functions to escape, instead of each doing potentially more work.
}
}
}
}


Made a small change for doing unnecessary work.

That code has a side effect. You're returning a void method? What is the point of that. What you should do is say that once it returns successfully, you break out of the loop:

checkCoins:
for(int i = 0; i < 4; i++) {
if(coin[i] != toonie) {
coin[i] = (int) (Math.random() * ((6-0) + 1));
return checkCoins(coin, turns);
break checkCoins;
}
}


This is a labeled break statment.

Once it returns successfully, you break out and avoid a side-effect of the method.

(Yes, I know it's an unimportant side effect that doesn't actually affect anything, however consistency !)

(I just want to point out that there are some non-elegant pieces of your code, such as using an int assigned to a random number to toonie. You could create a class with an state called isToonie

class Coin {
bool isToonie = false;
}


and then have your code make more sense (instead of: if (coin[i] != toonie), we get: if (coins[index].isToonie))).

Cheers !

Edited by superman3275, 09 April 2013 - 07:22 PM.

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

or Personal-Message me on here !

### #12nitishk  Members

162
Like
0Likes
Like

Posted 09 April 2013 - 07:16 PM

...snip...

The analogy you presented, the child can have more children, kind of confuses me. If I am using recursion, I am making another call to the method I am in, so does that not mean that I am simply going back and forth between 2 children?

The recursive function operates on each node, which calls the recursive function on all it's children, i.e:
if we
  void Func(Node N){
for(int i=0;i<N.Children.Count;i++) Func(N.Children[i]);
return;
}

which allows you to operate on an indeterminable number of children.

package mainPackage;

public class RecursionCoin {

final static int toonie = 6;

static int[] coin = {0,0,0,0};
static int turns = 0;

public static void main(String[] args) {
for(int i = 0; i < 4; i++){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
}
checkCoins(coin, turns);
System.out.println(turns);
}

private static void checkCoins(int[] coin, int turns2) {
turns = turns2 + 1;

for(int i = 0; i < 4; i++){
if(coin[i] != toonie){
coin[i] = 0 + (int)(Math.random() * ((6 - 0) + 1));
return checkCoins(coin, turns); //Once this function returns succesfully, you know that you are done.
//returning here allows all your recursive functions to escape, instead of each doing potentially more work.
}
}
}
}


Made a small change for doing unnecessary work.

That code has a side effect. You're returning a void method? What is the point of that. What you should do is say that once it returns successfully, you break out of the loop:

if (coin[i] != toonie) {
coin[i] = 0 + (int) (Math.random() * ((6 - 0) + 1));
checkCoins(coin, turns);
break;
}


Once it returns successfully, you break out and avoid a side-effect of the method.

(Yes, I know it's an unimportant side effect that doesn't actually affect anything, however consistency !)

(I just want to point out that there are some non-elegant pieces of your code, such as using an int assigned to a random number to toonie. You could create a class with an state called isToonie

class Coin {
bool isToonie = false;
}


and then have your code make more sense (instead of: if (coin[i] != toonie), we get: if (coins[index].isToonie))).

Cheers !

Thanks for the pointers!
Fixed my code, works like a charm

### #13superman3275  Members

2061
Like
0Likes
Like

Posted 09 April 2013 - 07:26 PM

Also, it's smarter to use loops for this, considering that it can overflow the stack (as mentioned by slicer4ever).

I'm a game programmer and computer science ninja !

Here's my 2D RPG-Ish Platformer Programmed in Python + Pygame, with a Custom Level Editor and Rendering System!

Here's my Custom IDE / Debugger Programmed in Pure Python and Designed from the Ground Up for Programming Education!

Want to ask about Python, Flask, wxPython, Pygame, C++, HTML5, CSS3, Javascript, jQuery, C++, Vimscript, SFML 1.6 / 2.0, or anything else? Recruiting for a game development team and need a passionate programmer? Just want to talk about programming? Email me here:

or Personal-Message me on here !

### #14Cornstalks  Members

7026
Like
2Likes
Like

Posted 09 April 2013 - 07:39 PM

I'll try and talk about why recursion is useful. The most obvious is that it can greatly simplify problems. For example, consider the following: what if you had a binary tree (not sorted), and you wanted to find out if a certain value is in that tree? The simplest code I can think of to do that is using recursion, not loops. I'll post some sample code that uses recursion to search a binary tree for a particular value. Notice it's pretty simple, short, and easy to follow and understand (hopefully). Now try seeing if you can write the equivalent using loops (in just 3 lines of code, like my recursive search... that should show you why recursion is nice):


// Just for reference, this is the kind of data structure I'm assuming
struct BinaryTree
{
struct Node
{
Node* left;
Node* right;
int value;
};

Node root;
};

// Basically, this is a recursive depth first search
bool find(int value, const BinaryTree::Node* root)
{
if (root == NULL) return false;

if (root->value == value) return true;

return find(value, root->left) || find(value, root->right);
}


[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

### #15Yrjö P.  Members

1416
Like
1Likes
Like

Posted 09 April 2013 - 08:02 PM

Can someone just skim through my code, see if this makes sense?

The point of using recursion on something like this is usually being able to write readable, concise and safe code. Your code, unfortunately, is a bit of a mess due to how it uses shared state (the static variables outside the functions). When it does the recursive function call, that's pretty much a replacement for a goto. The result is uglier than a normal iterative solution, never mind a recursive one.

Here's a recursive solution without external state. (This is Scala code, but I'm hoping it's about as easy to read as pseudocode. I omitted some trivial code.)

// takes a collection of four coins as an argument, exchanges one non-toonie coin, returns the new set of four coins
def try_to_improve(Coins c): Coins = ...

// tests whether all coins in the collection are toonies
def all_toonies(Coins c): Boolean = ...

// recursive func
def toonie_recursive(Coins c, Int tries): Int =
if (all_toonies(c))
return tries
else
total_tries = toonie_recursive(initial_coins, 1)