Register a domain and help support LQ
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Recursion in C
 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

 10-02-2005, 08:06 AM #1 hubabuba Member   Registered: Jan 2002 Location: UK Distribution: Slack 14.1 Posts: 193 Rep: 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
 10-02-2005, 08:34 AM #2 acid_kewpie Moderator   Registered: Jun 2001 Location: UK Distribution: Gentoo, RHEL, Fedora, Centos Posts: 43,415 Rep: 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.
 10-02-2005, 11:28 AM #3 hubabuba Member   Registered: Jan 2002 Location: UK Distribution: Slack 14.1 Posts: 193 Original Poster Rep: 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.
 10-02-2005, 11:35 AM #4 acid_kewpie Moderator   Registered: Jun 2001 Location: UK Distribution: Gentoo, RHEL, Fedora, Centos Posts: 43,415 Rep: 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?
 10-02-2005, 11:59 AM #5 hubabuba Member   Registered: Jan 2002 Location: UK Distribution: Slack 14.1 Posts: 193 Original Poster Rep: 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.
10-02-2005, 12:21 PM   #6
Dark_Helmet
Senior Member

Registered: Jan 2003
Posts: 2,786

Rep:
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).

 10-02-2005, 12:36 PM #7 hubabuba Member   Registered: Jan 2002 Location: UK Distribution: Slack 14.1 Posts: 193 Original Poster Rep: Yes, the exercise requires recusion to be used.
 10-02-2005, 12:53 PM #8 acid_kewpie Moderator   Registered: Jun 2001 Location: UK Distribution: Gentoo, RHEL, Fedora, Centos Posts: 43,415 Rep: 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...
 10-02-2005, 12:58 PM #9 wapcaplet Guru   Registered: Feb 2003 Location: Colorado Springs, CO Distribution: Gentoo Posts: 2,018 Rep: 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
10-02-2005, 01:12 PM   #10
taylor_venable
Member

Registered: Jun 2005
Location: Indiana, USA
Distribution: OpenBSD, Ubuntu
Posts: 892

Rep:
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!

10-02-2005, 04:11 PM   #11
wapcaplet
Guru

Registered: Feb 2003
Distribution: Gentoo
Posts: 2,018

Rep:
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.

 10-03-2005, 05:51 AM #12 bigearsbilly Senior Member   Registered: Mar 2004 Location: england Distribution: FreeBSD, Debian, Mint, Puppy Posts: 3,352 Rep: 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 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 */ }```
 10-03-2005, 07:46 AM #13 enemorales Member   Registered: Jul 2004 Location: Santiago, Chile Distribution: Ubuntu Posts: 410 Rep: 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!