Coding Bat Recursive Problems – Day 1

Today, we are looking at a primer for recursion using problems in CodingBat in Computer Science 2. We looked at 3 different problems from CodingBat.

Bunny Ears

http://codingbat.com/prob/p183649

Here is the setup of the problem:

We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

public int bunnyEars(int bunnies) {
  if (bunnies == 0){
    return 0;
  } else {
    return 2 + bunnyEars(bunnies-1);
  }
}

Let’s use an input of 6. With this, we would anticipate the output to be 12, since each bunny has 2 ears.

Line 3 will not be run since the condition set in line 2 is FALSE. Currently, bunnies is set to 6.

So, we move on to line 4, which is the start of the default case, and is executed on line 5. So with bunnies set to 6, we return a 2 and then add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #5.

Now, bunnies = 5, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #4.

Now, bunnies = 4, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #3.

Now, bunnies = 3, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #2.

Now, bunnies = 2, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #1.

Now, bunnies = 1, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is 0.

Now, bunnies = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

  • 0 from when bunnies = 0 (cumulative total = 0)
  • 2 from when bunnies = 1 (cumulative total = 2)
  • 2 from when bunnies = 2 (cumulative total = 4)
  • 2 from when bunnies = 3 (cumulative total = 6)
  • 2 from when bunnies = 4 (cumulative total = 8)
  • 2 from when bunnies = 5 (cumulative total = 10)
  • 2 from when bunnies = 6 (cumulative total = 12)

The total is returned as 12 ears.

Bunny Ears 2

http://codingbat.com/prob/p107330

Here is the setup of the problem:

We have bunnies standing in a line, numbered 1, 2, … The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we’ll say have 3 ears, because they each have a raised foot. Recursively return the number of “ears” in the bunny line 1, 2, … n (without loops or multiplication).

public int bunnyEars2(int bunnies) {
  if (bunnies == 0){
    return 0;
  } else if (bunnies % 2 != 0){
    return 2 + bunnyEars2(bunnies-1);
  } else{
    return 3 + bunnyEars2(bunnies-1);
  }
}

For this one, let’s use an input of 5. We would expect the output to be 12 since bunnies 1, 3, & 5 have a total 6 ears and bunnies 2 & 4 have a total of 6 ears.

Line 3 will not be run since the condition set in line 2 is FALSE. Currently, bunnies is set to 5.

So, we move on to line 4. This condition is looking to see if we are working with an even numbered or odd numbered bunny. We have set the condition to use the modulus of 2 of the integer of bunnies. If the modulus is NOT 0, then the statement is TRUE and therefore it is an ODD numbered bunny.

Line 6 is the start of the default case which is used if we are working with an EVEN numbered bunny.

Now, bunnies = 5, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #4.

Now, bunnies = 4, so line 2 is FALSE, line 4 is FALSE, so we run the default case at line 6. We return a 3 and add that to the number of bunny ears from the next bunny (bunnies -1), which is bunny #3.

Now, bunnies = 3, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #2.

Now, bunnies = 2, so line 2 is FALSE, line 4 is FALSE, so we run the default case at line 6. We return a 3 and add that to the number of bunny ears from the next bunny (bunnies -1), which is bunny #1.

Now, bunnies = 1, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is 0.

Now, bunnies = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

  • 0 from when bunnies = 0 (cumulative total = 0)
  • 2 from when bunnies = 1 (cumulative total = 2)
  • 3 from when bunnies = 2 (cumulative total = 5)
  • 2 from when bunnies = 3 (cumulative total = 2)
  • 3 from when bunnies = 4 (cumulative total = 10)
  • 2 from when bunnies = 5 (cumulative total = 12)

The total is returned as 12 ears.

Triangle

http://codingbat.com/prob/p194781

Here is the setup of the problem:

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

public int triangle(int rows) {
 if (rows == 0){
   return 0;
 } else {
   return rows + triangle(rows - 1);
 }
}

Here, we are building something that looks like this:

Like the cases before it, line 2 is a condition looking for when we are to row 0. If line 2 is FALSE, we will move to line 4. For this example, let’s use rows = 4. With this, the output should be 10 as there are 10 cubes needed to complete a 4 row triangle.

So, we start with rows = 4. Line 2 is FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #3.

We are returning the row number as that is equal to the number of cubes of each row (e.g. row 7 = 7 cubes, row 4 = 4 cubes, etc…).

We now move to rows = 3. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #2.

We now move to rows = 2. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #1.

We now move to rows = 1. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is 0.

Now, rows = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

  • 0 from when rows = 0 (cumulative total = 0)
  • 1 from when rows = 1 (cumulative total = 1)
  • 2 from when rows = 2 (cumulative total = 3)
  • 3 from when rows = 3 (cumulative total = 6)
  • 4 from when rows = 4 (cumulative total = 10)

Python Recursion and Factorial

As the final Computer Science lesson of the 2016/2017 academic year, I reviewed the somewhat concept of recursion in the Python programming language. In this review, I used the mathematical concept of factorial to discuss recursion.

#Program Name: Recursion Sample
#Programmer Name: Eric Evans, M.Ed.
#Program Description: Provide a functional example of a recursion problem in Computer Science using the mathematical concept of factorial.
#
#Define function named factorial which will have an input value of n.
def factorial(n):
    print("Factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        result = n * factorial(n-1)
        print(n,"! = ",result)
        return result
#Output the function factorial with an input value of 4.
print(factorial(4))

Let’s pull this concept apart line-by-line.

Lines 1 through 5 and line 14 are comment lines and have no real bearing on the program. They simply exist for documentation purposes.

At line 6, we declare a new function named “factorial” that will receive an input of “n”. This is done using the def or define call in Python. The “factorial” function occupies lines 6 through 13.

On line 7, we output the text “Factorial has been called with n = ” concatenated with the value of “n” cast as a string.

On lines 8 and 9, we enter the first part of a conditional statement. At line 8, we use a Boolean equals to see if “n” is equal to 1. If “n” is equal to 1, then line 8 executes and returns the value “1”.

Line 10 begins the process of addressing what to do if “n” does not equal 1.

On line 11, we declare a variable named “result”, which is defined as the value of “n” multiplied by the value of the “factorial” function with an input value that is one less than the current value of “n”.

Line 12 is simply allowing us to see the factorial value of the current “n” value each time through the loop.

Line 13 returns the value of the variable named “result”.

Line 15 calls the “factorial” function and provides it the necessary input to process. In this case, it is a 4.

Now, let’s see what happens when we run this code:

Factorial has been called with n = 4
Factorial has been called with n = 3
Factorial has been called with n = 2
Factorial has been called with n = 1
2 ! =  2
3 ! =  6
4 ! =  24
24

So, let’s see what’s going on with this output.

Lines 1 through 4 of the output are generated by line 7 of the code. That code displays the static words with the dynamic output of the value of “n”. Notice that each time through the loop, it decremented by 1.

Looking at lines 5 through 7 of the output, we see that the calculations actually start with the lowest factorial number of 2 and increment by 1.

Now, if you notice, the way the calculation was coded on line 11, we are performing the following:

  • (Step 1)  4! = 4 X 3!
    • This is the original problem. Solve for 4!, but it is defined needing to know the value of 3!, which is defined in step 2.
  • (Step 2)  3! = 3 X 2!
    • To solve step 1, we need to know the value of 3!. However, it is defined needing to know the value of 2!, which is defined in step 3.
  • (Step 3)  2! = 2 X 1!
    • To solve step 2, we need to know the value of 2!. However, it is defined needing to know the value of 1!, which is defined in step 4.
  • (Step 4)  1! = 1
    • To solve 3, we need to know the value of 1!. It has a given value of 1.
  • (Step 5)  2! = 2 X 1 = 2
    • Now, that we know the value of 1!, we can calculate the value of 2!.
  • (Step 6)  3! = 3 X 2 = 6
    • Now that we know the value of 2!, we can calculate the value of 3!.
  • (Step 7)  4! = 4 X 6 = 24
    • Now that we know the value of 3!, we can calculate the value of 4!, which was the original problem.

As you can see, the final solution is dependent upon the solution of a previous step, which was dependent upon the solution of a previous step, which was dependent upon the solution of a previous step, which – well you get the idea. This is the basic concept of recursion.