• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
chosenkill6

Function Recursion

14 posts in this topic

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

 

 

0

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

2

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[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!

0

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.[/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?

0

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
1

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

0

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[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
0

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[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
0

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[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
1

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[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
2

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

0

Share this post


Link to post
Share on other sites

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

0

Share this post


Link to post
Share on other sites

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);
}
2

Share this post


Link to post
Share on other sites

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)
1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0