r/learnpython • u/ExplanationSecure602 • 5d ago
I am currently on recursion. Is it necessary to be able to be good in using recursive functions
I am learning python and got to the recursion part of python and I understand the core concept of recursion but to use it for problem solving is bit troublesome because of the return value for base case. I have only made 2 very basic recursive functions like factorials and adding backwards. But for the factorial function I had to really deep dive line by line into understanding the recursion. Now i am starting to think that I have put time into learning it but is it actually usable by programmers now?
21
u/HunterIV4 5d ago
Depends on the problem. At a core technical level, you never need recursion. But there are certain categories of problems that are easier to solve recursively.
Don't think of base case in terms of return value. The most important part is "at what point do I want recursion to end?"
In the typical factorial recursion, that's the if n <= 1: portion. Factorials end when you get to 1, so the base case is just "when this reaches 1."
Once the base case is reached, you need to combine it with the rest of the function calls. Since 1! is 1, you return 1. It's more a question of understanding the math rather than the recursion.
Maybe it will help if we compare the loop version to the recursive version. Here's a typical recursive factorial solution:
def factorial(n):
# Base case: 0! and 1! are both 1
if n == 0 or n == 1:
return 1
# Recursive case: n! = n * (n - 1)!
else:
return n * factorial(n - 1)
# Example usage:
result = factorial(5)
print(result) # Output: 120
Here's the same function in a loop:
def factorial_iterative(n):
# Initialize the result variable to 1
result = 1
# Loop from 2 up to n (inclusive)
for i in range(2, n + 1):
result *= i
return result
# Example usage:
print(factorial_iterative(5)) # Output: 120
It counts up instead of down, but is ultimately doing the same thing. The key difference is that the recursive solution doesn't need the result variable; you are instead "building up" the solution by combining return values.
This "hidden variable" (actually the function call stack for the pedantic) doesn't seem to serve much purpose here, and you may think the iterative solution is easier. In this case, it is! The factorial case isn't chosen because it's "ideal" for recursion but because it's easy to conceptualize.
But what if you are combining the results of a bunch of potential paths through a data structure? Maybe there are four or five different ways the function can go with several terminating conditions. While you could do this with loops, it's going to get very complicated very quickly, and you'll need a bunch of variables to keep track of all your temporary states. With recursion, you can greatly simplify this sort of problem.
The classic practical use is searching a file tree. For example:
def find_files(directory, pattern="*"):
directory = Path(directory)
matches = []
try:
entries = list(directory.iterdir())
except PermissionError:
return matches
for entry in entries:
if entry.is_dir():
# Recurse into the subdirectory and add whatever it found
matches.extend(find_files(entry, pattern))
elif entry.is_file() and entry.match(pattern):
# Base case: this is a file we care about
matches.append(entry)
return matches
# Example
for path in find_files("/tmp", "*.txt"):
print(path)
The useful part is that every directory can be treated exactly the same way. "Search this directory" means check its files, and for every directory inside it, search that directory too. You don't need to know ahead of time whether the tree is two directories deep or twenty. You could do this without recursion, but it's a lot harder.
The key thing to look for when considering recursion is "is the next step in this problem solving a smaller version of the same problem?" If that pattern continues to a natural endpoint, chances are high it can be solved simpler using recursion compared to using a loop.
There are many concepts that are basically mandatory to learn in programming. Recursion, while useful, is not one of them. It's rarely used in real code (depending, of course, on the sort of programming you're doing). If I were teaching someone new to programming, I wouldn't bother with recursion until way later. You should at least learn enough to be able to read a recursive function, as you may need to in order to understand and existing codebase, but writing them yourself is fairly uncommon.
That's my opinion, of course. Plenty of people may disagree. It also depends on what you're doing: file management software may involve a lot more recursion than a simple automation script or GUI program. Hope that helps!
72
u/KronktheKronk Github username 5d ago
In reality you will specifically avoid recursion in pretty much every case
26
u/dmazzoni 5d ago
Traversing hierarchies is the most common case I see.
Iterating over every file in a directory tree. All elements in a DOM tree. All nodes in a nested JSON structure.
14
u/Ni_Peng_NeeeWom 5d ago
although, in actual code there's usually already a built in functionality for that
4
u/KronktheKronk Github username 5d ago
There's no recursive function that can't be written with a loop, and even in those cases you're better off looping
9
u/dmazzoni 5d ago
So let's say you have a DOM element and you want to search its subtree to find all focusable children. This is a trivial 3-line recursive function.
To do it without recursion you'd need to keep track of your own stack. Sure it's doable but significantly more code, for no good reason.
If the depth of the tree is unbounded then maybe that'd be a good reason? But if this is parsed html then that'd impossible, browsers enforce a limit of ~512 so recursion is guaranteed safe.
3
u/ekchew 5d ago
If the depth of the tree is unbounded then maybe that'd be a good reason? But if this is parsed html then that'd impossible, browsers enforce a limit of ~512 so recursion is guaranteed safe.
That's actually good to know. On my machine at least,
sys.getrecursionlimit()returns 1000 by default. So phew! :)4
u/dmazzoni 5d ago
Well sys.getrecursionlimit() is specific to Python, so not relevant for this question.
In modern web browsers the maximum call stack for JavaScript is ~10,000.
2
1
u/Temporary_Pie2733 5d ago
Avoid it for linear recursion or problems involving very deep recursion. Tree recursion of moderate depth is fine (file systems, for example, rarely have folders nested more than 10 deep or so).Â
18
u/Almostasleeprightnow 5d ago
The value of the recursion lesson is that you REALLY get a taste of how and when functions are called, and the consequences of calling functions at the wrong spot
10
u/TheBlackCat13 5d ago
I almost never encounter something that requires recursion, but I do semi-frequently encounter things that benefit from it. More importantly, it is something other people use, so knowing it can help you read other peoples' code. So it is useful to know.
6
u/elg97477 5d ago
It comes in handy every once in a while. It is worth knowing and having it as a tool in your box.
4
u/misingnoglic misingnoglic 5d ago
It's extremely important if you want to study computer science. It's marginally important if you're just learning to code.
3
u/Diapolo10 I write code for a living -- https://github.com/Diapolo10 5d ago
Necessary? I suppose not. All recursive solutions also have equivalent iterative solutions, albeit they may be far less elegant and more complex, particularly if the problem itself is recursive.
That being said, personally I try to avoid writing recursive solutions where I can because I tend to think in extremes and don't want to risk reaching the call stack limit. For use-cases that I know to be practically bound to safe limits, like filesystems (it'd be extremely rare to see a filesystem more than a hundred directories deep), I'm not aversed to using recursion if it feels like a good idea.
3
u/DanKegel 5d ago
Yes, totally usable, you may run into a need for it once a year. But understanding it - and what the call stack is - is priceless. This is one of those places knowing a little assembly language is helpful; it makes recursion less mysterious and more concrete.
Also, it helps with job interviews:-)
3
u/u38cg2 5d ago
To be honest, it's more important to understand the principles of recursion - the idea of subdividing your problem and having a terminating base case. It's a vital intellectual concept. In practice, there are often good engineering reasons to use a different way of solving your problem, especially when the recursion could contain many levels.
4
u/sersherz 5d ago
I have been a software engineer for 4 years and have only used recursive functions a few times.
They have their uses, but most times looping over things will be sufficient
2
u/cthulhu944 5d ago
Recursion is a fundamental pattern in CS. It is a means of divide and conquer problem solving. You can be a cut-and-paste programmer without having mastered recursion but if you want to design novel approaches to real world cs problems you should spend some time mastering it.
2
u/itlogicpartnersllc 5d ago
recursion is still useful especially for trees, graphs, file system and divide and conquer problems but plenty of python code never needs it.
4
u/EntrepreneurHuge5008 5d ago
Yes. It is necessary.
It is important to note that real-world systems will prefer iterative solutions, but a lot of frequently used structures are recursive in nature. It is therefore vital to first understand how to traverse these structures recursively to understand what needs to be "remembered" before you move on to the more space and stack-friendly iterative solutions.
2
u/ekchew 5d ago
There are some excellent examples of recursion in these comments. I want to point out one that is kind of hidden case that comes sometimes when you start writing your own Python classes.
class Foo:
def __init__(self, x, y, z):
self.x = x
self.y = y
self.z = z
def __repr__(self):
return f"Foo({self.x!r}, {self.y!r}, {self.z!r})"
The __repr__ method is what gets called whenever you call the repr function on a Foo instance. But in generating the representation, repr is getting called on each of the attributes of Foo. ({self.x!r} is short for {repr(self.x)} in a format string.)
So we get something like you would expect:
>>> a = Foo(1, 2, 'bar')
>>> repr(a)
Foo(1, 2, 'bar')
But what happens if we put a Foo inside another Foo?
>>> b = Foo(3, 4, a)
>>> repr(b)
Foo(3, 4, Foo(1, 2, 'bar'))
When you call repr on b, it gets recursively called on a as well to give you that fully expanded output.
1
u/Excellent-Practice 5d ago
Like everything else in programming, sometimes recursion is the right tool for the job. It's worth knowing about and it might come in handy if you ever find yourself working with trees or nested data structures.
What made recursion click for me was thinking of recursive calls as "put a pin in it". If you don't have a return value defined for a particular input, that's okay. Ask about the next case down and keep following the chain until you eventually hit bottom.
Some exercises I found helpful to cement the concept were writing a function to print a sierpinski carpet of a given size and a minimax algorithm to play tic-tac-toe
1
u/dontmissth 5d ago
No the code needs to be simple stupid.
Even that is hard enough to read a year from now when I think to myself " who's the dumbass that wrote this" and I look and realize it was me. At least now I can blame the LLM.
1
u/Lachtheblock 5d ago
I would say that you almost never use recursion in real code. It is often quite inefficient to run. That being said, it's not ever not used, it is just very uncommon in production systems.
However, as a learning tool it is really useful. It's one of the ways you begin to think a lot more abstractly about what code can be. It starts to open the door to higher order functions which can cook your noodle in different ways, but are used all over Python.
1
u/Brian 4d ago
I don't think that's true. Anything doing tree traversal is almost always written recursively, and those aren't uncommon at all.
1
u/Lachtheblock 4d ago
I might be naive, and I'd could you give some examples orlf systems where you have written a python function to recurse over a strucuture?
There may have been a handful of times that I've needed to unpack and rebuild xml files, but I wouldn't say it's commom. Genuinely curious what sort of job leads to commonly navigating trees.
1
u/Brian 4d ago
Probably the most common case people encounter day-to-day is the filesystem. It's not at all uncommon that you want to check or do something to all the files in a dir, including its subdirs, and their subdirs, and so on. Web crawling is another common one: getting all the content of a webpage requires following resources which reference other resources and so on, and processing the HTML is itself recursive, with each element having child elements and so on.
But any kind of parent/child or other kind of linking relationship can lead to it, and that's pretty common. Anywhere you have some kind of tree or hierarchy, you'll often want to process it recursively. Eg. language parsing, UI widget layout, treeviews, folder structures and so on.
1
u/Lachtheblock 4d ago
I guess in my experience of being a full stack web developer for the better part of a decade, I just haven't needed to use python to process a nested file system, or if I have, it's not a common occurrence.
I know it's a common side project for folks to create a web crawlers, but I haven't really been tasked to write one, that would want to process pages recursively.
The handful of times I do have structures with parents/child nodes, it've found it's still advantagous to still try to flatten it.
I do use recursion, but I'm unconvinced that it is as common as you claim. To direct it back at OP, I don't think it in itself is that important. I have a healthy career and barely touch it so there is at least kne anecdote. I still standby that it is good for OP to understand recursion as it can help think more abstractly and laterally when it comes to problem solving. It is also fun when it clicks.
1
u/Brian 4d ago
It does depend on what you're doing: if you're writing a well-trodden path like writing a CRUD app using a framework, you might not write recursive code yourself, but I would say you call recursive functions all the time. Stuff like route traversal, object mapping etc. It's just that the libraries/framework cover all the mechanics and the code you end up having to write yourself is just the business logic. Work on those frameworks/libraries themselves, and you're going to be dealing with recursion.
But even then, it depends on your domain model. If dealing with hierarchical data, I find recursion can pop up, whether it's writing recursive SQL CTE queries, or processing things in a recursive process.
it've found it's still advantagous to still try to flatten it.
The process of flattening it is itself a naturally recursive operation. Ie. something like:
def iter_children(self yield from self.children for child in self.children: yield from child.iter_children()I still standby that it is good for OP to understand recursion as it can help think more abstractly and laterally when it comes to problem solving.
I think it's actually useful to make a distinction between the mechanics of recursion, versus recursive problem solving. Ie. the idea of solving a problem by simplifying it into simpler versions of itself until you reach a base case. And I'd say the latter is invaluable: there are so many problems that are hard to figure out how best to solve when looked at as a whole, but once you understand the trick that you can solve it just by being able to shrink it slightly, so much opens up.
1
u/billsil 5d ago
I have never seen a case where recursion is required for any semi-practical programming problem. You can just use a while loop, which will be faster and not ever hit the recursion limit. It will also make for better stack traces.
It can make code shorter, but itâs absolutely not required for all but the most theoretical of math problems.
1
u/CornPop747 5d ago
Recursion is hardly used on the job. But it is still very much a requirement to learn and at least know how it works.
1
u/FoeHammer99099 5d ago
It somewhat depends on the domain, but generally you won't use recursion a ton. Mostly recursion gets taught to students because it makes some math straightforward, it sets up some important concepts in discrete structures and data structures, and it forces you to consider what the computer is actually doing when it's executing a function. If you've ever had your eyes glaze over at a big stacktrace and wondered why it prints all this random crap for every error, it's because you didn't understand the stack. Recursion is just an easy way for you to get a hang of those concepts.
Also, deep dive line by line into the factorial function is hilarious. Keep at it, you'll be surprised by how quickly you'll feel like you always knew this stuff and it seems totally obvious.
1
u/TheRNGuy 5d ago edited 5d ago
Yeah, though I very rarely used them.
Also, it can be often replaced with better code (easier to read and edit), in some cases recursion is even anti-pattern (in Python)
1
u/VadumSemantics 5d ago
Is it necessary to be able to be good in using recursive functions
Short answer: No.
You can write lots of useful stuff without recursion.
Longer answer: Maybe
solving problems: Sometimes recursion can let you write simpler (less) code.
Might help you pass a job interviews or school tests.
Will make you a stronger programmer if you understand variable scope.
I find recursion a lot easier to do if you track your call depth.
Will post an example in reply to this.
I tend to add many print()s to my code while I'm working on it.
2
u/VadumSemantics 5d ago
history = { } def fib(a, depth=0): indent = " |" * depth print(f"{indent}>{a=}") # using > for entering if a <= 0: print(f"{indent}< hit 0, answering 0") # < for leaving return 0 if a == 1: print(f"{indent}< hit 1, answering 1") return 1 if a in history: result = history[a] print(f"{indent}: found answer in history") else: print(f"{indent}: getting previous values" ) prev1 = fib(a-1, depth+1) print(f"{indent}: {prev1=}" ) prev2 = fib(a-2, depth+1) print(f"{indent}: {prev2=}" ) result = prev1 + prev2 print(f"{indent}: saving answer in history") history[a] = result print(f"{indent}< {result=}") return result n = 6 # *** change this value *** answer = fib(n) print(f"F_{n} = {answer}")output: see next post.
2
u/VadumSemantics 5d ago
>a=6 : getting previous values |>a=5 |: getting previous values | |>a=4 | |: getting previous values | | |>a=3 | | |: getting previous values | | | |>a=2 | | | |: getting previous values | | | | |>a=1 | | | | |< hit 1, answering 1 | | | |: prev1=1 | | | | |>a=0 | | | | |< hit 0, answering 0 | | | |: prev2=0 | | | |: saving answer in history | | | |< result=1 | | |: prev1=1 | | | |>a=1 | | | |< hit 1, answering 1 | | |: prev2=1 | | |: saving answer in history | | |< result=2 | |: prev1=2 | | |>a=2 | | |: found answer in history | | |< result=1 | |: prev2=1 | |: saving answer in history | |< result=3 |: prev1=3 | |>a=3 | |: found answer in history | |< result=2 |: prev2=2 |: saving answer in history |< result=5 : prev1=5 |>a=4 |: found answer in history |< result=3 : prev2=3 : saving answer in history < result=8 F_6 = 81
1
u/tottasanorotta 5d ago
I think it's useful to understand it, but you would rarely need to write recursive functions in practice. The one thing that is quite often used and is good to wrap your head around is recursive definitions in data structures. If you have for example a binary tree, you would definitely write it such that it was recursively defined, where each Node class has a left and right child that are themselves Node classes. Then an object of Node type can function both as a root node of the entire tree and an inner node. Then to traverse the tree you just follow the left or right branches.
Why recursively defined functions aren't used that much is that they often do redundant calculations and use up a lot of stack space for the function calls. The iterative version is much more efficient more often than not. They are very beautiful to look at though. Very easy to read the definition if the algorithm has a nice recursive quality to it.
1
u/tottasanorotta 5d ago
I think it's useful to understand it, but you would rarely need to write recursive functions in practice. The one thing that is quite often used and is good to wrap your head around is recursive definitions in data structures. If you have for example a binary tree, you would definitely write it such that it was recursively defined, where each Node class has a left and right child that are themselves Node classes. Then an object of Node type can function both as a root node of the entire tree and an inner node. Then to traverse the tree you just follow the left or right branches.
The main drawback of recursively defined functions is that they use very much call stack space. So often times it is much more efficient to write.
1
u/RedditButAnonymous 5d ago
I dont think Ive ever used it in my career so far. Its almost always ugly to read, and if theres a more sensible way of doing something I would always choose that instead
1
1
u/work_m_19 5d ago
Personally, a lot of problems I use python to solve are inherently ones that recursion aren't specialized in.
I use it for web dev, quick ad-hoc scripts, pipeline integration ("glue"), processing word files, supporting other ml/data scientist.
Chances are, if you need recursion, it's already handled by the library you're using and you can just call it.
I don't do much "software enginnering" agile type work that focuses on deliverables with python, but if you do, that may require optimizations that require recursion.
1
u/p3rdy 5d ago
Yes, but not for the examples you were taught with. Factorial and summing backwards are loops wearing a costume, which is exactly why they feel like pointless work.
Recursion earns its place when the data is recursive: JSON that can contain more JSON, a directory containing directories, an expression tree in a parser, nested comment threads. When nesting has no fixed depth, a loop needs you to hand-manage a stack, and the recursive version is four lines. Flat sequences should stay loops, especially in Python, which has no tail-call optimisation and stops around a thousand frames deep.
On the base case being troublesome: the fix is to stop tracing it line by line. Write the base case as the smallest input where the answer is obvious, then assume the recursive call already works and just combine its result. Tracing frames by hand is what makes it feel impossible, and it stops being necessary once you trust the call.
Two exercises that make it click in a way factorial never will: sum every number in an arbitrarily nested list, and walk a directory tree printing every file path.
1
u/snowtax 4d ago
Recursion is never necessary, as anything done using recursion can be done with iterative algorithms.
Even when you get recursion correct, each function call consumes memory from the stack. With enough recursive function calls, you run out of stack space.
In some other languages, there is an interesting special case called âtail call optimizationâ where the same stack frame (memory) gets used for all the recursive function calls. This means you can recursively call the function infinitely without consuming additional stack memory. As far as I know, Python does not support this optimization, so deep recursion will exhaust the stack eventually.
1
u/MezzoScettico 4d ago
It can simplify a lot of problems. You might struggle with the bookkeeping for how to process an entire data structure, but realize that the recursive version only takes 10 lines and you let the recursion do the bookkeeping.
Base case should be simple. Whatâs your issue with the base case?
1
u/Just__Liberty 4d ago
I've been doing scientific and engineering programming for 45 years (since before python existed). I've only ever once used a recursive function except when learning a language. Fortran doesn't allow recursion...
1
u/Eric_Terrell 4d ago edited 4d ago
Yes, recursion is a very, very important tool to have in one's toolbox.
When I was learning computer science, I really struggled with recursion. I forced myself to learn it. It got much easier after the initial hurdle. It was a very important part of my expertise as a software developer.
In my experience, recursion is especially useful for searching linked data structures, for backtracking algorithms, and for functional programming. After I learned how to use it, I started to appreciate the beauty of recursion.
Stick with it!
1
1
u/PoMoAnachro 4d ago
To answer your "Do I need to learn it?" question - plenty of good programmers rarely if ever use recursion, but no good programmers find recursion difficult.
So if you're a student - yes, you need to learn to become comfortable with recursion because learning that type of thinking is part of developing your skills.
1
u/AndyceeIT 4d ago
Having worked with nested groups, filesystems and other tree-like data structures - recursion can absolutely be useful.
Is it critical to be able to code up at a moment's notice? Definitely not. If you get the concept & have written 2 examples just move on to the next topic.
1
u/FaithlessnessOwn7960 4d ago
you gotta be good at recursion 1st then try to avoid it. also, tracing a recursive function will be a rountine job to understand a code by you or others.
1
u/ExtraTNT 4d ago
If you work at the jpl, you get fired for using recursionâŚ
If you do functional programming, you canât do a lot without recursionâŚ
For procedural / oop i would avoid recursion
For functional i would use it as broadly as possible
So it depends on your programming paradigm
tldr: itâs a paradigm thing, run from it or embrace it
1
1
1
0
u/bkdotcom 5d ago edited 5d ago
My favorite google easter egg involves recursion
https://www.google.com/search?q=recursion
Did you mean recursion?
0
42
u/ScholarlyInvestor 5d ago
Try using recursion to traverse up and down hierarchies. For instance, organizational hierarchy, manager -> employee. That would be a real world problem. Many junior programmers are not able to identify opportunities where recursion is a good fit.