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

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.

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.

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?

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.

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

Yes, the exercise requires recusion to be used.

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

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

Recursion Considered Harmful?
 

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!

Re: Recursion Considered Harmful?
 

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.

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


or normally....

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!