Question

Recommended Posts

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

  • 0

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]
  • 0
  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.

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

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

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

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • For anyone looking for a lightweight formatting-free text editor, I recommend Notepad3.
    • This looks really dumb, especially if it costs $100+. Noone who cares about using a flight yoke would touch that thing, people who don't care are probably fine using the analog sticks on their controller, so who is it for?
    • A) "they shouldn't be making money off of those [free videos]"?? That is literally their business model, making money off videos that users post...if you don't feel like that should be allowed, then are you saying YouTube shouldn't exist. B) Yes, the example I gave is a net-negative transaction. If YouTube makes money from others who are following their rules, it doesn't change the fact that the person using an ad-blocker is costing them money. C) YouTube has always operated at a loss...kind of invalidates your entire argument. As I always say, I don't care what you do, I will not even say you are wrong for doing it. That is purely your choice. Just be honest enough to say something like "Google is rich, I honestly don't care." Perfectly fine reason. Don't act like there is some imagined justification for why it isn't breaking the rules.
    • You can now present content from your camera feed in Google Meet by David Uzondu Google has a new feature rolling out for Google Meet that lets you directly present video from an external camera feed right into your meetings. This means if you have a document camera for showing physical papers, a dedicated external camera for a better angle, or even output from a video production tool, you can now pipe that into Meet as a presentation source. This new option supports video up to 1080p at 30FPS. This "present from camera" function offers a more integrated way to handle certain video inputs compared to some existing workarounds. For instance, it might prove less complicated than a setup with OBS Studio where you arrange your various video sources into scenes, activate the virtual camera output, and then navigate Google Meet's settings to specifically choose "OBS Virtual Camera" as your video input before you can even start presenting that customized feed. Alongside this camera presentation feature, Google's announcement also mentioned several improvements to the general screen sharing experience in Meet. Initiating any type of screen share is faster now, and video quality during screen sharing has also been sharpened, with better handling of dynamic content like scrolling text or embedded videos. To reduce interruptions, if a second presenter stops sharing their screen, any previous presentation will now automatically resume. For those wondering when they can get their hands on this, the rollout for the camera presentation feature and these screen sharing enhancements has begun for Rapid Release domains. Users on Scheduled Release domains will start seeing it from June 11, 2025. Google notes that it could take up to 15 days for these features to be visible to all eligible users. Most Google Workspace accounts, including Business Standard and Plus, various Enterprise and Education tiers, and Workspace Individual subscribers, will have access. This new presentation option joins other recent Google Workspace enhancements. For instance, Gemini in Google Drive can now summarize changes to your files, offering a quick way to get updated on what you missed in documents since you last opened them.
  • Recent Achievements

    • First Post
      James courage Tabla earned a badge
      First Post
    • Reacting Well
      James courage Tabla earned a badge
      Reacting Well
    • Apprentice
      DarkShrunken went up a rank
      Apprentice
    • Dedicated
      CHUNWEI earned a badge
      Dedicated
    • Collaborator
      DarkShrunken earned a badge
      Collaborator
  • Popular Contributors

    1. 1
      +primortal
      382
    2. 2
      +FloatingFatMan
      177
    3. 3
      ATLien_0
      174
    4. 4
      snowy owl
      169
    5. 5
      Xenon
      134
  • Tell a friend

    Love Neowin? Tell a friend!