LinuxQuestions.org
Review your favorite Linux distribution.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 10-07-2005, 01:09 PM   #1
hubabuba
Member
 
Registered: Jan 2002
Location: UK
Distribution: Slack 14.1
Posts: 193

Rep: Reputation: 30
using return in recursive function


Hi

I've looked up, that a function can return without actually specifiyng what to return. All I have entered is "return" in my recursive function. The function is meant to return an array, but as far as i understand, I cannot return an array by entering: return array. Correct? So, using "return" on its own is used to stop the function. Correct?
 
Old 10-07-2005, 01:20 PM   #2
itsme86
Senior Member
 
Registered: Jan 2004
Location: Oregon, USA
Distribution: Slackware
Posts: 1,246

Rep: Reputation: 58
It's that a function can return without actually specifying what to return, but only if it's a void function. If you define the function as returning a value then you should always return a value from the function. Maybe if you show your function we can give you some helpful hints.
 
Old 10-07-2005, 01:29 PM   #3
bigfez
LQ Newbie
 
Registered: Mar 2005
Posts: 29

Rep: Reputation: 15
What language are you using?
 
Old 10-07-2005, 04:36 PM   #4
hubabuba
Member
 
Registered: Jan 2002
Location: UK
Distribution: Slack 14.1
Posts: 193

Original Poster
Rep: Reputation: 30
here is the function:

Code:
int selectionSort(int a[], int f, int t)
{
  int i;
  int hold;
  int smallest;  

  if(f == t)
  {
    return;
  }

  for(i = 0; i < N; i++)
  {
    if(i == 0)
    {
      hold = a[i];
      smallest = i;
    }

    else
    {
      if(a[i] < hold)
      {
        hold = a[i]; 
        smallest = i;
      }
   
      else if(i == 4)
      {
        a[smallest] = a[f];
        a[f] = hold;
      }
    }
  } 
   
  selectionSort(a, f + 1, t);
}

Last edited by hubabuba; 10-07-2005 at 04:40 PM.
 
Old 10-07-2005, 05:04 PM   #5
itsme86
Senior Member
 
Registered: Jan 2004
Location: Oregon, USA
Distribution: Slackware
Posts: 1,246

Rep: Reputation: 58
You're not ever returning a value so I'd just redefine the function as returning type void instead of int.
 
Old 10-09-2005, 02:12 PM   #6
The_Nerd
Member
 
Registered: Aug 2002
Distribution: Debian
Posts: 540

Rep: Reputation: 32
And you really should be passing pointers around instead of arrays. Passing arrays to functions is very inefficient. This is because every time you call a function the parameters actually are a local copy of the origional (meaning they are destroyed when the function returns). So, in example:

Code:
int myfunction(int myint)
{
    myint++; //value increased
    return 0; //myint destroyed
}

int main(int argc, char **argv)
{
    int i = 1; //i created and assigned the value of 1
    myfunction(i); //myint created and assigned the value of i
    printf("value: %d", i); //i still = 1
}
the output will be:

Code:
value: 1
The reason is because when you call myfunction(i) a copy of i is created (myint). So you are actually working with a copy, not the origional variable. This is fine in allot of cases, but it is inefficient. It starts being a problem when you really do need to modify the origional variable, and/or when you are passing arrays. Lets say you pass an array to your function that is 1000 ints long (4000 bytes if sizeof(int) = 4). That means your program will have to copy 4000 bytes every time the function is called. It can start getting really slow and start being a big memory hog.

That is why it is better to use pointers when passing arrays. A pointer to an array will point to the start of the array in memory. So, if you did this:

Code:
int selectionSort(int *a, int f, int t)
{
  if (a == NULL) return 0; //make sure it isn't a invalid pointer
  int i;
  int hold;
  int smallest;  

  if(f == t)
  {
    return;
  }

  for(i = 0; i < N; i++)
  {
    if(i == 0)
    {
      hold = a[i];
      smallest = i;
    }

    else
    {
      if(a[i] < hold)
      {
        hold = a[i]; 
        smallest = i;
      }
   
      else if(i == 4)
      {
        a[smallest] = a[f];
        a[f] = hold;
      }
    }
  } 
   
  selectionSort(a, f + 1, t);
}
Then you are only making a copy of the pointer (which is either 4, 8 bytes... depending on the system and compiler). The size of the pointer never changes. So even if your array is 10000 ints long, you still only copy 4/8 bytes.

Good luck!
 
Old 10-09-2005, 04:37 PM   #7
btmiller
Senior Member
 
Registered: May 2004
Location: In the DC 'burbs
Distribution: Arch, Scientific Linux, Debian, Ubuntu
Posts: 4,164

Rep: Reputation: 330Reputation: 330Reputation: 330Reputation: 330
Quote:
Originally posted by The_Nerd
[B]And you really should be passing pointers around instead of arrays. Passing arrays to functions is very inefficient. This is because every time you call a function the parameters actually are a local copy of the origional (meaning they are destroyed when the function returns).
Actually, arrays a never copied when passed to a function as per question 6.4 of the C FAQ.
 
Old 10-09-2005, 05:45 PM   #8
The_Nerd
Member
 
Registered: Aug 2002
Distribution: Debian
Posts: 540

Rep: Reputation: 32
Quote:
Originally posted by btmiller
Actually, arrays a never copied when passed to a function as per question 6.4 of the C FAQ.
Kewl! Didn't know that. Makes sense though.
 
Old 10-09-2005, 06:02 PM   #9
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,455

Rep: Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172Reputation: 1172
Languages such as C++ and Pascal provide for this notion very easily by distinguishing between passing parameters by value and by reference. The "C" language obliges you to use explicit pointers for this purpose, while C++/Pascal do the same task without changing the notation.

When a parameter is passed "by value," a copy of the value is placed on the stack and it becomes in-effect a private-variable of the function. The function can change the value at-will because only the copy, on the stack, is ever being manipulated. These changes are not and cannot be seen by the caller.

When a parameter is passed "by reference," a pointer to the original value is placed on the stack. (Just as you did, explicitly, in "C.") All of the references to this value are accomplished indirectly, by means of the pointer on the stack. When the language (C++, Pascal) supports this concept, you simply refer to the parameter the same way whether it's being passed by value or by reference. When it does not ("C"), you must write different source-code.

In any case, when you are passing a "complex object," such as an array, you probably always want to pass it "by reference." Although implementations vary, "stack space" should be considered a limited resource... you can run out of it. As a categorical rule, "large" things should be dynamically allocated, so that the space for them is not in the stack but in the heap. This rule holds both for parameters and for local variables, both of which live in the stack.
 
Old 10-10-2005, 10:59 AM   #10
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,314

Rep: Reputation: 175Reputation: 175
Are you creating a sorted copy of the array or destructively sorting it?

Well, C is not *really* great at doing recursive functions.
You can do it, obviously, but it gets messy.

It's not as easy as lisp for example. You have to organise all your own storage space
etc.

You can't really return an array as such except the pointer to one passed
in.

I notice from your code that you don't (seem to) pass in the size of the array.
Another C drawback is you can't determine the size of an array passed
as a parameter so you'll need to pass the size in too.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
gcc: recursive function quirk Disruptor Linux - Software 4 09-23-2014 06:45 AM
Perl file handler in recursive function enemorales Programming 4 02-02-2009 04:20 PM
can a function return a string? hubabuba Programming 13 03-06-2005 03:51 PM
error recursive function in c shams Programming 3 07-28-2004 09:44 PM
Recursive Function TriggerJ Programming 4 02-02-2004 09:58 PM


All times are GMT -5. The time now is 10:21 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration