CODEWITHSUNDEEP
c#algorithm
Mike Hofer
Mike Hofer

Reputation: 17002

Why would this method need to be recursive?

On a whim, I've decided to go back and seek certification, starting with 98-361, Fundamentals of Software Development. (I'm doing this more for myself than anything else. I want to fill in gaps in my knowledge.)

In the very early course of the book, they present this interesting scenario in the Proficient Assessment section:

You are developing a library of utility functions for your application. You need to write a method that takes an integer and counts the number of significant digits in it. You need to create a recursive program to solve this problem. How would you write such a program?

I find myself gaping at this scenario in befuddlement. If I understand "significant digits" correctly, there's no need whatsoever for a function that counts an integer's significant digits to be recursive. And, any architect who insisted that it be recursive should have his head examined.

Or am I not getting it? Did I completely miss something here? From what I understand, the significant digits are the digits of a number, starting from the left, and proceeding right, excluding any leading zeroes.

Under what conditions would this need to be recursive? (The whole point of this exercise for me is to learn new things. Someone throw me a bone.)

EDIT: I don't want an answer to the problem question. I can figure that out on my own. It just seems to me that this "problem" could be solved far more easily with a simple foreach loop over the characters in a string.

Final Edit

Given the sage advice of the awesome posters below, this was the simple solution I came up with to solve the problem. (Despite what misgivings I may have.)

using System;

class Program
{
    static void Main(string[] args)
    {

        var values = new[] { 5, 15, 150, 250, 2500, 25051, 255500005, -10, -1005 };
        foreach (var value in values)
        {
            Console.WriteLine("Signficiant digits for {0} is {1}.", value, SignificantDigits(value));
        }
    }

    public static int SignificantDigits(int n)
    {
        if (n == 0)
        {
            return 0;
        }

        return 1 + SignificantDigits((int)(n / 10));
    }
}

Upvotes: 0

Views: 755

Answers (3)

paxdiablo
paxdiablo

Reputation: 881383

There's no need for such an algorithm to be recursive. But the intent here is not to write real-world code, it's to ensure you understand recursion.

Since you stated you weren't after code, I'll be careful here, but I need to provide something to compare the complexity of the solutions, so I'll use pseudo-code. A recursive solution may be something like:

def sigDigits (n):
    # Handle negative numbers.

    if n < 0:
        return sigDigits (-n)

    # 0..9 is one significant digit.

    if n < 10:
        return 1

    # Otherwise it's one plus the count in n/10 (truncated).

    return 1 + sigDigits (n / 10)

And you're right, it equally doable as iteration.

def sigDigits (n):
    # Handle negative numbers.

    if n < 0:
        n = -n

    # All numbers have at least one significant digit.

    digits = 1

    # Then we add one and divide by ten (truncated), until we get low enough.

    while n > 9:
        n = n / 10
        digits = digits + 1

    return digits

There are some (usually of a mathematical bent, and including myself) that consider recursive algorithms much more elegant where they're suitable (such as where the "solution search space" reduces very quickly so as to not blow out your stack).

I question the suitability in this particular case since the iterative solution is not too complex, but the questioner had to provide some problem and this one is relatively easy to solve.

And, as per your edit:

... could be solved far more easily with a simple foreach loop over the characters in a string

You don't have a string, you have an integer. I don't doubt that you could turn that into a string and then count characters but that seems a roundabout way of doing it.

Upvotes: 4

Oleksi
Oleksi

Reputation: 13097

That seems like a pretty forced example. The problem can be solved with an simpler iterative algorithm.

A lot of teaching resources really struggle to provide useful examples of when to use recursion. Technically you never need to use it, but for a large class of (mostly algorithmic) problems, it can really simplify things.

For example, consider any operation on a binary tree. Because the physical structure of a binary tree is recursive, the algorithms that operate on it are also naturally recursive. You can also write imperative algorithms to operate on binary trees, but the recursive ones are simpler to write and understand.

Upvotes: 1

Mitch Wheat
Mitch Wheat

Reputation: 300549

It doesn't need to be recursive. It's simply that the question is asking you to write a recursive implementation, presumably to test your understanding of how a recursive function works.

Upvotes: 2

Related Questions