Join us and get access to thousands of tutorials and a community of expert Pythonistas.
This lesson is for members only. Join us and get access to thousands of tutorials and a community of expert Pythonistas.
Python Recursion: Pesky Details & Summary
Congratulations on making it to the end of this course! In this lesson, you’ll see a few more pesky little details. You’ll find out why you shouldn’t use list slicing and what the maximum recursion limit is.
To download the code in this course, click the link below:
To download the slides in this course, click the link below:
Congratulations, you made it to the end of the course! What’s your #1 takeaway or favorite thing you learned? How are you going to put your newfound skills to use? Leave a comment in the discussion section and let us know.
00:00 Here are some small details that you should know when dealing with recursion in Python. Python has a default call stack depth, so you can cause a stack overflow if you create too many frames.
00:11 Here’s the recursion limit.
00:15 Also, Python slicing will create new copies of a list. It is recommended to use indices instead when recursing over lists. This is because it’s not good practice to create copies of lists if there is a better way. For example, here is the naive way to sum all the numbers in a list.
00:36
If the list is an empty list, return 0, otherwise return the first element of the list plus the sum of the rest of the elements of the list.
00:46
This is a better way. We’ll define a helper function. This is a higher order function defined inside of our function that takes in the index, the start index. If the start index is equal to the length of the list, we’ve gone too far, so we’ll return 0.
01:01
Otherwise, we’ll return the list at the starting index plus the rest of the list after starting at that index, and we’ll return helper(0). It might take a little bit of time to wrap your head around the differences between these two, and I would definitely encourage you to try to type these out, put some print statements in, maybe think about some examples.
01:24 But the one on the left is not so great because we’re copying the list every time. The one on the right is a little better. That was the video on recursion, and thank you so much for watching!
tobenary on Nov. 12, 2019
Great lecture
James Uejio RP Team on Nov. 14, 2019
@lordchuffnel Thank you glad you enjoyed the video. What exactly do you mean by using other standard library methods/helpers to create same outcome?
@tobenary Thank you glad you enjoyed it!
David on Nov. 14, 2019
Thanks for the tutorial. What are some ‘real-world’ examples were developers might think of using recursion in their daily development. E.g. when trying to sort, when crunching large numbers, etc. Examples that are more concrete than “it works well for data structures or problems that can be broken into sub-problems”.
James Uejio RP Team on Nov. 15, 2019
@david You’re welcome. That is a great question and I should have went through it in the course (hopefully people will read this reply).
In terms of your examples (sorting or crunching large numbers), recursion might not be your best friend. There are exceptions, for example look up merge sort, it’s sometimes implemented recursively, but in general in industry you would use iteration to solve those problems. Here are some examples in the real world though where it would help to know recursion:
- You are looking to solve problems that deal with recursive data structures such as Linked Lists or Trees. You do not care about speed or memory. An example would be if you are looking to iterate through a file system and need to find/manipulate certain files. This is something you just need to do once and needs to get done ASAP, and you don’t care about optimizing your solution. File systems are naturally a recursive tree structure because you have folders inside folders, and your base case is a file, and so traversing through a file system is arguably much easier using recursion.
- Codebases in industry can get really really large. There might be a case where one API might call another API which might modify some data which might have a side effect of calling another API which then calls the original API. Let’s say there’s a bug… You’ll probably need to know about base cases and recursion in order to find it.
- You need to solve a problem using Dynamic Programming. This is a more advanced technique, and merits it’s own course, so don’t worry if you don’t know what it is. But for those viewers who have heard of the term, many people suggest first using recursion, then memoizing/caching your recursive solution, and then come to the Dynamic Programming solution. Trying to jump straight into the DP solution can be very difficult, so you need to know how to think about the problem recursively.
- Finally, you are solving a coding challenge for a company or have a technical interview, and the question would be faster to solve using recursion… better to have a solution than nothing! The interviewer might even prefer the recursive solution due to brevity and simplicity.
All problems that can be solved iteratively can be solved recursively (and vice versa), and as you can see it all depends on the situation.
Sorry for the long explanation, hope it helps and please let me know if you have any other questions!
sion on Nov. 18, 2019
Thank you for an excellent presentation and also for the real world notes you added for David. This has been very useful to me.
Paulo Vital on Dec. 6, 2019
Great video course @James.
I’d like to see more examples or maybe explanation about the recursion using lists which, IMHO, is the case more common to be used.
Any plan to explore more this topic?
James Uejio RP Team on Dec. 8, 2019
Hello @Paulo,
Thanks for watching! We don’t plan in the near future to explore recursion on Real Python, but here are some more examples from a course I used to help teach in college: Recursion worksheet: cs61a.org/disc/disc03.pdf Solutions + Video: cs61a.org/disc/disc03_sol.pdf Note this is a live course so those links might expire. Let me know if they don’t work.
There are also video lectures available from the Professor: www.youtube.com/watch?v=B2_8t2jyvX0&list=PL6BsET-8jgYXN1DM5Jm9qN5IxqO7_GCTh&index=2 on this topic with many examples!
Hope that helps!
Ghani on Oct. 19, 2020
Excellent course James. Thanks also for the additional explanations and learning resources offered above.
James Uejio RP Team on Oct. 30, 2020
You’re welcome Ghani!
sushubhatt on June 23, 2024
start_index is not assigned any value , still how is it getting the value in helper function?
Become a Member to join the conversation.
lordchuffnel on Nov. 12, 2019
could you please make another video using other standard library methods/helpers to show other ways of creating the same outcome with less code.
Great video, thanks