58 posts in this topic

Posted

The partitioning was my focus because it demonstrates that recursion can be an inferior solution to a problem, as was the case in the wikipedia quicksort example.

And an iterative solution can be inferior to a recursive one, particularly if the problem is naturally recursive and writing an iterative implementations involves explicitely managing a stack that recursion manages implicitely. It is not generally the case that iterative solutions are superior, and in certain languages like Haskell, recursive solutions are sometimes the only possible solutions; in several languages, recursive solutions are more idiomatic than iterative ones.

 

I'm not disputing that recursion has a place, just that in many cases iteration can perform the same function without the worry of stack or performance issues.

These are only worries in C due to the particular semantics of C, not due to the nature of recursion.

 

*OOTB yes. Because most of the things you say C is missing are available through third party libraries or drop in code files. An example would be Sqlite, which provides database support and comes in both shared library and amalgamation form. The same applies to common data structures and algorithms, if the programmer is inclined to seek stock solutions.

Sqlite cannot compare to F# type providers or C# LINQ, to mention some actual language features that are helpful to database programming. And when I say language features that are helpful to data structures and algorithms I am not talking about libraries of ready-made data structures and algorithms, but support for abstractions such as iterators and list comprehensions to help in writing one's own implementations in a legible way.

 

1. Simplicity. There's no large API or feature set to learn.

2. Lots of high level languages are based upon it in one way or another. So what you learn in C can be applied to a large number of other languages.

3. It teaches how to manage system resources properly.

4. Because it's so powerful yet completely general purpose, you can write absolutely anything in it, from operating systems to Android apps to embedded software.

5. It has universal compiler and standard library support across all major platforms.

1. Simplicity, ok.

2. Most languages look like most other languages, and most concepts from most languages apply to most other languages, C contains relatively few concepts and even several of these don't apply in most other languages (such as its antiquated compilation model and explicit memory management), so that's not really a strong point of C.

3. Most languages have constructs for managing system resources, only difference in C is the need to do it for every single thing that's not stack-based and that's not necessarily what you want to focus on for a first programming language.

4. Lots of languages are general-purpose. Operating systems and Android apps and embedded software were written in Lisp and Java and C# etc.

5. If you're writing a device driver for some obscure router, then perhaps there's only a C compiler for that, but most platforms support most mainstreams languages in general, so that's not really an important consideration.

 

Assembly is architecture specific and features cryptic mnemonic codes that don't resemble natural language. Hardly comparable with C or other high level languages.

And C code is very cryptic when it comes to expressing concepts that it's not good at, for instance futures (which are supported by most programming languages today) would probably be a nightmare in C.

 

REPL's have their use, but they're not a replacement for a proper editor and build system. That being said, it wouldn't hurt to make them more available as you rightly point out.

Good REPL support largely negates the need to rely on a build system in the context of learning a language's syntax, playing with what the different statements do, etc., i.e. the kind of very small program that a student learning a first programming language might be doing.

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

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]

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

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.

1 person likes this

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Posted

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.