locked
Recursive Methods RRS feed

  • Question

  • Was this the proper way to do this? 


    "Write and test a recursive method that computes the sum of the numbers in an array."


        class Program
        {
            static void Main(string[] args)
            {
                int sum = 0;
                foreach (int i in new int[] { 1, 2, 3 })
                {
                    sum += i;
                }
                Console.Out.WriteLine("sum=" + sum);   //sum=6
                Console.ReadLine();

            }
        }
    }
    Saturday, May 23, 2009 9:40 PM

Answers

  • No, that's not recursion, it's looping. Recursion is where a routine calls itself to solve the problem. A common example of this is the Fibbonacci series, which is defined as:

    F(1) = 1
    F(2) = 1
    F(n, n>2) = F(n-1) + F(n-2)

    So a method to calculate this would look like:

    public int Fibbonacci(int n) {
        if (n == 1 || n == 2) return 1;
       
        return Fibbonacci(n-1) + Fibbonacci(n-2);
    }

    If we were to use this for finding the Fibbonacci number where n = 5, the trace would be like this:

    Fibbonacci(5) -> n is not 1 or 2, so return Fibbonacci(4) + Fibbonacci(3).
      Fibbonacci(4) -> n is not 1 or 2, so return Fibbonacci(3) + Fibbonacci(2)
        Fibbonacci(3) -> n is not 1 or 2, so return Fibbonacci(2) + Fibbonacci(1).
          Fibbonacci(2) -> n is 2, so return 1
          Fibbonacci(1) -> n is 1, so return 1
        Fibbonacci(3) = 1 + 1, so return 2
        Fibbonacci(2) -> n is 2 so return 1 (this is the 2nd part of Fibbonacci(4)
      Fibbonacci(4) = 2 + 1 = 3
      Fibbonacci(3) -> n is not 1 or 2, so return Fibbonacci(2) + Fibbonacci(1) (this is 2nd part of Fibbonacci(5))
        Fibbonacci(2) -> n is 2, so return 1
        Fibbonacci(1) -> n is 1, so return 1
      Fibbonacci(3) = 1 + 1, so return 2
    Fibbonacci(5) = 3 + 2 = 5

    and we are done



    Ron Whittle - If the post is helpful or answers your question, please mark it as such.
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:48 AM
    Sunday, May 24, 2009 12:26 AM
  • Florian is correct... the loop you used is as efficient as you can get, recursion will only make it worse.

    Anyway, this looks like a school assignment... so I guess the goal is to let you explore recursion, not to get an efficient algorithm.

    A possible approach to make this recursive is to give a recursive definition of the problem. We can readily see that summing the elements of an array means to sum the value of the first element to the sum of all the remaining elements. We still need a "base case": we can use the fact that the sum of the element of an array containing zero elements is zero.

    Our recursive method will then look like this (I'll keep this static so that you can use it directly in your console program):

    private static int SumFromIndex (int [] array, int startIndex) {
      // handle the base case
      if (startIndex == array.Length) {
        return 0;
      }

      return (array [startIndex] + SumFromIndex (array, startIndex + 1)); // this is the recursive rule
    }

    We also want another "cosmetic" method so that calling

    private static int RecursiveSum (int [] array) {
      return SumFromIndex (array, 0);
    }

    You use it from main:

    static void Main (string [] args) {
      int [] testArray = { 1, 2, 3, 4, 5 };

      Console.WriteLine ("sum = {0}", RecursiveSum (testArray));
      Console.ReadLine ();
    }

    There are other ways of course... but this should be a reasonable starting point.

    HTH
    --mc

    • Edited by Mario Cossi Sunday, May 24, 2009 1:23 AM Fixed an error
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:47 AM
    Sunday, May 24, 2009 12:34 AM
  • I like Ron's example. Here is another one I did for a forum member a year or so ago. They wanted to Delete all files embedded within directories.

    //Declare in the namespace
    public delegate void DeleteDelegate(string directory); 

    //Code Snippet
    private static void DeleteFiles(string directory)
    {
        string[] directoryArray = Directory.GetDirectories(directory);
        if (directoryArray.Length != 0)
        {
            DeleteDelegate del = delegate(string d)
            {
                DirectoryInfo directoryInfo = new DirectoryInfo(d);
                FileInfo[] fileInfo = directoryInfo.GetFiles();
                foreach (FileInfo fi in fileInfo)
                    fi.Delete();
            };
            del(directory);
            foreach (string dir in directoryArray)
            {
                del(dir);
                DeleteFiles(dir);
            }
        }
    }

    John Grove - TFD Group, Senior Software Engineer, EI Division, http://www.tfdg.com
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:39 AM
    Sunday, May 24, 2009 1:47 AM
  • Hi,

    Your method is not a recursive method, which is not simple to create in C# simple because of the fact that there is checked if there is a return value.
    That is not so bad, because they are dangerous to use; you have not any control around them.

    The available memory on the users computer makes how many rounds it can make.

    See this sample of a recursive method.


            
            private static double sum = 0;
            static void Main(string[] args)
            {
                adder();
                Console.WriteLine(sum.ToString());
                Console.ReadLine();
            }
            private static void adder()
            {
                sum += 1;
                if (sum < 1000) adder();
            }
    
    

    If you change the 1000 for by instane 10000000000 you will see that you get a stack overflow (if not then even more)

    Cor

     
    • Proposed as answer by Cor Ligthert Sunday, May 24, 2009 6:14 AM
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:48 AM
    Sunday, May 24, 2009 6:14 AM

All replies

  • What's the reason why you need a recursive method for this? A simple loop (as you did) works fine.

    Edited: Typo
    Saturday, May 23, 2009 10:00 PM
  • No, that's not recursion, it's looping. Recursion is where a routine calls itself to solve the problem. A common example of this is the Fibbonacci series, which is defined as:

    F(1) = 1
    F(2) = 1
    F(n, n>2) = F(n-1) + F(n-2)

    So a method to calculate this would look like:

    public int Fibbonacci(int n) {
        if (n == 1 || n == 2) return 1;
       
        return Fibbonacci(n-1) + Fibbonacci(n-2);
    }

    If we were to use this for finding the Fibbonacci number where n = 5, the trace would be like this:

    Fibbonacci(5) -> n is not 1 or 2, so return Fibbonacci(4) + Fibbonacci(3).
      Fibbonacci(4) -> n is not 1 or 2, so return Fibbonacci(3) + Fibbonacci(2)
        Fibbonacci(3) -> n is not 1 or 2, so return Fibbonacci(2) + Fibbonacci(1).
          Fibbonacci(2) -> n is 2, so return 1
          Fibbonacci(1) -> n is 1, so return 1
        Fibbonacci(3) = 1 + 1, so return 2
        Fibbonacci(2) -> n is 2 so return 1 (this is the 2nd part of Fibbonacci(4)
      Fibbonacci(4) = 2 + 1 = 3
      Fibbonacci(3) -> n is not 1 or 2, so return Fibbonacci(2) + Fibbonacci(1) (this is 2nd part of Fibbonacci(5))
        Fibbonacci(2) -> n is 2, so return 1
        Fibbonacci(1) -> n is 1, so return 1
      Fibbonacci(3) = 1 + 1, so return 2
    Fibbonacci(5) = 3 + 2 = 5

    and we are done



    Ron Whittle - If the post is helpful or answers your question, please mark it as such.
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:48 AM
    Sunday, May 24, 2009 12:26 AM
  • Florian is correct... the loop you used is as efficient as you can get, recursion will only make it worse.

    Anyway, this looks like a school assignment... so I guess the goal is to let you explore recursion, not to get an efficient algorithm.

    A possible approach to make this recursive is to give a recursive definition of the problem. We can readily see that summing the elements of an array means to sum the value of the first element to the sum of all the remaining elements. We still need a "base case": we can use the fact that the sum of the element of an array containing zero elements is zero.

    Our recursive method will then look like this (I'll keep this static so that you can use it directly in your console program):

    private static int SumFromIndex (int [] array, int startIndex) {
      // handle the base case
      if (startIndex == array.Length) {
        return 0;
      }

      return (array [startIndex] + SumFromIndex (array, startIndex + 1)); // this is the recursive rule
    }

    We also want another "cosmetic" method so that calling

    private static int RecursiveSum (int [] array) {
      return SumFromIndex (array, 0);
    }

    You use it from main:

    static void Main (string [] args) {
      int [] testArray = { 1, 2, 3, 4, 5 };

      Console.WriteLine ("sum = {0}", RecursiveSum (testArray));
      Console.ReadLine ();
    }

    There are other ways of course... but this should be a reasonable starting point.

    HTH
    --mc

    • Edited by Mario Cossi Sunday, May 24, 2009 1:23 AM Fixed an error
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:47 AM
    Sunday, May 24, 2009 12:34 AM
  • I think the line:


      return (array [0] + SumFromIndex (array, startIndex + 1)); // this is the recursive rule

    should be:


      return (array [startIndex ] + SumFromIndex (array, startIndex + 1)); // this is the recursive rule
    Sunday, May 24, 2009 12:59 AM
  • Oops, this is what you get when you write code without testing, I guess.
    Fixed the code... thanks Matthew for pointing it out.

    --mc

    Sunday, May 24, 2009 1:24 AM
  • I like Ron's example. Here is another one I did for a forum member a year or so ago. They wanted to Delete all files embedded within directories.

    //Declare in the namespace
    public delegate void DeleteDelegate(string directory); 

    //Code Snippet
    private static void DeleteFiles(string directory)
    {
        string[] directoryArray = Directory.GetDirectories(directory);
        if (directoryArray.Length != 0)
        {
            DeleteDelegate del = delegate(string d)
            {
                DirectoryInfo directoryInfo = new DirectoryInfo(d);
                FileInfo[] fileInfo = directoryInfo.GetFiles();
                foreach (FileInfo fi in fileInfo)
                    fi.Delete();
            };
            del(directory);
            foreach (string dir in directoryArray)
            {
                del(dir);
                DeleteFiles(dir);
            }
        }
    }

    John Grove - TFD Group, Senior Software Engineer, EI Division, http://www.tfdg.com
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:39 AM
    Sunday, May 24, 2009 1:47 AM
  • Hi,

    Your method is not a recursive method, which is not simple to create in C# simple because of the fact that there is checked if there is a return value.
    That is not so bad, because they are dangerous to use; you have not any control around them.

    The available memory on the users computer makes how many rounds it can make.

    See this sample of a recursive method.


            
            private static double sum = 0;
            static void Main(string[] args)
            {
                adder();
                Console.WriteLine(sum.ToString());
                Console.ReadLine();
            }
            private static void adder()
            {
                sum += 1;
                if (sum < 1000) adder();
            }
    
    

    If you change the 1000 for by instane 10000000000 you will see that you get a stack overflow (if not then even more)

    Cor

     
    • Proposed as answer by Cor Ligthert Sunday, May 24, 2009 6:14 AM
    • Marked as answer by Bin-ze Zhao Wednesday, May 27, 2009 3:48 AM
    Sunday, May 24, 2009 6:14 AM
  • Your right, I'm learning Recursive methods.  I tried for awhile before looking for assistance.  So..  The below code (thanks to Mario)  does correctly satisfy the question from my book?


    namespace Unit_9_Project
    {

        class Program
        {
            private static int SumFromIndex(int[] array, int startIndex)
            {
                if (startIndex == array.Length)
                {
                    return 0;
                }

                return (array[startIndex] + SumFromIndex(array, startIndex + 1)); // this is the recursive rule
            }

            private static int RecursiveSum(int[] array)
            {
                return SumFromIndex(array, 0);
            }


            static void Main(string[] args)
            {
                int[] testArray = { 1, 2, 3, 4, 5 };

                Console.WriteLine("sum = {0}", RecursiveSum(testArray));
                Console.ReadLine();
            }
        }
    }
    Sunday, May 24, 2009 3:27 PM