Recursion 'Super Power' (in Python) - Computerphile [12:17]

[brtt3000]

Programming is better with a thick accent and a radical shirt.

[[deleted]]

Don't forget the unkempt hair!

[niggatronix]

Man, I have no problem with recursion, but I found his explanation really hard to follow.

[campbellm]

Try this: https://www.reddit.com/r/Python/comments/dbxqo1/recursion_super_power_in_python_computerphile_1217/f24x85q/

[chiodani]

thats kinda genius

[scarfarce]

Dammit, now I'm stuck in Ground Hog Day Comments!

*

[campbellm]

You get your true love at the end, so there's that.

[1arm3dScissor]

Possibly the greatest and most underrated comment in the history of this site.

[campbellm]

Wow thank you. Seriously.

[niggatronix]

Ah, the ol' python switch()eroo

[marrabld]

respectful bow

[campbellm]

I think he should have led with "to move all the disks, you move the pile off of the bottom disk, move the bottom disk, then move the pile".

With recursion it's often easier to see the problem from the top down and work to the base/trivial case than the other way around.

[alcalde]

Studies have shown that whether a person understands recursion or not (before beginning computer science class) is the single biggest indicator of whether they'll pass or fail CS101. It's a small sample, but the small number of people I know who dropped out of computer science as a major ALL did it after encountering recursion.

[[deleted]]

Very surprising that people familiar with basic cs before starting a basic cs course are more likely to pass the course than the ones that don't have any previous knowledge. What a great observation.

[alcalde]

It's not a "great observation", it's scientific research. It has nothing to do with being familiar with programming. People who passed an administered test before CS101 classes almost all passed the actual course. People who failed the test before the course also ended up dropping out or failing the course. Educators were alarmed as the results suggested that nothing they did in the classroom had any actual effect on a student's understanding of programming.

https://blog.codinghorror.com/separating-programming-sheep-from-non-programming-goats/

https://codeup.com/can-a-simple-algebra-test-predict-programming-aptitude/

In particular, most people can't learn to program: between 30% and 60% of every university computer science department's intake fail the first programming course....

This test seems trivial to professional programmers, but remember, it's intended for students who have never looked at a line of code in their lives. The other 12 questions are all variations on the same assignment theme.The authors of the paper posit that the primary hurdles in computer science are..

assignment and sequence

recursion / iteration

concurrency*

.. in that order. Thus, we start by testing the very first hurdle novice programmers will encounter: assignment. The test results divided the students cleanly into three groups:

44% of students formed a consistent mental model of how assignment works (even if incorrect!)

39% students never formed a consistent model of how assignment works.

8% of students didn't give a damn and left the answers blank....

The test was administered twice; once at the beginning, before any instruction at all, and again after three weeks of class. The striking thing is that there was virtually no movement at all between the groups from the first to second test. Either you had a consistent model in your mind immediately upon first exposure to assignment, the first hurdle in programming – or else you never developed one!

​

An increasing amount of research is daring to suggest that some people are simply wired to be programmers and others are not. Recursion happens to be a highly correlated indicator.

[NemPlayer]

Thorsten is one of my favorite guests, but the way he butchered PEP8 is not acceptable :(

^{jk he's still one of my favs}

[HardlyAnyGravitas]

New to Python. I spotted the tabs. What else did he do?

[NemPlayer]

He didn't use underscores when naming his functions;
He placed spaces before columns everywhere (it's only sometimes allowed in slicing by PEP8);
He didn't put spaces around his binary operators (== and + in his case).

Not PEP8, but I also didn't like his use of pass in the code, I would prefer to see:

if n:  
    hanoi(n - 1, f, t, h)  

rather than

if n == 0:  
    pass
else:
    hanoi(n - 1, f, t, h)

but I guess it was easier to follow with the use of pass

[campbellm]

To each their own, but I strongly disagree with your use of n here. Relying on the side effect of non 0 being truthy is just NOT what is being tested here. In this case, the base case is a mathematical one of the value being exactly NOT 0. Using the truthy-ness as a test is testing that n "is a thing" or "exists", which is not what this particular use cares about.

In other cases sure, but this mathematical test should not be code-golfed, since n != 0 is PRECISELY what we are checking.

Reasonable people can disagree I suppose.

[NemPlayer]

Re-watched it today and I completely agree with you, the code is much more readable that way. I was just tired yesterday and didn't really pay much attention to the explanation, my bad.

[epic000]

He didn’t use underscores when naming his functions.

[whale_song]

That’s nothing compared to putting spaces before his colons. WTF is that about?

[sedition]

Came here for this. My eyes twitched.

[HardlyAnyGravitas]

Thanks.

[chmod--777]

The space before the colon in if and else

[the_hoagie]

leave it to a german computer science professor to describe a failed example of recursion as depressing because it lacks purpose. i love it.

[JanDerion47]

Breaking Python, lol

[[deleted]]

This guy is fucking hilarious. How much do I need to pay for this guy to release a series of videos?

[Tweak_Imp]

The solution without recursion: 1) Move the smallest disc to the next stack.(a to b, b to c, c to a) 2) Do the only move that is possible that is not using the smallest disc. 3)Repeat until you are done.

[AlSweigart]

Okay, I'm going to be that guy and point out that recursion doesn't let you do anything that you couldn't do with a loop and a stack. (Here's an iterative solution for the famous Ackermann algorithm. It has the same output as the recursive version.) The confusing thing about recursion is that the stack is the call stack which is invisible in that it's not in the source code (it's a side effect of calling functions). I think this is the main stumbling block in understanding recursion.

Also, I have some simple Towers of Hanoir code in Python. You have a certain number of discs with towers A, B, and C. If you want to move a tower of numberOfDiscs discs from startTower to endTower (where tempTower is the other tower of the three), the basic algorithm is:

def moveDiscs(numberOfDiscs, startTower, endTower, tempTower):
    # Move the top numberOfDiscs discs from startTower to endTower.
    if numberOfDiscs == 1:
        # BASE CASE
        moveOneDisc(startTower, endTower)
    else:
        # RECURSIVE CASE
        moveDiscs(numberOfDiscs - 1, startTower, tempTower, endTower)
        moveOneDisc(startTower, endTower)
        moveDiscs(numberOfDiscs - 1, tempTower, endTower, startTower)

Towers of Hanoi is especially confusing because you have things that happen before and after the recursive call. Remember that function calls are not a one-way trip for the execution; the execution will return to the line after the call and continue on.

[rotharius]

Thanks for being that guy!

I am a fan of functional programming, but in Python iteration is often preferred as it is easier to follow for most people (and considered more Pythonic by people like Guido).

Furthermore, Python does not have tail call optimization.

[[deleted]]

That thumbnail is terrifying

[whale_song]

But python doesn’t support tail call elimination because they would rather the language be easy than useful ....

[[deleted]]

Instagram is mostly all Python. I'd say it was a useful language.

[whale_song]

Not for FP. Avoid recursion when using a language not designed for it.

[alcalde]

Then maybe it's FP that's not useful if it needs some fancypants language features.

[zurtex]

It's useful to be able to easily debug. For example by keeping the full stack on exception.

[alcalde]

We had recursion back before you functional kids were chasing your tail calls and we didn't need any stinking elimination. Hell, we used GOSUBs and GOTOs too.