How does this function calculate?

Question

I've been working through CodeWars katas and I came across a pretty cool solution that someone came up with. The problem I have is I don't understand how it works. I understand some of it like what it is generally doing but not detail specifics. Is it returning itself? How is it doing the calculation? Can someone explain this to me because I really what to learn how to do this. And if you know of any other resources I can read or watch that would be helpful. I didn't see anything like this in the Swift documentation.

    func findDigit(_ num: Int, _ nth: Int) -> Int {
           let positive = abs(num)

           guard nth > 0 else { return -1 }
           guard positive > 0 else { return 0 }
           guard nth > 1 else { return positive % 10 }

           return findDigit(positive / 10, nth - 1) }        

For context:

Description:

The function findDigit takes two numbers as input, num and nth. It outputs the nth digit of num (counting from right to left).

Note

If num is negative, ignore its sign and treat it as a positive value. If nth is not positive, return -1. Keep in mind that 42 = 00042. This means that findDigit(42, 5) would return 0.

Examples

findDigit(5673, 4) returns 5

findDigit(129, 2) returns 2

findDigit(-2825, 3) returns 8

findDigit(-456, 4) returns 0

findDigit(0, 20) returns 0

findDigit(65, 0) returns -1

findDigit(24, -8) returns -1

Greatly appreciate any help. Thanks.

Answer 1

This is a simple recursive function. Recursive means that it calls itself over and over until a condition is satisfied that ends the recursion. If the condition is never satisfied, you'll end up with an infinite recursion which is not a good thing :)

As you already understand the purpose of the function, here are the details of how it works internally:

// Saves the absolute value (removes the negative sign) of num
let positive = abs(num)

// Returns -1 if num is 0 or negative
guard nth > 0 else { return -1 } 

// Returns 0 if the absolute value of num is 0 (can't be negative)
guard positive > 0 else { return 0 } // Could be guard positive == 0

// nth is a counter that is decremented with every recursion.
// positive % 10 returns the remainder of positive / 10
// For example 23 % 10 = 3
// In this line it always returns a number from 0 - 9 IF nth <= 0
guard nth > 1 else { return positive % 10 }

// If none of the above conditions are true, calls itself using
// the current absolute value divided by 10, decreasing nth.
// nth serves to target a different digit in the original number
return findDigit(positive / 10, nth - 1) 

Let's run through an example step by step:

findDigit(3454, 3)
num = 3454, positive = 3454, nth = 3
-> return findDigit(3454 / 10, 3 - 1)

num = 345, positive = 345, nth = 2 // 345, not 345.4: integer type
-> return findDigit(345 / 10, 2 - 1)

num = 35, positive = 35, nth = 1
-> return 35 % 10
-> return 5

Answer 2

This is a recursive algorithm. It works by solving the original problem by reducing it to a smaller problem of the same time, then solving that, recursively, until a base case is hit.

I think you'll have a much easier time understanding it if you see the calls being made. Of course, it's best to step through this in the debugger to really see what's going on. I've numbered the sections of interest to refer to them below

func findDigit(_ num: Int, _ nth: Int) -> Int {
    print("findDigit(\(num), \(nth))") //#1
    let positive = abs(num) // #2

    guard nth > 0 else { return -1 } // #3
    guard positive > 0 else { return 0 } // #4
    guard nth > 1 else { return positive % 10 } // #5

    return findDigit(positive / 10, nth - 1) // #6
}

print(findDigit(5673, 4))

1. I print out the function and its parameters, do you can see what's going on. Here's what's printed:

   findDigit(5673, 4)

   findDigit(567, 3)

   findDigit(56, 2)

   findDigit(5, 1)

   5

2. Take the positive value of num, so the - sign doesn't get in the way.

3. Assert that the nth variable is greater than 0. Since the digit counting in this problem, any value equal to less 0 is invalid. In such a case, -1 is returned. This is very bad practice in Swift. This is what Optionals exist for. It's much better to make this function return Int? and returning nil to represent an error in the nth variable.

4. Assert that the positive variable is greater than 0. The only other possible case is that positive is 0, in which case its digit (for any position) is 0, so that's why you have return 0.

5. Assert that nth is greater than 1. If this is not the case, then nth must be 1 (the guard numbered #3 ensures it can't be negative, or 0. In such a case, the digit in the first position of a decimal number is that number modulo 10, hence why positive % 10 is returned.

6. If we reach this line, than we know we have a sane value of nth (> 0), which isn't 1, and we have a positive number greater than 0. Now we can proceed to solve this problem by recursing. We'll divid positive by 10, and make it into the new nth, and we'll decrement nth, because what is the nth digit of this call, will be in the n-1 th spot of the next call.

Answer 3

Someone by the name of JohanWiltink on CodeWars answered my question. But I chose to accept Nicolas's for the detail.

This was JohanWiltink explanation:

The function does not return itself as a function; it calls itself with different arguments and returns the result of that recursive call (this is possibly nested until, in this case, nth=1).

findDigit(10,2) thus returns the value of findDigit(1,1).

If you're not seeing how this works, try to work out by hand what e.g. findDigit(312,3) would return.

Thanks so much to everyone that answered! Really appreciate it!

Answer 4

It is a recursive solution. It does not return itself, per se, it calls itself on a simpler case, until it gets to a base case (here a 1 digit number). So for example, let us trace through what it does in your first example: findDigit(5673, 4) calls findDigit (567, 3) calls findDigit (56,2) calls findDigit (5,1) which is the base case which returns 5 which bubbles all the way back up to the surface.