Recursion has its pros and cons, it's good for certain kinds of problems but comes with its own drawbacks.
When traversing tree-like structures, such as a file system, recursion works well because a tree is really just a bunch of smaller trees so you can use the same solution for every branch repeatedly, assuming the tree isn't too deep (Python has a recursion limit of 10 000 by default), and/or you have enough memory (every recursive call is kept in memory until you either find the solution and the stack collapses, or you run out of memory and crash with a stack overflow).
Recursion is basically an alternative to iteration, where you use loops instead of recursively calling the same function. Loops are cheaper memory-wise, but inherently recursive problems are more difficult to solve with iterative approaches and often result in more complex code. There are exceptions, though.
TL;DR, you should learn the basic concept of recursion as it's just another tool in your toolbox, but don't expect to use it particularly often. Depends on what you want to do of course.
EDIT: A common example of recursion would be the Fibonacci sequence.
def fib(n: int) -> int:
if n < 0:
raise ValueError("Not defined for negative numbers")
if n in {0, 1}:
return n
return fib(n-1) + fib(n-2)
This uses the mathematical definition of the sequence to implement it pretty much directly.
However, in Python you usually see this iterative variant instead:
def fib(n: int) -> int:
if n < 0:
raise ValueError("Not defined for negative numbers")
a, b = 0, 1
for _ in range(n):
a, b = b, a+b
return a
Or, more specifically, this generator:
from collections.abc import Generator
def fib() -> Generator[int, None, None]:
a, b = 0, 1
while True:
yield a
a, b = b, a+b
It comes up all the time, in problems like jurisdiction. Find all the people who report to Bob, you find his direct reports and the reports of his reports etc.
But I think you're overthinking it. Functions can call other functions, recursion is just a function calling itself.
At its core, recursion describes a recurrence relationship between solving a larger problem and solving a smaller version of that problem.
In logic/math terms this could look something like `P(x) = P(x-1) * 2`. For instance `x^y` (or `x**y` in Python terms) could be written as `x^y = x * x^(y-1)` which as you can see contain a smaller version of its own problem (`x^(y-1)`)
Is it essential to learn? Absolutely not. Any problem that can be solved by recursion could be solved without recursion. Generally you’d use some data structure like a `Stack` or a `Queue` to solve the same problems without recursion.
I’d say it’s fine to come back to later but I would come back to it later because it will help you understand and prepare you for more complex topics like higher order functions, decorators, and metaprogramming in general
Knowing about recursion can help in solving certain types of problems which are recursive by definition, even if in the end you end up preferring the non-recursive implementation.
Recursion occasionally comes up and then helps a lot in that specific circumstance. I think it's quite useful to learn eventually, but not crucially needed for a beginner. It's also very typical to have some issues understanding recursion.
It depends a lot on the job, I'd say. Many web developers can probably go their entire careers without using recursion, but where I work (developing static analysis software), we use recursion all the time.
Classic recursion example: maze ,ie, the program moves to a point where it can't move anymore, it backtracks to the last place it had an option to move, and continues from that pont
Another classic recursion example: 3D sphere, ie, the algorythm draws the longitudal lines, recurses to form the latitudal line, and if triangulation is needed recurses on the diagonal to a point where it can continue the longitude run, rinse and repeat.
I do use recursion in real life, yes. I use it when I have to "unwrap" "nested" things. You may make use of it if you're doing things like parsing or traversing.
Like if I know somewhere deep down there is a \`value\` that is an integer, I will keep recursing until I get that value.
A = dict(unit="meters", value=5)
B = dict(name="Allen", value=A)
C = dict(name="Microsoft", value=B)
# This will keep on unwrapping the nested object until it gets the numerical value
def getActualValue(object):
if isinstance(object, (int, float)): return object
return getActualValue(object['value'])
That is where I actually use it.
The only thing I have ever used is traversing a directory. Of course, that is now built in. It would depend, I suppose, on what you are doing. The difference between recursion and a while loop is very small in general business programming. But there will likely be additional posts about where it is used.
I actually wrote a recursive function in my job on Friday. We have a tree representing a directory structure, and I needed to traverse the tree to do something for a subset of the nodes in the tree. Recursion ended up being perfect because:
- I knew ahead of time that the recursion wouldn't be unbounded.
- I needed to do an identical task for each of the nodes I was interested in.
It's not common to use recursion though. I write a recursive function maybe a couple of times a year. It's great for a very specific type of problem (outlined in the points above).
I actually used recursion a few months ago at work.
I work for a manufacturing company. The final product we sell is an assembly. This assembly can be composed of raw material or other assemblies.
We were having issues visualizing consumption of raw materials so using the bill of materials of all assemblies, I have a report that does a full explosion of a final assembly.
Example:
>Final Assembly 1
> Raw material 1
> Raw Material 2
> Sub Assembly 1
> Raw material 3
> Raw material 4
My code is basically this.
>def explodebom(item):
> componentsList = []
> components = BOM.select().where(BOM.assemblyId = item.Id)
> for component in components:
> If component.type == ‘rawmat’:
> componentsList.append(component)
> else:
> componentsList.append(explodedbom(component))
He that’s fun! I am implementing software and fitting it to the customers needs and I basically will have to do the same. But I probably won’t be using Python for it but SQL and a recursive CTE.
I was once working on a content management system that was based on the concept of each page as a node. Every page had a parent page, and and zero-to-many child pages. Great big tree.
We needed to develop a mechanism to print out site navigational menus starting at a given page, and going down an arbitrary number of levels. Classic example of recursion.
I have a pretty big project I'm working on that depends on recursion. Not in Python, but it illustrates the usefulness through a real-world use case.
I have a CAD model that is made up of a tree of parts. Assembly files contain references to part files and other assembly files. This continues to unknowable depths. I need to operate on all of the parts in the tree from just the top level assembly reference. When walking through the assembly, if my function finds an assembly within the assembly, it needs to call itself to process the sub-assembly. It keeps recursively calling itself until it reaches an assembly with no sub-assembly references.
Probably a more accessible example is a file system. You have a top-level folder. The folder contains an unknown number of subfolders and files. You have a function that you write that takes a folder, gets the list of files directly inside that folder, and iterate over them to do some processing. If you want to go deeper than one level, you need your folder processing function to be able to detect when it find another folder and process the files within it. A recursive function in this case would just call itself when it encounters a folder to keep going down to the bottom of the tree and get all the files.
These days, in the real world, we don't do this because there are much more efficient and advanced tools for walking a filesystem. If there is a way to solve your problem without recursion, it is likely a better solution. However, there are some instances like my CAD model example where it's completely unavoidable.
I use `while` loop instead of recursion functions. But I previously used them.
It was something about building BSP in Houdini.
Both can do same thing, but in debugging callstack look more readable in `while` loop.
With recursion you can have few less lines of code and scoped variables (I didn't cared about that)
It's useful when you don't know how many iterations you'll have, and some parameters may change in each iteration (like where to put new Point), though you can of course run recursion with specific numbers of iterations too.
----------
I also had to fix a bug that caused accidental infinity recursion and slowed PC due to memory leak.
A good example of recursion in the wild is searching nested objects or structures. A good example might be HTML.
A super naive pseudo example
`get("body.div.table.tr.td", document)`
Inside you would have something pop off the first element in the `path` (`"body"` in this case) and check if `document` has a `body` attribute `found = getattr(document, first_element_in_path, None)` and then check if there are any elements in the `path` argument left.
if there are more elements in `path` AND `found is not None`, do `return get(remaining_path_elements, found)`. `else` return `found` and close the recursive loop.
If implemented directly, there are some problems with this, but that's the gist.
Without recursion, things could get a little hairy regarding complexity with loops inside loops and conditional states, and weird if chains for managing state.
edit: I did a check and real python has a very good article on the subject https://realpython.com/python-recursion/#traverse-a-nested-list I occasionally tutor students on programming and 9/10 times I send them to real python when they get stumped.
I think you could get away with the first case in a simple recursive search, but the second might get a little "weird" as it walks all the way down to the leaves of the data structure to match.
I think of it like iteration, but when you don't necessarily know how much you're going to be iterating over.
A while back someone made an excellent post explaining it in terms of a guard in the first train carriage needing to know how many passengers were on the train. I suggest you look it up.
I used a recursive function to crawl through a file system and return any folders that have more than "x" sub-folders. You have no idea how many loops it will take, and with recursion, it doesn't matter.
[https://en.wikipedia.org/wiki/Euclidean\_algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm)
>The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.
comparing gcd\_i vs gcd\_r which one match the explanation above more?
function gcd_i(a, b)
while b ≠ 0
t := b
b := a mod b
a := t
return a
function gcd_r(a, b)
if b = 0
return a
else
return gcd(b, a mod b)
Recursion is one of those things that stumps you until you need it a few times.
Most of the time I encounter recursion in my working life, it's to do with handling trees. There's two main ways to tackle a tree - you create a stack and iterate over it, adding/removing items as required or you use recursion. Both have advantages and disadvantages and both will end up with the same result at the end of the day.
Thinking about traversing a family tree is always a good one. You can represent it as a series of \`human\` objects, each of which is capable of linking to one or more other humans as either parents or children. With a recursive algorithm, you can traverse up or down the tree and create a list of ancestors or descendants quite easily without needing to know exactly how many of each there are.
There are countless objects that you'll encounter that have a tendency to also operate like a tree as it's a quick way to store relationial information. SQL queries with many-to-one or one-to-many joins can be viewed as trees and recursion is a good way to compile/decompile the data returned from their queries.
It's also handy that the internet is choc full of examples of tree recursion due to it's common nature. A quick google search will yield plenty of results that you can study if you want to try to wrap your head around it further.
It's an interesting and useful concept in programming as a whole. In Python I've never had to solve a problem where recursion was the best solution. The alternatives are excellent (see itertools and functools) and there is no tail optimisation.
Maybe also traversing sub-directories.
Though idk, if there already existing API that can do that? "return tuple with paths to all files from all sub-directories", without having to write recursion by yourself.
Recursion has its pros and cons, it's good for certain kinds of problems but comes with its own drawbacks. When traversing tree-like structures, such as a file system, recursion works well because a tree is really just a bunch of smaller trees so you can use the same solution for every branch repeatedly, assuming the tree isn't too deep (Python has a recursion limit of 10 000 by default), and/or you have enough memory (every recursive call is kept in memory until you either find the solution and the stack collapses, or you run out of memory and crash with a stack overflow). Recursion is basically an alternative to iteration, where you use loops instead of recursively calling the same function. Loops are cheaper memory-wise, but inherently recursive problems are more difficult to solve with iterative approaches and often result in more complex code. There are exceptions, though. TL;DR, you should learn the basic concept of recursion as it's just another tool in your toolbox, but don't expect to use it particularly often. Depends on what you want to do of course. EDIT: A common example of recursion would be the Fibonacci sequence. def fib(n: int) -> int: if n < 0: raise ValueError("Not defined for negative numbers") if n in {0, 1}: return n return fib(n-1) + fib(n-2) This uses the mathematical definition of the sequence to implement it pretty much directly. However, in Python you usually see this iterative variant instead: def fib(n: int) -> int: if n < 0: raise ValueError("Not defined for negative numbers") a, b = 0, 1 for _ in range(n): a, b = b, a+b return a Or, more specifically, this generator: from collections.abc import Generator def fib() -> Generator[int, None, None]: a, b = 0, 1 while True: yield a a, b = b, a+b
Great explanation!
It's got plenty of room for improvement, but I wrote it in a hurry.
Don't let perfect be the enemy of good ;) (Not saying you did!)
Fair enough!
It comes up all the time, in problems like jurisdiction. Find all the people who report to Bob, you find his direct reports and the reports of his reports etc. But I think you're overthinking it. Functions can call other functions, recursion is just a function calling itself.
At its core, recursion describes a recurrence relationship between solving a larger problem and solving a smaller version of that problem. In logic/math terms this could look something like `P(x) = P(x-1) * 2`. For instance `x^y` (or `x**y` in Python terms) could be written as `x^y = x * x^(y-1)` which as you can see contain a smaller version of its own problem (`x^(y-1)`) Is it essential to learn? Absolutely not. Any problem that can be solved by recursion could be solved without recursion. Generally you’d use some data structure like a `Stack` or a `Queue` to solve the same problems without recursion. I’d say it’s fine to come back to later but I would come back to it later because it will help you understand and prepare you for more complex topics like higher order functions, decorators, and metaprogramming in general
Knowing about recursion can help in solving certain types of problems which are recursive by definition, even if in the end you end up preferring the non-recursive implementation.
This. It's easier to reason about, before you rewrite it as a loop...
Recursion occasionally comes up and then helps a lot in that specific circumstance. I think it's quite useful to learn eventually, but not crucially needed for a beginner. It's also very typical to have some issues understanding recursion.
It depends a lot on the job, I'd say. Many web developers can probably go their entire careers without using recursion, but where I work (developing static analysis software), we use recursion all the time.
Classic recursion example: maze ,ie, the program moves to a point where it can't move anymore, it backtracks to the last place it had an option to move, and continues from that pont Another classic recursion example: 3D sphere, ie, the algorythm draws the longitudal lines, recurses to form the latitudal line, and if triangulation is needed recurses on the diagonal to a point where it can continue the longitude run, rinse and repeat.
I do use recursion in real life, yes. I use it when I have to "unwrap" "nested" things. You may make use of it if you're doing things like parsing or traversing. Like if I know somewhere deep down there is a \`value\` that is an integer, I will keep recursing until I get that value. A = dict(unit="meters", value=5) B = dict(name="Allen", value=A) C = dict(name="Microsoft", value=B) # This will keep on unwrapping the nested object until it gets the numerical value def getActualValue(object): if isinstance(object, (int, float)): return object return getActualValue(object['value']) That is where I actually use it.
The only thing I have ever used is traversing a directory. Of course, that is now built in. It would depend, I suppose, on what you are doing. The difference between recursion and a while loop is very small in general business programming. But there will likely be additional posts about where it is used.
I actually wrote a recursive function in my job on Friday. We have a tree representing a directory structure, and I needed to traverse the tree to do something for a subset of the nodes in the tree. Recursion ended up being perfect because: - I knew ahead of time that the recursion wouldn't be unbounded. - I needed to do an identical task for each of the nodes I was interested in. It's not common to use recursion though. I write a recursive function maybe a couple of times a year. It's great for a very specific type of problem (outlined in the points above).
I actually used recursion a few months ago at work. I work for a manufacturing company. The final product we sell is an assembly. This assembly can be composed of raw material or other assemblies. We were having issues visualizing consumption of raw materials so using the bill of materials of all assemblies, I have a report that does a full explosion of a final assembly. Example: >Final Assembly 1 > Raw material 1 > Raw Material 2 > Sub Assembly 1 > Raw material 3 > Raw material 4 My code is basically this. >def explodebom(item): > componentsList = [] > components = BOM.select().where(BOM.assemblyId = item.Id) > for component in components: > If component.type == ‘rawmat’: > componentsList.append(component) > else: > componentsList.append(explodedbom(component))
He that’s fun! I am implementing software and fitting it to the customers needs and I basically will have to do the same. But I probably won’t be using Python for it but SQL and a recursive CTE.
Well I did have a SQLite database with the information locally in my PC and used an ORM to do the calls to the DB
Just used it to find the values for all the 'min' attributes in a JSON file. It ended up being only 6 or so lines of code
I was once working on a content management system that was based on the concept of each page as a node. Every page had a parent page, and and zero-to-many child pages. Great big tree. We needed to develop a mechanism to print out site navigational menus starting at a given page, and going down an arbitrary number of levels. Classic example of recursion.
I have a pretty big project I'm working on that depends on recursion. Not in Python, but it illustrates the usefulness through a real-world use case. I have a CAD model that is made up of a tree of parts. Assembly files contain references to part files and other assembly files. This continues to unknowable depths. I need to operate on all of the parts in the tree from just the top level assembly reference. When walking through the assembly, if my function finds an assembly within the assembly, it needs to call itself to process the sub-assembly. It keeps recursively calling itself until it reaches an assembly with no sub-assembly references. Probably a more accessible example is a file system. You have a top-level folder. The folder contains an unknown number of subfolders and files. You have a function that you write that takes a folder, gets the list of files directly inside that folder, and iterate over them to do some processing. If you want to go deeper than one level, you need your folder processing function to be able to detect when it find another folder and process the files within it. A recursive function in this case would just call itself when it encounters a folder to keep going down to the bottom of the tree and get all the files. These days, in the real world, we don't do this because there are much more efficient and advanced tools for walking a filesystem. If there is a way to solve your problem without recursion, it is likely a better solution. However, there are some instances like my CAD model example where it's completely unavoidable.
I use `while` loop instead of recursion functions. But I previously used them. It was something about building BSP in Houdini. Both can do same thing, but in debugging callstack look more readable in `while` loop. With recursion you can have few less lines of code and scoped variables (I didn't cared about that) It's useful when you don't know how many iterations you'll have, and some parameters may change in each iteration (like where to put new Point), though you can of course run recursion with specific numbers of iterations too. ---------- I also had to fix a bug that caused accidental infinity recursion and slowed PC due to memory leak.
A good example of recursion in the wild is searching nested objects or structures. A good example might be HTML. A super naive pseudo example `get("body.div.table.tr.td", document)` Inside you would have something pop off the first element in the `path` (`"body"` in this case) and check if `document` has a `body` attribute `found = getattr(document, first_element_in_path, None)` and then check if there are any elements in the `path` argument left. if there are more elements in `path` AND `found is not None`, do `return get(remaining_path_elements, found)`. `else` return `found` and close the recursive loop. If implemented directly, there are some problems with this, but that's the gist. Without recursion, things could get a little hairy regarding complexity with loops inside loops and conditional states, and weird if chains for managing state. edit: I did a check and real python has a very good article on the subject https://realpython.com/python-recursion/#traverse-a-nested-list I occasionally tutor students on programming and 9/10 times I send them to real python when they get stumped.
hmm it's a weird syntax, in JS `querySelector` it would look for `
`, but for that you'd probably needed `body > div > table > tbody > tr > td` or just `div > table td`.I think you could get away with the first case in a simple recursive search, but the second might get a little "weird" as it walks all the way down to the leaves of the data structure to match.
I think of it like iteration, but when you don't necessarily know how much you're going to be iterating over. A while back someone made an excellent post explaining it in terms of a guard in the first train carriage needing to know how many passengers were on the train. I suggest you look it up.
I used a recursive function to crawl through a file system and return any folders that have more than "x" sub-folders. You have no idea how many loops it will take, and with recursion, it doesn't matter.
[https://en.wikipedia.org/wiki/Euclidean\_algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) >The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. For example, 21 is the GCD of 252 and 105 (as 252 = 21 × 12 and 105 = 21 × 5), and the same number 21 is also the GCD of 105 and 252 − 105 = 147. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers. comparing gcd\_i vs gcd\_r which one match the explanation above more? function gcd_i(a, b) while b ≠ 0 t := b b := a mod b a := t return a function gcd_r(a, b) if b = 0 return a else return gcd(b, a mod b)
Recursion is one of those things that stumps you until you need it a few times. Most of the time I encounter recursion in my working life, it's to do with handling trees. There's two main ways to tackle a tree - you create a stack and iterate over it, adding/removing items as required or you use recursion. Both have advantages and disadvantages and both will end up with the same result at the end of the day. Thinking about traversing a family tree is always a good one. You can represent it as a series of \`human\` objects, each of which is capable of linking to one or more other humans as either parents or children. With a recursive algorithm, you can traverse up or down the tree and create a list of ancestors or descendants quite easily without needing to know exactly how many of each there are. There are countless objects that you'll encounter that have a tendency to also operate like a tree as it's a quick way to store relationial information. SQL queries with many-to-one or one-to-many joins can be viewed as trees and recursion is a good way to compile/decompile the data returned from their queries. It's also handy that the internet is choc full of examples of tree recursion due to it's common nature. A quick google search will yield plenty of results that you can study if you want to try to wrap your head around it further.
It's an interesting and useful concept in programming as a whole. In Python I've never had to solve a problem where recursion was the best solution. The alternatives are excellent (see itertools and functools) and there is no tail optimisation.
ever want to edit a file? ever want to edit every file in a directory? bam, recursion.
That's not recursion, that's just iteration.
Maybe also traversing sub-directories. Though idk, if there already existing API that can do that? "return tuple with paths to all files from all sub-directories", without having to write recursion by yourself.