Jump to content
  • Advertisement
Sign in to follow this  
chosenkill6

Function Recursion

This topic is 1923 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

 

 

Share this post


Link to post
Share on other sites
Advertisement

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 = 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 != toonie)
			{
				//if not, we want a new coin for this
				coins = 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...

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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 = 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 != toonie)
			{
				//if not, we want a new coin for this
				coins = 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!

Share this post


Link to post
Share on other sites

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

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?

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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 = 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 != toonie){
				coin = 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

Share this post


Link to post
Share on other sites

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 = 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 != toonie){
				coin = 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

Share this post


Link to post
Share on other sites


...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);
    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 = 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 != toonie){
				coin = 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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!