LinuxQuestions.org
Register a domain and help support LQ
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-02-2005, 09:06 AM   #1
hubabuba
Member
 
Registered: Jan 2002
Location: UK
Distribution: Slack 14.1
Posts: 193

Rep: Reputation: 30
Recursion in C


Hello Everyone!

I am learning C from the book and I am a bit stuck on one exersice. I am not asking you to tell me how to wright the program for that exercise, I just want some help. I wrote the execrise question below and some questions after.

(Selection Sort) A selection sort searches an array looking for the smallest element in the array. When the smallest element is found, it is swapped with the first element of the array. The process is then repeated for the subarray beginning with the second element of the array. Each pass of the array results in one element being placed in its proper location. For an array of "n" elements, n - 1 passes must be made and for each subarray, n - 1 comparisons must be made to find the smallest value. When the subaaray being processed contains one element, the array is sorted. Write a recusive function selectionSort to perform this algorithm.

Here are the questions:

1) I have read that recursive function inludes "return", but I think the "selectionSort" function should be of type "void" because all it does is sort values in an array. So I think it will not return anything and should be of type void. Am I correct?

2) At the moment I have no idea how to make the subarray start with the second element of the array, the third and so on (recursively). Should I think that it will involve decrementing a velue untill it will equal to 1, in order to keep the recusion going? (like in the execise: n - 1)

3) In recursion, does a value always have to decrement to 1 or 0?

Thank you
 
Old 10-02-2005, 09:34 AM   #2
acid_kewpie
Moderator
 
Registered: Jun 2001
Location: UK
Distribution: Gentoo, RHEL, Fedora, Centos
Posts: 43,414

Rep: Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967
ahh at last, someone who gets how to ask homework questions properly.

1) well no, you'd most likely want to call the final thing using like, "newArr = sortthis(oldarr)" so the return would be the sorted array. you COULD make it rearrange the original array, but that's not a good way to do things normally.

2) remember that there is only ONE function. as such each recursion must be started with the very same information that the initial call is, i.e an array. How about simply not giving that first element to the next recursion in the first place? remove it from the array first off.

3) not sure what you mean by that at all, but essentially you are recusing until you find yourself starting the function with a single value array. you just look out for being asked to sort an array such as (999). you know you can't sort that, it's just one item! so there's the end of your sort.

essentially the new array doesn't exist at all until each successive sort has found it's lowest item. then all the recursive functions collapse in on themselves, spilling back the sorted array right at the end.
 
Old 10-02-2005, 12:28 PM   #3
hubabuba
Member
 
Registered: Jan 2002
Location: UK
Distribution: Slack 14.1
Posts: 193

Original Poster
Rep: Reputation: 30
Thanks Chris,

1) Do I have to use the "for" loop to scan through the array and swap elements and then the recursion will run starting with the second element of the original array to repeat the step?

2) Should I not pass an array and the element number as the parameter to the recursive function?

I have many more questions, but these are the last ones I am asking.

This is just too confusing, I have been trying to write this program for the last two days and still can figure it out, it is really p*****g me off now.
 
Old 10-02-2005, 12:35 PM   #4
acid_kewpie
Moderator
 
Registered: Jun 2001
Location: UK
Distribution: Gentoo, RHEL, Fedora, Centos
Posts: 43,414

Rep: Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967
1) you don't *have* to do anything... up to you. you do need some way to access each value in turn though.

2) no. only if you think it's suitable to call the first function as newArr=(oldArr, 0) or something... and that's just messy. you should write ONE function only. you need to basically find the lowest value, keep it safe, and give everything else to the next recursion.

where are you studying btw?
 
Old 10-02-2005, 12:59 PM   #5
hubabuba
Member
 
Registered: Jan 2002
Location: UK
Distribution: Slack 14.1
Posts: 193

Original Poster
Rep: Reputation: 30
I study in Southampton Solent University used to be called Southampton Institute, but it is computer networking course, not programing. I am learning C by myself, I love Linux and programming and always wanted to learn C and C++, but struggling with it as you can see.
 
Old 10-02-2005, 01:21 PM   #6
Dark_Helmet
Senior Member
 
Registered: Jan 2003
Posts: 2,786

Rep: Reputation: 369Reputation: 369Reputation: 369Reputation: 369
Quote:
Originally posted by hubabuba
3) In recursion, does a value always have to decrement to 1 or 0?
If I could expand a little on what acid_kewpie was getting at... There is no "one way" to implement a recursive algortihm, but every recursive algorithm must include a terminating condition: a set of input values that prevents another self-call. It sounds like you're relying on a decrementing counter telling the number of unsorted elements. That'll work. You could also have a counter that increments until the number of items sorted is equal to the array's size. There are tons of way you can set up your terminating condition.

I do have a question though: Do you have to use recursion? Is that what the exercise requires? You could accomplish the same sort with two for loops (one nested in the other).
 
Old 10-02-2005, 01:36 PM   #7
hubabuba
Member
 
Registered: Jan 2002
Location: UK
Distribution: Slack 14.1
Posts: 193

Original Poster
Rep: Reputation: 30
Yes, the exercise requires recusion to be used.
 
Old 10-02-2005, 01:53 PM   #8
acid_kewpie
Moderator
 
Registered: Jun 2001
Location: UK
Distribution: Gentoo, RHEL, Fedora, Centos
Posts: 43,414

Rep: Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967Reputation: 1967
Well we can only go so far in helping you, as you're clearly aware. it's very simple recursion really, and is a great demonstration on how it's useful. But generally take the next element in the array. is it the lowest number so far? no? add it to a new array. yes? well store it in a variable. is there already a number in that variable? yes? push that one on to the new array. got to the end of the array? pass the new array to yourself as a recursion. Recieve a sorted array back from the recursion and attach your lowest number to the start and return it. job done.

i've a friend just completing a phd in marine biology or somethign down in southampton at the real uni, that silly bridge over the river is a killer...
 
Old 10-02-2005, 01:58 PM   #9
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
I remember being taught recursive algorithms in my earliest programming classes, but later learned that recursive function-calling is nearly always a bad idea, for reasons of memory and stability.

Sometimes it's hard to think of a non-recursive solution. You might have fun coming up with one anyway, even if it's not assigned
 
Old 10-02-2005, 02:12 PM   #10
taylor_venable
Member
 
Registered: Jun 2005
Location: Indiana, USA
Distribution: OpenBSD, Ubuntu
Posts: 892

Rep: Reputation: 41
Recursion Considered Harmful?

Quote:
I remember being taught recursive algorithms in my earliest programming classes, but later learned that recursive function-calling is nearly always a bad idea, for reasons of memory and stability.
As you hint at, recursion is often used because it's the solution that most closely matches how we (as humans) see the problem. But I wouldn't consider it a bad idea, even though it does inherently cost a little speed in function-call overhead. Rather, using a solution you can easily understand will save you lots of time and energy, opposed to trying to create a solution that doesn't make much logical sense, but is iterative instead of recursive. You don't lose much in terms of peformance these days, unless you're writing some really sensitive component. I'd also argue that you're more likely to make "off-by-one" iterative mistakes than infinite recursion mistakes, and even if you do, those infinite recursion errors are easier to identify. As to memory, using recursion can help you isolate variables and such that should not interact or impact one another (assuming that you're using variables with limited scope), for example when solving a maze. Recursion is good for you!
 
Old 10-02-2005, 05:11 PM   #11
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
Re: Recursion Considered Harmful?

Quote:
Originally posted by taylor_venable
Recursion is good for you!
OK, I admit I still use it when it makes sense It is a good concept to help introduce what you can do with programming, and is usually easy to understand. But for me at least, it promoted the tendency to look for a recursive solution in cases where an iterative one would be more logical.

In my 2nd edition Deitel & Deitel "C++ How to Program", for instance, the very first recursion example is to calculate a factorial (this seems to be the favorite way of illustrating recursion). 5! = 5 * 4!, which is ( 5 * ( 4 * 3! ) ), which is ( 5 * ( 4 * ( 3 * 2! ) ) )... sure, it works, but it's simpler and more logical to just do 5! = 5 * 4 * 3 * 2 * 1. No additional function-calling overhead, no possibility of stack overflow.

Humans (in general) may find some recursive concepts more natural, but programmers should also be adept at expressing concepts in terms that computers find easier to deal with, especially if efficiency (of memory space or execution time) is of concern.
 
Old 10-03-2005, 06:51 AM   #12
bigearsbilly
Senior Member
 
Registered: Mar 2004
Location: england
Distribution: FreeBSD, Debian, Mint, Puppy
Posts: 3,298

Rep: Reputation: 175Reputation: 175
Here's a simple recursion:
reverses strings.

1. if string is NULL return (the terminating condition)
2. reverse the rest of the string minus the first character and...
3. print the first character

Code:
#include <stdio.h>


void reverse(char * string)
{
    char char1 = string[0];

    if (char1 == NULL ) {    /* if NULL string return */
        return;
    }

    reverse(string + 1);  /* reverse the string and... */
    putchar (char1);     /* print this character */

}
int main(int argc, char ** argv)
{

        for( ++argv; --argc; ++argv) {
            reverse(*argv);
            putchar('\n');
        }
}

or normally....
Code:
void reverse(char * string)
{
    if (! *string ) {    /* if NULL string return */
        return;
    }

    reverse(string + 1);  /* reverse the string and... */
    putchar (*string);    /* print this character */

}
 
Old 10-03-2005, 08:46 AM   #13
enemorales
Member
 
Registered: Jul 2004
Location: Santiago, Chile
Distribution: Ubuntu
Posts: 410

Rep: Reputation: 30
I'll recommend you to sort "in-place", because if you don't do that then you will have to merge the result of the induction in a new array and that's messy. About the recursion, use a function like this

sort(array,from,to)

array: the array to sort
from: the first position in the array
to: the last position in the array.

so the idea is that it sort the element between positions from and to and does not touch the others. In this way you can implement the recursion by changing the value of "from".

HTH!
 
  


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
chmod recursion -- files only Risc91 AIX 12 09-18-2012 09:58 AM
Perl, recursion ivanatora Programming 11 03-14-2005 02:49 PM
tar: '--no-recursion' option doesn't prevent recursion Earl Parker II Slackware 12 08-17-2004 03:49 AM
Writing bash script with recursion.. ray5_83 Programming 4 08-04-2004 06:44 PM
help with recursion function debdas Programming 4 05-14-2003 04:03 AM


All times are GMT -5. The time now is 09:05 PM.

Main Menu
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