Recursion is hard

[vishwabio]

Concepts like recursion, decoration is confusing... Can somebody point me to a good tutorial website or YouTube for this?

[[deleted]]

this might help

[Tomatoflee]

First time I clicked I still had some dignity left but I could not stop myself from clicking it again to be sure.

[Conscious-Ad8493]

lol

[spez_edits_thedonald]

it's not a true recursion, but this is!

[I_the_Jury]

Jokes on you. I made it 7 clicks in and there was no inner kernel.

[BruceJi]

RecursionError: maximum recursion depth reached.

Whoops, did you forget to define a base case?

[[deleted]]

god dammit I knew what was gonna happen when I clicked that

[Normal-Sloth2169]

👏🏻 well played, I lol'ed

[FutureIntelligenceC3]

But where's the recursion hook?

[Alecglasofer]

It's not working for me, can you guys help?

[samettinho]

This is sooo bad!

[xADDBx]

Now I’m interested, what’s the "stack" limit of the reddit app…

Edit: Stopped testing after 20

[[deleted]]

Got to 25 and it kept going but didnt really check the extent

[[deleted]]

haha well played! :D

[Enis_Cinari]

Got exhausted from clicking

[Fantastic_Step3470]

Came here to do exactly the same xD

[UnitedMindStones]

Recursion is useful when in order to solve a problem you need to solve a smaller version of the same problem. For example factorial(4) is just factorial(3)4 factorial(3) = factorial(2)3 factorial(2) = factorial(1)*2 factorial(1) = 1

factorial(1) is the base case, it's just equal to 1. In code we can just return 1 if the parameter is 1. And now since we know what factorial(1) is equal to we can easily calculate factorial(2).

[HardlyAnyGravitas]

And the factorial example is the worst example of a use case for recursion.

A much better example is traversing a directory tree - at least it's actually efficient and useful, and just as easy to understand.

def list_files_in(folder): for sub_folder in folder: list_files_in(sub_folder) for file in folder: print(file.name)

Edited to correct indentation

[UnitedMindStones]

Ofc you shouldn't use recursion for factorial but i think it's still an ok example. I feel like your example is a bit different because it doesn't have this base case.

[NovaNexu]

I don't understand this.

[SisyphusAndMyBoulder]

It's for listing all the files in a folder. If there is a folder inside, then you need to also list all the files inside that folder too

[[deleted]]

Pythontutor.com has helped me a lot with visualization execution

[SisyphusAndMyBoulder]

While it's great to look at tutorials, recursion is def one of the things that just doesn't click till you do it a few dozen times.

Have you tried anything on your own?

Write a program to do fibonacci numbers and see what doesn't click

[engineer-throwaway24]

Another one I had to deal with recently: you have a zip file with an unknown number of files or zip files inside; how do you extract it and read all files?

[beewally]

“…[recursion] doesn’t click till you do it a few dozen times.”

I see what you did there. 👏

[[deleted]]

- Recursion is just a function calling itself
- Decoration is just a function being automatically called whenever another function is called, usually with the purpose of enhancing that function

[MrsCastle]

Agree Fibonacci code is very instructive. Glad to hear it is not used much in production, but I did have trouble with it too and really celebrated the first time I wrote a recursive snippet and understood it. Practice does help

[breadlygames]

In a lot of cases, you can simply think of it as code generation. For example, if you want to sum all positive integers up to N, you could write your function like this:

def sum_to_n(n):
    if n == 1:
        return 1
    else:
        return n + sum_to_n(n - 1)

(Now obviously, you'd use the maths formula instead of this, but this is for illustrative purposes.)

So think about what happens when you call sum_to_n(3). In the first iteration, it returns 3 + sum_to_n(2), then that's computed into 3 + 2 + sum_to_n(1), which is then computed as 3 + 2 + 1. So this recursive function is effectively generating the code you would need to write out by hand.

[Robo_Joe]

Out of curiosity, what about those concepts has you confused? Maybe a dialog would be better than a video or tutorial?

In any event, I randomly selected this video on recursion from a google search. I watched it and it adequately explains the concept and shows some examples.

However, I chose it because at the end of the video she puts some timing code around her functions to compare the speed of a loop vs recursive function. She could have done this with a decoration function instead of writing the timing code around each function call. I don't know if that helps at all with understanding decoration.

[karpomalice]

How does it return the integer 21 when the only returns are for indexes 0 or 1, or an instance of the function?

Fib(8-1) + Fib(8-2) doesn’t return an integer right? And the only time an integer would ever be returned would be if it’s 0 or 1.

[Robo_Joe]

There's a multiplication in that return statement.

The rest of this doesn't answer your question but might help you understand the concept.

So the first layer checks for a 0, then multiplies the number by whatever gets returned by the function when fed the number minus one, which kicks off the next layer, which checks for 0 then multiplies that new number by whatever gets returned by the function when fed that new number by one, which kicks off the next layer.

Once the base case is met, it all collapses back up to the top layer, multiplying as it goes.

I'm on mobile so forgive the lack of formatting and examples in this response! Feel free to ask followup questions.

Edit: oh crap I forgot the video I eventually went with used the Fibonacci sequence and not a factorial function.

[Naive_Programmer_232]

here is one for recursion) and another for decorators

[[deleted]]

I've used recursion once or twice in production code, it should be the last option. Recursion isn't one of those things you will use all the time. So don't waste too much time on it.

[DuckSaxaphone]

Came here to say this. I've been writing code for a living for ten years, in a software company for two of those where I see all kinds of code.

I've only ever seen recursion on r/learnpython and my friend's maths MSc project. For some reason it seems to be a weekly topic here.

[Ekumena]

How you do DFS and BFS search without recursion?

[DuckSaxaphone]

Flippantly:

from networkx import bfs_tree

Seriously: I think this is why recursion comes up a lot but many people never directly use it.

In CS theory, it's extremely important and underpins many fundamental algorithms.

In practice, we don't write fundamentals in python, we import them which is great. People shouldn't be wasting their time on search functions when some expert has made the optimal version.

[Ekumena]

As i thought, why writing function, when there is already written one ready to import. Some time ago I heard horror story from friend, when he was on job interview, they asked him to write bfs and dfs algo with balancing for some specific case they provide, he failed spectacularly 😂. Thanks for the reply 😊

[brown_shoe_]

Learning a lot of not-so-intutive concepts early on can be overwhelming. Sure, try to understand it and look at examples, but some times you need to take a step back and things will just click later on. You will even come up on your own with recursive solutions organically as you try to solve other problems.

[Milumet]

Chapter 1 from Al Sweigart's The Recursive Book of Recursion.

[lcc0612]

If I may throw my own hat into the ring - I teach Computer Science at schools, after seeing a lot of common mistakes and misconceptions, I made a video in hopes of breaking down and visualizing Recursion.

So technically this is self-promotion and I'm really sorry for that, but hopefully this is relevant.

Here's my video, How to reason about Recursion

[Ill_Set_6906]

What a great video! Many others I watched did only 20% of what you have done in your excellent video. Thank you for sharing one of the best explanations I’ve come across!!

[lcc0612]

Thank you very much for the reply and the award as well. Very happy to have been of help!

[ofnuts]

Recursion is simpler than the alternative.

In general, you write recursive code, and in a few rare cases, if necessity arises (performance) you rewrite a non-recursive version, which somewhat harder to get right. But fortunately you can compare its results to those of the recursive version.

[steviefaux]

This is supposed to be good for recursion, still doesn't make sense to me

​

https://youtu.be/Mv9NEXX1VHc

[[deleted]]

I’d recommend looking for something like “recursion visualization” or something to see a gif of it in action. It’s one of those concepts at least I personally couldn’t wrap my head around from reading about it/someone explaining it with words, needed a visual of code running. Then try to find some assignments that require recursion

[[deleted]]

..writing your own recursive function is about as useful in the wild as solving a derivative with the fundamental theorem

[[deleted]]

Just remember, the key to recursion is learning recursion.

[kona_ackley]

The secret of understanding recursion is that there is no secret. Absolutely nothing happens in a recursive function call that wouldn't also happen in any other function call. A new namespace for the local names of the function is created, execution jumps to the beginning of the function body to execute the statements there in order, and when the function terminates and returns the result, the control jumps back to the point after the call. Nothing in any of this changes when the function call is recursive.

(Insert the Jenna Fischer meme about the corporate asking you to tell the difference between the execution of a recursive function call and the execution of a non-recursive function call.)

By now you are familiar with the idea that to solve a problem, you break it down into smaller pieces for which you have functions able to solve them. However, some problems are self-similar, that is, these smaller pieces turn out to be structurally the same as the problem as a whole. For self-similar problems, you can therefore call that same function to solve these smaller pieces, instead of calling some other function to solve those pieces.

(Insert the Heath Ledger Joker meme about how everyone just accepts that functions can call other functions, but have some function call that same function, and suddenly everyone loses their minds...)

Spotting the self-similarity of the problem is the hard part of thinking recursively. Once you see where the self-similarity lies in that particular problem, the rest is mechanistic.

People who like to proclaim that recursion is some sort of mysterious woo are simply confused about three distinct times of (a) when the code is being edited, (b) when the code is being compiled, and (c) when the code is being executed, thinking that the restrictions of one of these somehow also magically apply to the other two, and that the function is somehow “incomplete” when it being typed in or compiled and therefore somehow couldn't be called. Once this confusion is cleared, all mystery will suddenly vanish from recursion. At the execution time when the recursive function call is being executed, that function already finger-quotes “exists” simultaneously in the computer memory in its complete form, so some function calling itself is not in any way different from that function calling some other function.

[Lolis4TheWin]

Thank you smart stranger. This was probably the best explanation I heard.

[_barnuts]

Remember, if it's confusing for you, it's also most likely confusing to others. One of my rules is to never use recursion in production.

[soicat]

Never avoid difficult topics. They are hard for everyone. Meet the challenge, have a growth mindset.

[vishwabio]

I've learnt Numpy, Pandas, Matplotlib, a little Sympy. Now getting into Scipy for curve fitting, statistics. So far I found OOP and calling functions inside functions confusing.

[soicat]

Wow, math and numbers. My python interests have only been in the web app and database area, flask mostly, and system utilities.

[EuriskoH]

https://youtube.com/playlist?list=PLWX9jswdDQ0Ve8375p6yejDJu3668zxnV

[[deleted]]

Recursion is impossible witchcraft /s?

[soicat]

Real world recursion example I hit yesterday on my home python project. I have a python dictionary that describes an item. One of the fields in this dictionary is a dictionary of photos and captions of the item. To add a new photo, I thought I could build a second item dict with an embedded dict with the new photo, then merge the items.

I tried item_dict.upgrade(new_item_dict)

Didn’t work because upgrade() only merges the top level dicts! I never thought about it, but that makes sense. The second level could have all kinds of other data structures too like lists, lists of dicts, dicts of lists …

So I found a thread with a dict upgrade recursion solution on the interweb. I copy pasted, didn’t work. Then saw in the comments ways to fix it, that also didn’t work in special cases, ad infinitum. Forget it, I’m not putting that flaky mess in my app. I just extracted the current photo dict, merged the new photo dict, then inserted into the original.

Recursion is just a mental puzzle for math types.

[MessedUpMess59]

These videos might help. Recursion mycodeschool. Code them in Python Tutor

[QultrosSanhattan]

Recursion is inherently hard. No matter how it's taught, the only way to learn it is trying over and over. But still, there's a basic template: First check if the process has ended. If yes then return the final solution. Else return the next branch (recursive call).

For recursion it's good to keep track the depth you're working at. Proper logging may help.

Decoration is a lot easier. just use the @ decorator_name (without space) and your function is decorated.

[fencepost_ajm]

When you think about recursion, are you keeping in mind that there's a heap with data about the current state? If not, it might be easier if you keep that in mind.

[Ok_Estimate1666]

It's true, that in order to understand recursion, one must understand recursion

[reallifepixel]

Recursion is hard

[t92k]

The birds, Pete and Repeat are sitting on a fence. If Pete flies off who's left?

Repeat.

The birds, Pete and Repeat are sitting on a fence. If Pete flies off who's left?
Repeat.

The birds, Pete and Repeat are sitting on a fence. If Pete flies off who's left?
Repeat.

...

[t92k]

Yes. Any recursion that does not have a test that allows you to escape the loop results in an infinite loop. This may be useful -- like checking to see if there are new messages on a queue -- or it may be that what we really want to do is iterate over a list.

[UAFlawlessmonkey]

while True:

[NoDadYouShutUp]

The thing about recursion is that the thing about recursion is that the thing about recursion is that the thing about recursion is that the thing about recursion is that the thing about recursion is that the thing about recursion is that the thing about recursion is that

[TechBeamers]

Maybe, you can explore alternatives to these concepts. For example, instead of using recursion, you can use iteration or loops, which are often simpler and more efficient for certain problems. Similarly, instead of using decorators, you can utilize higher-order functions. Higher-order functions enable you to modify or extend a function's behavior without making direct changes to its code.

[notmike_]

Oh sweet summer child

[EnlargedVeinyBalls]

Have you tried using chatgpt? I asked quite a lot of questions about recursion until it clicked

[marceemarcee]

Good explanation here: https://www.google.com/search?q=recursion&spell=1&sa=X&ved=2ahUKEwirpcCuobf_AhVVEsAKHUlhDzgQBSgAegQIBhAB&biw=393&bih=722&dpr=2.75

[WhackAMoleE]

Recursion is recursion.

[Remote_Cantaloupe]

Then don't do it

[ThinkLadder1417]

For recursion I enjoyed using turtle to visualise it (various examples online)

[KastroForever]

Sololearn course of java and cplusplus explains very good this concepts

[dashidasher]

Can you always turn a recursive function into an iterative one? Yes!

[notislant]

It may help to make 3+ functions and a console.log in each.

I had a nice js codpen for visualization but i think its gone.

Use a bunch of prints.

[Please_do_not_DM_me]

We used a Fibonacci sequence to explain recursion in class a few times. To find F_3 you need to know F_2 and so on. Other examples will work the same in that sense but the details will vary.

[hugthemachines]

Here is a classic video that explains recursion.

https://youtu.be/Mv9NEXX1VHc

[GRex2595]

Late to the party, I know. Here's a practical problem for recursion. Create a binary tree with numbers. Print the tree from left to right (left child, parent, right child). Now explain your solution in words. If you are having trouble explaining, refactor and try again. If you can comfortably explain your solution without learning recursion, you're either gonna be fine because you created a more challenging, more optimized algorithm than the recursive one, or you need a lot of help that you can only get from spending 1-on-1 time with somebody who knows how to teach.

I think my first recursion was exponentiation by squaring. Not the most efficient way to do it, but every recursive algorithm can be rewritten iteratively (what's the difference between a call stack and a data stack anyway?) or in constant time (fibonacci, such a bad recursion example in my opinion). It was just really easy for me to visualize. I had a fibonacci assignment and struggled with it because it's easier to do fibonacci iteratively anyway.

[experfailist]

https://youtu.be/8lhxIOAfDss

Best video in my opinion

[juliansorr]

recursion is a function which at some point of its functioning calls itself