## Programs that Require the Use of Recursion

In the factorial function and the greatest common divisor function that we just looked at, there is no good reason to use a recursive program since the result can easily be achieved, taking up less memory, using

However, some problems are not easily solved using iteration and are better suited to a

Two of these problems will now be discussed.

In the

On peg

*iteration*.However, some problems are not easily solved using iteration and are better suited to a

**recursion solution**.Two of these problems will now be discussed.

- Tower of Hanoi
- Word Scramble

**Tower of Hanoi**In the

**Tower of Hanoi**, there are three pegs:**A**,**B**, and**C**.On peg

**A**, there are a number of discs,*1*to*n*,*1*being the smallest and*n*being the biggest. The discs are placed on peg**A**in decreasing order of size from bottom to top. Disc*n*, the largest, is at the bottom; disc*1*, the smallest, is at the top.The objective is to move all

To become familiar with this problem, find a website that will allow you to try to solve the Tower of Hanoi problem. Check out this website to start:

Tower of Hanoi

IF

ELSE

Move (n-1) discs to the

Move disc

Move (n-1) discs to the

Trace through the code shown above, and determine what output will be displayed as a result of the execution of this code.

A

NUF NFU UNF UFN FNU FUN

IF the length of the string is 1, then print the word

ELSE

For each character in the string, use the character as the first letter in the word and build another word from the remaining letters.

*n*discs from peg**A**to peg**C**(using, if required, the “temporary peg,” peg**B**) subject to the following conditions:- Only one disc, the top disc on any peg, can be moved at a time.
- A larger disc cannot be placed on top of a smaller disc.

To become familiar with this problem, find a website that will allow you to try to solve the Tower of Hanoi problem. Check out this website to start:

Tower of Hanoi

**Recursive Algorithm to Solve this Problem****Note:***n*represents the number of discs.IF

*n*is*1*, move disc*1**to*the**peg (C in above example) from the***to***peg (A in above example).***from*ELSE

Move (n-1) discs to the

**peg (B in above example) from the***temporary***peg using the***from***peg***to*Move disc

*n*to the**peg from the***to***peg***from*Move (n-1) discs to the

**peg from the***to***peg using the***temporary***peg***from***Code to Solve this Problem****public static void main(String[] args)****{****int n = 8;****String fromPeg = "A";****String toPeg = "C";****String tempPeg = "B";****System.out.println("Towers of Hanoi problem");****System.out.println("There are " + n + " discs on peg A initially ");****hanoi (fromPeg, toPeg, tempPeg, n);****}****public****static****void hanoi (String from, String to, String temp, int n)****{****if (n ==1)****{****System.out.println("Move disc 1 from " + from + " to " + to);****} else****{****hanoi (from, temp, to, n-1);****System.out.println("Move disc " + n + " from " + from + " to " + to);****hanoi (temp, to, from, n-1);****}****}**Trace through the code shown above, and determine what output will be displayed as a result of the execution of this code.

**Word Scramble**A

**Word Scramble**consists of a group of scrambled letters; for example, the scrambled letters NUF, when unscrambled, form the following “words”:NUF NFU UNF UFN FNU FUN

**Recursive Algorithm to Solve this Problem**IF the length of the string is 1, then print the word

ELSE

For each character in the string, use the character as the first letter in the word and build another word from the remaining letters.

**Code to Solve this Problem****public static void main(String[] args)****{****String letters = "NUF";****System.out.println("Word Scramble \n");****scrambleWords(letters, "");****}****public****static void scrambleWords (String word, String scrambledLetters)****{****String remainingLetters;****String origWord = word;****String origscrambledLetters = scrambledLetters;****if (word.length() == 1)****{****System.out.println(scrambledLetters + word);****} else****{****for (int pos = 0; pos <origWord.length(); pos++)****{****remainingLetters = origWord.substring(0, pos) + origWord.substring(pos+1, origWord.length());****scrambleWords(remainingLetters, origscrambledLetters + origWord.charAt(pos));****}****}****}**## Mr. Spok's Dilemma(choosing k out of n things)

The Enterprise is nearing the end of its 5 year mission to explore new worlds but has just stumbled upon an unexplored solar system that contains n planets. Unfortunately, they only have time to visit k of these planets. Mr. Spok begins to ponder how many different choices are possible for exploring these planets and because time is short, he doesn't care which order they visit the planets either. How many different combinations of k planets can the Enterprise visit?

Mr. Spok is really interested in visiting Planet X so he starts to think about how to picks planets in terms of Planet X. He begins to realise that there are 2 possibilities: we visit Planet X or we don't visit Planet X. If they visit Planet X, then they will have to choose k-1 other planets to visit out of the remaining n-1 planets left. On the other hand, if they don't visit Planet X, then they will have to choose k planets to visit with the n-1 planets still left. This is a good start to our recursive solution.

To determine all of the possible ways to visit the k planets, the solutions becomes numVisits(n, k) = (the number of groups of k planets including Planet X) +

(the number of groups of k planets not including Planet X). But, we already thought of how this looks in terms of n and k. Thus our recursive definition is:

numVisits(n, k) = numVisits(n-1, k-1) + numVisits(n-1, k)

Now we have to make sure that we stop at some point in time. We need a base case! Mr. Spok starts to think of answers to this problem he already knows. He immediately realizes that if there are n planets and the number of planets they want to visit is also n (i.e. k=n), there is only 1 way to visit this group. You visit every planet! Though it seems silly, there is also one other base case we need to deal with. If they don't have time to visit any of the planets (i.e. k=0), there is also 1 way to visit this group, we don't see any of them. Also, in the event that k > n, we have made a mistake and the solution is 0. There is no way to visit more planets than we have in our list to choose from.

We now have a solution we can program:

Mr. Spok is really interested in visiting Planet X so he starts to think about how to picks planets in terms of Planet X. He begins to realise that there are 2 possibilities: we visit Planet X or we don't visit Planet X. If they visit Planet X, then they will have to choose k-1 other planets to visit out of the remaining n-1 planets left. On the other hand, if they don't visit Planet X, then they will have to choose k planets to visit with the n-1 planets still left. This is a good start to our recursive solution.

To determine all of the possible ways to visit the k planets, the solutions becomes numVisits(n, k) = (the number of groups of k planets including Planet X) +

(the number of groups of k planets not including Planet X). But, we already thought of how this looks in terms of n and k. Thus our recursive definition is:

numVisits(n, k) = numVisits(n-1, k-1) + numVisits(n-1, k)

Now we have to make sure that we stop at some point in time. We need a base case! Mr. Spok starts to think of answers to this problem he already knows. He immediately realizes that if there are n planets and the number of planets they want to visit is also n (i.e. k=n), there is only 1 way to visit this group. You visit every planet! Though it seems silly, there is also one other base case we need to deal with. If they don't have time to visit any of the planets (i.e. k=0), there is also 1 way to visit this group, we don't see any of them. Also, in the event that k > n, we have made a mistake and the solution is 0. There is no way to visit more planets than we have in our list to choose from.

We now have a solution we can program:

**public static int numPlanets(int n, int k)**

{

if(k == 0 || n == k)

{{

if(k == 0 || n == k)

{

**return 1;****}else if(k > n)****{****return 0;****}****return numPlanets(n - 1, k - 1) + numPlanets(n - 1, k)**

}}

## Final Thoughts on Recursion

**Recursive functions**are common in Computer Science, because they allow programmers to write efficient programs using a minimal amount of code. The downside is that they can create

*infinite loops*, which can cause the program to crash, or worse yet, hang the entire computer system.

*Recursion should be used with a function that has a small number or NO parameters*, since the recursion places a new occurrence of the function on the stack, along with those variables. It is quite possible for a function to recall itself upwards of thousands of times. Therefore, you could easily run out of memory in the stack when running your recursive program.