Role of "C" programming language for a beginner?

[narayan594]

Please any one help me with your suggestion......

I need a reason for why C.

[astropheed Veteran]

  On 15/05/2014 at 15:36, Andre S. said:

Recursion provides very elegant solutions . . .

 

Although I'm aware of the inherently subjective nature of 'elegance', I would argue the exact opposite. I do see how someone could consider recursion elegant. I see it as ugly and it makes re-reading code more difficult, like when trying to understand another persons code. A methodology (or sometimes necessity) of programming being ugly in no way infers its lack of usability. I completely understand the usefulness of recursion and use it accordingly. I was simply stating that I don't like to use it when I don't have to and it feels sloppy.

[Andre S. Veteran]

Well, for example, if I had to describe the Quicksort algorithm in plain English, I would say that it consists of

1) selecting a pivot element,

2) partitioning the collection between the elements greater than the pivot and those lesser than the pivot, and then

3) repeating the procedure on each partition until the the whole collection is sorted.

Hence if I had to translate in pseudo-code: 

function quicksort collection =
    pivot := selectpivot(collection)
    lesser := takeLesserThan(pivot, collection)
    greater := takeGreaterThan(pivot, collection)
    return [quicksort lesser] + [pivot] + [quicksort greater]

This is already basically correct, except that we're missing the terminating condition, i.e. we can't subdivide the list indefinitely:

function quicksort collection =
    if collection is empty
        return collection
    else
        pivot := selectpivot(collection)
        lesser := takeLesserThan(pivot, collection)
        greater := takeGreaterThan(pivot, collection)
        return [quicksort lesser] + [pivot] + [quicksort greater]

This still reads almost like English and is obviously correct.

Well, the equivalent Python code is remarkably similar (using list comprehensions and recursion): 

def quicksort(collection):
    if list == []: 
        return []
    else:
        pivot = collection[0]
        lesser = [x for x in collection[1:] if x < pivot]
        greater = [x for x in collection[1:] if x >= pivot]
        return quicksort(lesser) + [pivot] + quicksort(greater)

How would you implement this iteratively? Try it, and I doubt you'll come back and say it was more elegant than the 8 lines of code above.

(By the way, in a real functional language, the above boils down to 5 lines of code (using F#):

let rec quicksort = function
   | [] -> []                         
   | first::rest -> 
        let smaller,larger = List.partition ((>=) first) rest 
        List.concat [quicksort smaller; [first]; quicksort larger]

[astropheed Veteran]

  On 15/05/2014 at 22:24, Andre S. said:

Try it, and I doubt you'll come back and say it was more elegant than the 8 lines of code above.

 

<ass>

lst.sort()

</ass>

 

You consider 8 lines elegant. I consider 30 lines elegant if it clearly illustrates its intent. In this case yes, it's pretty nice. I hate needing to understand the logic of recursion as it's not immediately apparent to me. I go through it like this:

 

"Ok, so if this then call it again, the parameters would now... be... this?.... Yes, I think so... which now means when it calls it... It's this? Alright how is this terminated.... Ah when this value is..... This? I think?.... gah!"

 

I'm not as strong of a programmer as you are though, this I am certain.

[rfirth]

  On 15/05/2014 at 05:18, Torolol said:

well, chess alogirthm usually demands recursion,

on games that have finites moves like othello/reversi, using recursion would usually ensure the computer would win or at least draw.

 

I interviewed at Microsoft once... and decided to implement the solutions to the problems they gave me using recursion.

 

One of the Windows developers quickly reminded me that stack space in the kernel is limited and is pretty easy to overflow.

 

Something to think about.

[Andre S. Veteran]

  On 15/05/2014 at 23:57, rfirth said:

I interviewed at Microsoft once... and decided to implement the solutions to the problems they gave me using recursion.

 

One of the Windows developers quickly reminded me that stack space in the kernel is limited and is pretty easy to overflow.

 

Something to think about.

That's what tail calls are for.

[simplezz]

  On 16/05/2014 at 02:46, Andre S. said:

That's what tail calls are for.

Can all recursive functions be converted to tail calls? Tak for example. And just because something is tail recursive doesn't mean it has predictable memory usage.

[Andre S. Veteran]

  On 17/05/2014 at 13:48, simplezz said:

Can all recursive functions be converted to tail calls? Tak for example. And just because something is tail recursive doesn't mean it has predictable memory usage.

They have to be tail-recursive, meaning any recursive call has to be in tail position. Any recursive function can be converted to a tail-recursive function if necessary in continuation-passing style. Asynchronous programming relies heavily on that technique already, where you start a long-running task and sign the rest of the operation (a continuation) as a callback.

 

Tail call optimisation avoids the problems entailed (lol) by the creation of a stack frame for each call, but it's certainly no guarantee that the function even terminates, that's still up to the programmer.