Recursion 'Super Power' (in Python) - Computerphile

Recursion can be tricky to grasp. Professor Thorsten Altenkirch uses Python to demonstrate an example taken from his latest book.

This video was filmed and edited by Sean Riley.

[chunchunmaru]

A bit of trivia - the Python recursion limit is actually artificially implemented to prevent bad coding practice and on it's own doesn't cause a stack overflow.
Lets say we run this code:


def foo(x):
foo(x)


foo(3)


It will give us a recursion error after running around 1000 times (Pythons built in recursion limit).
Now try this:


import sys



def foo(x):
foo(x)


foo(3)


Instead of a recursion error, this one runs a bit longer until it returns a SegmentationFault (core dumped) error.


This is all because Pythons recursion limit of roughly 1000 doesn't cause a stack overflow and is only implemented to prevent bad coding practice, using sys module you can make the limit much higher until you cause an actual stack overflow (the SegmentationFault).

[mateja]

"It's like a super power, ja?". It's always nice to hear that.

[SergeMatveenko]

In order to understand recursion you need to understand recursion.

[isaactfa]

It kills me that he'll put a space before a colon, but not around operators or after commas.

[wellreadbull]

The skills, the looks, the accent... Prime movie villain material!

[amauta]

This video made me learn Python. Today, I have built a specific calculator for work and a document generator, albeit simple. Thank you. I still feel i know very little, but i am looking forward to continue learning.

[davidkim]

i love how everyone on Computerphile has a great sense of humor and they're charismatic as well

[Larbydarg]

Recursion is a magic spell and stack space is its mana.

[jellevanbrandt]

I do not understand anything, but I was satisfied when he moved the last disc from B to C.

[giannotti]

1:09 Of course, Prof. Altenkirch brushed up on his game beforehand with "Conceptual Programming with Python" (by Thorsten Altenkirch) XD

[pmcate]

This seems so magical! In every introduction to this game it is made clear that you cannot put a smaller disc on a larger one. But here we have no explicit mention of that!

[mlguy]

"I will leave the robotic arm as an exercise"

[cawsha]

I once found a recursive function call in an exception handler in C#. In the catch it waited 5 seconds and then called the same function again with the same arguments. Genius!

[CatzHoek]

I'm not going to read all comments but i just want to make sure you guys appreciate his shirt. It's absolutely marvellous. And this absolutely dry german manner when he delivered the jupiter joke, i love it.

[hoplahey]

I have used recursion two times in my programming life. Once when I learned recursion using the tower of hanoi example in class. The second when I wrote my thesis, and in the x-reference section I wrote; Recursion, see Recursion.

[buxt-tech]

I am disappointed with the lack of f-strings!

In all seriousness, always love seeing Prof Altenkirch! Excellent, simple video illustrating a powerful tool.

[jej]

Any recursive algorithm can be implemented nonrecursively using a stack. I learned that 25 years ago in an undergraduate computer science course.

If you use a recursive algorithm, you are in effect just using the built-in stack managed by the compiler / interpreter.

[vadrif-draco]

Is it weird that I understood recursion but not how the solution to this puzzle works?

[Vaaaaadim]

There is a way to do Towers of Hanoi without recursion, but doing this problem with recursion is insanely easy, and figuring it out non-recursively takes a wild insight I think.


Anyways, 3Blue1Brown made a video about how you can use counting in Binary to solve Towers of Hanoi. Titled "Binary, Hanoi and Sierpinski, part 1".

[mohammedsharikuzama]

This was supercool! My professor just copied the code and explained. Now, I understand the power. And, I really love his carefree nature and his accent.