White-box and Black-box testing of recursive functions

Question

I learned white-box and black-box testing in terms of iterative functions. Now i need to do white-box and black-box testing of several recursive functions (in F#). take the following recursive algorithm for gcd:

gcd (m, n)
    if  (m % n) = 0 then
         n
    else 
        gcd n ( m % n)

For the white-box test: how exactly do i go about covering the different branches of the algorithm? Naively one could say there are two branches but when the function is called more than once the possible branches will obviously increase. Should i do testing with arguments which results in different amounts of recursive calls or how exactly do i determine which values to test with?

black-box: i get the general idea of black box testing. we should look at possible values we might want to call the function with without having knowledge of its inner workings. In this case i am just not sure which are values we might want to call it with. one way could be just to start with two values m and n for which gcd = 1 and then do the same for values m and for which gcd = 2 up to some gcd= n for some arbitrary number n. Is this how one is supposed to go about this?

Answer 1

First of all, I don't think there is one single established definition of how to do white-box and black-box testing of recursive functions, but here is how I interpret it.

White-box testing. We want to test the function based on its inner working. In case of recursive functions, I think this means that we want to test that the recursive calls it makes are the ones we would expect. One way to do this is to log all recursive calls. A simple implementation of gcd that does this adds a parameter to keep a log and returns it with the result:

let rec gcd log m n = 
  let log = (m, n)::log
  if (m % n) = 0 then List.rev log, n
  else gcd log n (m % n)

Now, for some two parameters, say 54 and 22, you can do the calculation by hand, decide what the parameters of the recursive calls should be and write a test for that:

let log, res = gcd [] 54 22
log |> shouldEqual [ (54, 22); (22, 10); (10, 2) ]

Black-box testing. Here, we assume we do not know how exactly the function works, so we cannot test its internals. All we can do is to test it using a number of inputs. It is probably a good idea to think of corner-case or tricky inputs because those are the ones that could cause problems. Given a simple implementation:

let rec gcd m n = 
  if (m % n) = 0 then n
  else gcd n (m % n)

I would probably write tests for the following:

// A random case where one of the numbers is the result
gcd 100 50 |> shouldEqual 50
gcd 50 100 |> shouldEqual 50

// A random case where the only divisor is 1
gcd 13 123 |> shouldEqual 1
gcd 123 13 |> shouldEqual 1

// The following are problematic and I'm not sure what the right behaviour is
gcd 0 0    // This probably should not be allowed    
gcd 10 -5  // This returns -5, but I'm not sure that's what we want

Random testing. You could also use random testing (which is a form of black box testing) to generate multiple test cases automatically. There are at least two random tests I can think of:

1. Generate two random numbers, a and b and check that gcd a b = gcd b a. This is testing only a very basic property, but it can cover quite a lot of cases.

2. Pick a random number a and a couple of primes p1, p2, .... Then split the primes into two groups and produce a*p1*p3*p5 and a*p2*p4*p6. Write a test that checks that the GCD of the two numbers is a.