Thread: Help Recursive functions

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    2

    Post Help Recursive functions

    I have an assignment and Im trying to do it, but I need to figure out how to do the recursive funtions. I know how to do it with the loop but I want it with the recursive. The funtion is find the smallest value
    int findsmallest(int list[], int size)

  2. #2
    Registered User
    Join Date
    Jan 2006
    Location
    Washington D.C.
    Posts
    25
    Lets say I want to have an exponential function. Meaning I'll take the first parameter (x) to the second parameter (y) power. Here is what it would look like recursively.

    Code:
    int power(int x, int y)
    {
        if (y == 0)
            return 1;
        else
            return x * power(x, y-1);
    }
    I just want to show you an example of recursion, but at the same time not give you the answer. The most fun is learning .

    Better yet, if that doesn't help, can you post the code of your looped method, and I'll help you understand how to translate to recursion.
    Last edited by guyonasm; 01-22-2006 at 02:55 PM.

  3. #3
    Registered User
    Join Date
    Jan 2006
    Posts
    2
    Thanks for your reply. I am having a hard time figuring out the recursive. I put the loop because you said can help me to figure out how to do it if i put the loop...so i can learn how to translate it.

    Code:
    int find_smallest(int list[] )
        {
    	int i, small =list[0];
    	
    	i = 1;
    	while (i< list.length )
    	    {
    		if ( small > list[i] )
    		    small = list[i];
    		list+=1;
    	    }
    
    	return small;
        }

  4. #4
    Registered User
    Join Date
    Jan 2006
    Location
    Washington D.C.
    Posts
    25
    That code looks nice . I'm assuming you're actually using Java , but for the sake of this being a C++ forum, I'm going to take what you have, and explain it in terms of C++, as your list.length is something I've only seen done while coding in Java .

    Now that I'm thinking about it, it might be easier just to show you a way.

    Code:
    int findsmall(int list[], int curr, int size)
    {
        if (size-1 == curr)
            return list[0];
        else
            if(list[curr] < list[0])
            {
                // swap values
                int temp = list[curr];
                list[curr] = list[0];
                list[0] = temp;
            }
                
        findsmall(list, curr+1, size);  
        return list[0];    
    }
    There is no <arrayname>.length to determine the size of the array in C++, so it must be provided as a parameter, which is size, and curr, is the current position within the array. This function swaps the lowest value, into the first element of the array until it hits the end of the array, and then returns the first element.

    There are many other ways to go about it, and assuming you use Java, the third parameter isn't even needed.

  5. #5
    Registered User
    Join Date
    Jun 2002
    Posts
    230
    Just a word of advice. You should never really need a loop inside of a recursive function because it defeats the point of recursion if the loop is doing the work. On the other hand if you can get a loop to make it work, it shouldnt be to hard to see how to change that into a recursive function.
    C++ Rules!!!!
    ------------
    Microsoft Visual Studio .NET Enterprise

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Code:
    int findsmallest(int list[], int size) {
      if ( size == 1 ) return list[0];
      else {
        int rest = findsmallest( list+1, size-1);
        return list[0] < rest ? list[0] : rest;
      }
    }

  7. #7
    Registered User
    Join Date
    Jan 2006
    Location
    Washington D.C.
    Posts
    25

    Thumbs up

    Quote Originally Posted by Salem
    Code:
    int findsmallest(int list[], int size) {
      if ( size == 1 ) return list[0];
      else {
        int rest = findsmallest( list+1, size-1);
        return list[0] < rest ? list[0] : rest;
      }
    }
    Salem, that is beautiful, because not only is it smaller and simpler, but you don't even modify the array as I do .

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Loops or recursive functions?
    By mariano_donati in forum C Programming
    Replies: 5
    Last Post: 05-12-2008, 12:41 PM
  2. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 05:42 AM
  3. Passing pointers between functions
    By heygirls_uk in forum C Programming
    Replies: 5
    Last Post: 01-09-2004, 06:58 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM