Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Writing a recursive function by using optional parameters

  1. Jul 24, 2016 #1
    One way that I often write recursive functions in my work is by having an optional parameter that is used for all calls after the first. For example, here's how I might implement the classic "Find the largest palindrome in a given string" interview-type problem:

    Code (Text):

    using System;

    public static class Extensions
    {
        private static string Reverse(this string s)
        {
            char[] charArray = s.ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray);
        }  
       
        public static string LargestPalindrome(this string s, int k = -1)
        {
            if(k == -1) // If function was called for the first time
            {
                return s.LargestPalindrome(s.Length);          
            }

            // Try to find palindrome in all substrings of length k
            for(int i = 0, j = s.Length - k; i <= j; ++i)
            {
                string ss = s.Substring(i, k);
                if(ss == ss.Reverse())
                    return ss;          
            }
           
            // If here, didn't find a palindrome. Try all substrings
            // of length k - 1.
            return s.LargestPalindrome(k - 1);
           
        }
    }

                       
    public class Program
    {  
        public static void Main()
        {
            string s = "kandasndddsk";
            Console.WriteLine(s.LargestPalindrome()); // Expected output: "ddd"
        }
    }
     
    This is an alternative to writing it like

    Code (Text):

    using System;

    public static class Extensions
    {
        private static string Reverse(this string s)
        {
            char[] charArray = s.ToCharArray();
            Array.Reverse(charArray);
            return new string(charArray);
        }  
       
        private static string LargetsPalindrome_Subroutine(this string s, int k)
        {
            // Try to find palindrome in all substrings of length k
            for(int i = 0, j = s.Length - k; i <= j; ++i)
            {
                string ss = s.Substring(i, k);
                if(ss == ss.Reverse())
                    return ss;          
            }
           
            // If here, didn't find a palindrome. Try all substrings
            // of length k - 1.
            return s.LargestPalindrome(k - 1);      
        }
       
        public static string LargestPalindrome(this string s)
        {
            return s.LargestPalindrome(s.Length);                  
        }
    }

                       
    public class Program
    {  
        public static void Main()
        {
            string s = "kandasndddsk";
            Console.WriteLine(s.LargestPalindrome()); // Expected output: "ddd"
        }
    }
     
    Let me explain what I think are the advantages and disadvantages of the first way.

    Advantages:
    * Fancier
    * Slightly less code

    Disadvantages:
    * Although its intent is for the caller to use it with empty pamarameters, the call with a parameter is public and so it can be used as not intended. It could be argued that this violates OOP religious commandements.
     
  2. jcsd
  3. Jul 25, 2016 #2

    Filip Larsen

    User Avatar
    Gold Member

    Personally I would in general fancy the second version and possibly with the recursive function non-public as you have made it unless it really was meant to be called by an unknown caller. In your case the recursive function is simple and it may make sense for a caller to specify the maximum palindrome length, but in other cases where delicate data structures have to be prepared first you would not want to leave that up to an unknown caller.

    Also, in this particular case (and since its already on tail recursive form) I think I would write the algorithm as a single non-recursive function, possibly still with an optional argument where the caller can specify maximum palindrome length.

    Later: I suppose this is just an example and you are aware that the comparison with the reverse string can be done without allocating a new string.
     
  4. Jul 26, 2016 #3
    I would disagree with both of the claimed Advantages.

    1. "Fancier". This is simply not an advantage. In what way is "fancy" code better? If anything, "fancier" code can lead to bugs as usage of it can be obscure (as implied in the Disadvantages).

    2. "Slightly less code". While the first version does away with one method definition, the equivalent call is still made, and the (doesn't always mean much) measure "lines of code" is about the same.

    Worse, an entire conditional is added - that has to be evaluated in every iteration. The "if (k == -1)" is tested every time the recursed method is called ... and the condition it looks for only applies once. It might not matter in this simple example, but in general a recursed or iterated method should be as lean as possible.

    So I'd prefer the second method. It's cleaner, clearer and more efficient.

    Even if I wanted callers to be able to specify the maximum length of palindrome, I'd have the public and private parts separated. The public method would be able to do validation (like checking the requested length isn't longer than the string itself), before calling the private method to do the work.

    Finally, and maybe this is more an issue of style, I'd use a nullable int as the optional parameter. Using "-1" as a guard feels a bit old fashioned, and -1 vs value is less obvious than null vs value. (The inner routine would still take a non-nullable int).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Writing a recursive function by using optional parameters
  1. Recursion function (Replies: 5)

Loading...