Assignment 5.2: Recursion

Overview

In this assignment you will be modifying Assignment 5.1, where you had to create a radio which played a user-determined station for a user-determined length of time. It also had you create two separate files for your source code, and taught you how to save the Station class to an existing package.

You will be changing the play action in the Station class to use recursion instead of a repeat statement. Recursion is when a function calls itself, and each time it calls itself it moves closer and closer to meeting its end condition. An end condition is a condition that, when met, the recursive action stops calling itself. An example of this is having an end condition be when some integer variable is 0. This end condition is technically termed the base case.

Factorial Example

The code below calculates the factorial of a given number using recursion. The factorial of a number is the multiplication of that number with all integers smaller than it, but greater than or equal to 1. For example, in Quorum, one might hard code the factorial of 5 as:

integer FactorialOfFive = 5 * 4 * 3 * 2 * 1

which is the integer value 120.

action Main
    integer a = Factorial(5)
    output "a is equal to" + a

end

action Factorial (integer num) returns integer
    // This is the "base case" condition. You want to stop multiplying integers when you reach one. Otherwise, you will compute the wrong answer, particularly if you mistakenly multiply by 0!
    if num <= 1
         return 1
    else
         // This is the recursive step.
         return Factorial(num-1) * num 
    end
end

"a is equal to 120"

What's happening in this example is that the end condition, also called a base case is:

if num <= 1 then
return 1

This is the condition that will stop the recursive calls when it's met. The original call to that action, 5 in this case, got passed into the factorial function and started the recursive chain. After it ran through the function the first time it got to:

return Factorial(num-1) * num

Thus calling itself, the Factorial action, with num -1. Num is now one step closer to the base case, which is equal to or less than one. Consider what would happen if you used an addition operator in place of the subtraction operator. Would the program ever end? What about if num wasn't changed in the function?

An important take-away from this is that recursive actions have to have parameters to communicate with themselves. Without parameters there is no way for a recursive action to call itself while working towards a base case. What would happen if the recursive action was instead:

action Factorial() returns integer
    if num <= 1 then
         return 1
    end else then
         num-1
         return Factorial() * num 
    end
end

In that code example there is no way for the recursive action to pass the information that num got decremented by 1 to the next action call. It would go into an infinite loop and crash the program.