Jump to content

  • Log In with Google      Sign In   
  • 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.

  • You cannot reply to this topic
14 replies to this topic

#1 nitishk   Members   -  Reputation: 161

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

 

 



Sponsor:

#2 Juliean   GDNet+   -  Reputation: 2423

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)
	{
		//add to counter
		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...



#3 slicer4ever   Crossbones+   -  Reputation: 3467

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.

#4 nitishk   Members   -  Reputation: 161

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)
	{
		//add to counter
		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!



#5 nitishk   Members   -  Reputation: 161

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?



#6 superman3275   Crossbones+   -  Reputation: 2011

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 smile.png).

 

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 smile.png)!

 

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 smile.png).

 

Cheers smile.png!


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

I'm a game programmer and computer science ninja ph34r.png!

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:

hobohm.business@gmail.com

or Personal-Message me on here smile.png!


#7 nitishk   Members   -  Reputation: 161

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 smile.png).

 

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 smile.png)!

 

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 smile.png).

 

Cheers smile.png!

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



#8 nitishk   Members   -  Reputation: 161

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.


#9 superman3275   Crossbones+   -  Reputation: 2011

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 smile.png!


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

I'm a game programmer and computer science ninja ph34r.png!

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:

hobohm.business@gmail.com

or Personal-Message me on here smile.png!


#10 slicer4ever   Crossbones+   -  Reputation: 3467

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.

#11 superman3275   Crossbones+   -  Reputation: 2011

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 smile.png!)

 

(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 smile.png!


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

I'm a game programmer and computer science ninja ph34r.png!

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:

hobohm.business@gmail.com

or Personal-Message me on here smile.png!


#12 nitishk   Members   -  Reputation: 161

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 smile.png!)

 

(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 smile.png!

 

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



#13 superman3275   Crossbones+   -  Reputation: 2011

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 ph34r.png!

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:

hobohm.business@gmail.com

or Personal-Message me on here smile.png!


#14 Cornstalks   Crossbones+   -  Reputation: 6974

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 ]

#15 Yrjö P.   Crossbones+   -  Reputation: 1412

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
      return toonie_recursive(try_to_improve(c), tries+1)
 
// initial call
total_tries = toonie_recursive(initial_coins, 1)





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.



PARTNERS