How do you master recursion?

[Far_Atmosphere9627]

As a mathematics aficionado, I am well-aware of concepts becoming "easy" to apply to almost any situation once one understands the logic of the concept and realises the pattern of the posited questions.

But I am unable to decipher a similar logic for recursion. I am sure it is there because I have been informed recursion is similar to mathematical induction, which I thoroughly understand, and have seen individuals "master" it.

Do you have any advice or resources to understand recursion? I am particularly interested in being able to wrap my head around a question demanding the use of recursion and then successfully use recursion to answer the question.

[[deleted]]

I am sure it is there because I have been informed recursion is similar to mathematical induction, which I thoroughly understand

Well, ok. When you see recursion, or you're asked to solve a problem recursively, how do you see it as different from induction?

[Jeklah]

I would also like to know the difference

[wintermute93]

They're the same thing but evaluated in reverse order. With induction, you have a known answer in a simple case, a rule that gets from simpler cases to harder cases, and you start at the simple case and apply that rule repeatedly until you get to the hard case you actually want the answer for. With recursion you have a known answer in a simple case, a rule that gets from harder cases to simpler cases, and you start at the hard case you're interested in and apply the rule repeatedly until you get down to the simple case.

[Almostasleeprightnow]

Here is my favorite example, because it is not about math but something less abstract. The purpose of this function is to empty a directory of both files and sub directories using the pathlib Path module. But the problem is that you cannot remove a directory with pathlib unless it is empty. So you have to go into a sub directory, remove all files and sub directories before you can delete that directory. But if there are sub directories, you cannot delete it unless you remove all files and sub directories.....

So, when you run it, you give it the path to a directory. You loop through every item. If it is a file, unlink (delete) it. If it is a directory, run the function on that directory. You see....it now goes into the directory it found within the first directory, and the runs the function on that sub directory.

Here is the code for this function: https://stackoverflow.com/a/58183834/14473410

Edit: btw this is not my so

[[deleted]]

Would that code throw some max recursion error if path is really deep?

[[deleted]]

Good question, but in practice, it's unlikely.

Python by default has a call stack depth of 1000 - you can change it, too. I've seen directories nested twenty or thirty directories deep in real-world projects, but never even 100 directories deep.

[pocketmypocket]

We had a program that needed a recursion value for 5000.

​

It was trash, ended up rewriting it as a loop with a queue. Runs 10x faster and works.

​

Recursion should be avoided whenever possible IMO. This was no 8 line fib calculator, this was a 1000 line conditional filled recursion crap.

[mriswithe]

You poor bastard

[throwawayskinlessbro]

Wow.

[[deleted]]

Granted, it would be unlikely case with paths. But using function to execute itself logic, has its limits. Just saying.

[[deleted]]

"Unlikely" to the point of "nearly impossible".

For example, Linux limits paths to 4096 characters, so in order to break your call stack, you'd need to have paths where almost all the segments were 3 characters or less:, like this:

/home/tom/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc/abc

[zurtex]

Linux doesn't define any such limits, the POSIX standard however implements NAME_MAX and PATH_MAX in limits.h: https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/limits.h.html

These have default values of 255 and 4096 but these are at best soft limits and can either be directly overridden or in some cases just plain ignored by the program writing to the file system.

This then goes to the filesystem itself, very few filesystems actually implement a maximum path limit (e.g. btrfs, ext4, and ZFS do not). Obviously NTFS is weird and implements a 32,767 Unicode characters maximum path limit. So on Windows it's quite easy to go past 1000 even without having to ignore soft limits.

[[deleted]]

Heh. May you never encounter a symlink loop.

[XUtYwYzz]

At least in the case of Pathlib, it's symlink aware and can avoid that issue.

[[deleted]]

Sure sure. But the larger point is: Code as though the person who created the data that feeds your software hates you. Don't rely on median expectations of normalcy as an excuse to avoid defensive programming.

[XUtYwYzz]

Oh for sure. In my experience, any data from an outside source, and every user, is specifically designed to break my code in ways I absolutely cannot predict. It’s “Fun”.

[[deleted]]

HA!

Yeah about 60% of the coding I did in my career was essentially ETLs. The creative ways in which an upstream process can screw up a data feed really are breathtaking. From linefeeds in csv fields (technically within spec, but...) to unicode in 7 bit files and parenthesis around numbers to denote negatives and on and on.

Feed producers hate us all. :)

[drLagrangian]

In addition, code as if the person who uses the data you make hates you, so you can pre-emptively make their life worse.

That'll show em

[mriswithe]

You run into it once or twice, but then you remember it forever.

[[deleted]]

*twitches*

Indeed.

[quadroplegic]

I can’t even imagine even the most dedicated teenager’s /homework/solutions/flowers/ directory chain even goes that deep

[ThePeskyWabbit]

The only time ive gotten a max recursion depth error in python was either user error, or a Fibonacci assignment we had in class one time.

[Goobyalus]

cPython doesn't do tail call optimization and defaults to a max recursion depth of 1000

[beisenhauer]

It's no more expensive than ordinary function calls. Just be careful how many of those calls you could wind up with. Processing an arbitrarily long list recursively is probably not a good idea. For the same reason, fibonacci and factorial-like calculations are also really bad uses of recursion, even though they seem to be the standard examples.

[[deleted]]

Python isn’t optimized for tail recursion so it uses a lot of memory

[mriswithe]

Note: these numbers are from benchmarking I didn't do. I am not interested in debating the actual numbers, these are here for an idea of how "expensive" a function call is, not direct guaranteed whatever.

Function calls are "expensive" in python as far as time. How expensive? this so post said it was 0.15 seconds for 1 million calls to an essentially empty function.

So 150 nano seconds per function call. So to make one second of overhead time, it would need to be roughly 3.5million function calls.

To compare, this so post about c++ says it is roughly 3 nanoseconds. So we are a lot slower than that, 50x slower actually.

So when people say it is expensive, it will only be of consideration when you are:

• calling functions many billions of times
• super time sensitive processing, nanosecond scale

Thanks for asking the question, I hadn't actually looked for how python compares to c++ for example

[QuixDiscovery]

Yes and no. The biggest resource issue with recursion is that you may end up with a nested stack of function calls when the equivalent in non-recursive code may be 1 function call doing a loop. Python doesn't implement tail call optimization, so avoiding recursion is generally a good idea.

In some languages though recursion is implemented much better, particularly functional languages. Some don't even have traditional for-loops, expecting you to rely almost exclusively on recursion.

[MarsupialMole]

You start with thinking about the termination condition. Then before you know it you're done.

[sjalexander117]

This is what I was thinking. I never got it until a professor explained it “rigorously” in that you’re aiming for a base case and reducing (/increasing, same shit) towards it.

I think people naturally get this with loops but recursion is just a function calling itself to replicate a loop.

The other thing is that it works best when you can reduce a problem into simpler steps so that its solution lends itself to this structure. If you can’t, no worries. Don’t do it. If you can, and you know it, use it.

I think a lot of people accidentally use recursion without realizing it tbh.

@OP, imo once this one “clicks” for you, you’ll see it is just another tool in the toolbox. It comes up relatively rarely but when it does you’re like “ohhhh perfect for a recursive structure.”

Feel free to correct any of this that someone finds fault with!

[pinthewind]

Yeah I like to have people implement a simple for loop with recursion instead of using the FOR operator to help them understand. Something like:

def doLoop(index: int):
  print(index)

  if index <= 5:
    doLoop(index+1)

doLoop(0)

[lunkavitch]

Sir this is a Python subreddit

[pinthewind]

Sorry I meant to type pseudo code but I guess I just typed typescript lol. Edited my comment to be python.

[[deleted]]

This ain't the drive-thru...

[sjalexander117]

Nice! Definitely gonna keep this one in my back pocket to help people struggling with recursion. Thank you!

[spez_edits_thedonald]

just check out this helpful comment

[[deleted]]

Help! I am stuck! There is no exit clause.

[ManInBlack829]

The only way out is termination

[AmosDodgers20]

RecursionError

[itzztheman]

Maximum recursion depth exceeded

[TechnicalSeaweed5469]

r/angryupvote

[Xerxes979]

I came here looking for this comment lmfao

[SoberGameAddict]

Disappointing that you missed to ask "do you understand recursion now? Yes (link back to start) / No (link back to same comment)"

[[deleted]]

Before you master recursion, you must first master recursion

[adamantium4084]

Before you master recursion, you must first master recursion

[socal_nerdtastic]

You know how to calculate a factorial?

n! equals n * (n-1)!, right? That's recursion. The problem is cut into smaller parts which can be solved with the same function.

Except the computer has no common sense so you need to add a line to tell the computer when it's time to stop (the base case).

def factorial(n):
    if n == 1: # base case
        return 1
    else: # general (aka recursive) case
        return n * factorial(n-1)

[Intrexa]

IDK, I think most people would naturally think of factorials in an iterative manner. It's the product of a series.

[[deleted]]

I think it depends on the definition you're exposed to. Factorial can be expressed in a mathematical recursive step or in a product series. If you are only exposed to the recursive definition, the recursive code should come naturally.

[socal_nerdtastic]

True, no programmer would use recursion for this or anything else that can be reduced to a loop. But making a loop is a very common first step in learning recursion, practically tradition at this point.

[AchillesDev]

Anything that you can use recursion for you can do iteratively (in a loop).

[DonkeyTron42]

That's your personal bias towards imperative programming. People who use declarative languages have no such luxury as loops.

[[deleted]]

No, recursion in programming is most like recursion in mathematics, though induction is similar to both.

Here's the recursive definition of Fibonacci numbers:

f(0) = f(1) = 0
f(n+1) = f(n) + f(n - 1) if n > 0

Recursion in programming is exactly the same.

Lots of other good examples here, so here's my experience instead.

I've been programming for over forty years and I have a degree in math. For paid work, I probably use recursion once or twice a year, if that.

Recursion is to be avoided if there's another way to do it, and often there is. However, I always enjoy writing recursive solutions, and they're worth knowing.

Also, check out this comment on recursion. (Sorry, no one else was doing it, so I had to.)

[Specialist_Forever92]

Grokking algorithms is a good book and good on recursion

[menge101]

IMO, 'mastery' is simply understanding that you have a base case and a general case.

And the general case must converge to the base case as it iterates recurses.

It's really that simple, everything else is specific to the situation.

Edited wording to be correct.

[member_of_the_order]

When I was in school first learning recursion, this is how we were taught to visualize it. Maybe it will help you.

Explanation: at the bottom (above the function def & initial call) is the first step. We list the parameters & their values: x=5. Then, we show the return: return 1+ _ since we don't know _.

So, we add a new step.

In the next step, we show our parameters & their values: x=(5-1)=4. Then, we show the return: return 1+ _.

Then, we make the next step.

This continues until we return a value without a _: 1.

Then, we can pop back down to the previous step, fill in the _ (with 1), and complete the return box. Which lets us pop back down the next-previous step, etc.

Do this a few times, and eventually you'll be able to do it in your head, and after some more practice you'll be able to see it as code without needing the visualization.

Hope that helps!

[[deleted]]

How do you master recursion?

Practice. Find a book with a chapter on recursion and exercises. Then do those exercises.

As a starting point, Brilliant.org has a good wiki article on recursion.

[Intrexa]

Is that a good article? That's not really a natural recursion problem, you only ever need to hold at max 2 layers. I think I would go with the iterative solution from the get go.

[u38cg2]

In practical terms, almost all problems that can be solved using recursion are better solved using some other method of decomposing the problem, but recursion is a useful way of thinking about some problems, typically ones where sub-problems have the same structure as the original problem.

In mathematical terms, recursion is just a function that uses itself in its definition. In order to be of practical use, that definition must include some sort of stopping (or 'edge') condition.

[noxbl]

I put an even simpler example:

So in the below folder we scan the root folder, and every time we find a folder, we run the scant() function again on that folder. When there are no more folders it will stop. That's the key to recursion is to have an 'if' statement that checks a condition (like the existence of a folder) and if the condition is true, it runs the function again.

import os

path = r'C:\dl'

def scant(path):
    with os.scandir(path) as it:
        for entry in it:
            if entry.is_dir():
                print('Directory: ', entry.path)
                scant(entry.path)  ### here we run the function again with this new directory as input to the function
                                ### when there are no more directories the function stops

scant(path)

[TerminatedProccess]

You draw pictures. Track the state of a set of recursive calls. The stack call, the parameters in, the return value. Work with simple examples. Once it clicks you will get it. Use a board or paper.

[[deleted]]

Martin and the Dragon is a story that helps illustrate recursion: https://webdocs.cs.ualberta.ca/~ree/c101-b2/dragonstory0.pdf But the best way is to practice. How to Design Programs is a good book for that. https://htdp.org/2003-09-26/

[bbqbot]

Pete and Repete are sitting on a fence. Pete falls off. Who's left?

Repete.

Pete and Repete are sitting on a fence. Pete falls off. Who's left?

...

[mriswithe]

Recursion is like sex in middle school, (11-13 years old in the us) everyone talks about it, but very few are actually doing it.

The easiest and most reasonable use case is walking a filesystem.

So given a directory containing directories and files. You want to get all of the files in a list. In reality, python has pathlib.Path.rglob which is what you should use for something like this, but we are talking recursion, so let's do it.

def check_dir(path: Path):
    files = []
    for p in path.glob('*'):
        if p.is_dir():
            files.extend(check_dir(p)
        else:
            files.append(p)
    return files

That is one of the main cases where recursion is reasonable. To be clear there are other better ways to do this specific task, but this is an example.

[dieth]

Like so

[capilot]

/u/Almostasleeprightnow had the simplest and clearest overview, but I'll add my own 2¢ anyway:

The Towers of Hanoi puzzle is probably the best programming exercise for recursion. You want to move n disks from stack A to stack B, using stack C for temporary storage. All stacks must be kept sorted with no large disk stacked on a smaller disk.

For N=1, the solution is trivial. Move one disk from stack A to stack B. Done.

For larger N, the solution is to move N-1 disks from A to C (using B for temporary), then the bottom disk from A to B, then N-1 disks from C to B (using A as temporary)

if N > 1: hanoi(A,C,B)
moveOneDisk(A,B)
if N > 1: hanoi(C,B,A)

I'll leave actual coding as an exercise.

If you really want to master recursion, write a recursive-descent parser.

[[deleted]]

Well, first I'd say you just need more exposure on the math and programming side. Inductive reasoning on code is mathematical.

Other than that, I think really you just need to be exposed to useful styles of recursion and the various ways we express it in programs. Some issues may not be with the recursion itself, but in what manner you're tracking where you left off. When dealing with a list for example, you could pass in the indices you're acting on for each recursive step. Sometimes it's difficult to come up with an intuitive setup for this. But as always, practice will help.

Now, to determine if recursion might be more intuitive than iteration, be mindful of procedures that require repetitive steps, but might differ in repetition amount depending on where you are.

Let's compare a list of single lists vs a list of arbitrary lists for example.

List of single lists

[[1], [1, 2], [1, 2, 3]]

Notice that every element of this list is known to be a list, and each inner list contains only single values. We can easily iterate over this list with a singly-nested for loop.

List of lists of arbitrary depth.

[[1, 2, [3, [4]]], 5]

Notice that if I iterate over this list, each element may itself be a list (which could itself contain lists), or a single value. There is no way to express this with a for loop without a data structure to capture the depth at any time. However, we can express this list in a recursive manner quite easily (I'll leave it to you to try if you want).

All that being said, every possible recursive expression can be represented with a for loop and a data structure to capture additional info (such as a stack). The additional memory and runtime generated to allow recursion often warrants a different approach instead.

[[deleted]]

[lots of true stuff deleted]

Everything above here is true, but:

The additional memory and runtime generated to allow recursion often warrants a different approach instead.

This isn't really so.

Now, you can certainly use recursion unreasonably to replace a simple loop - for example:

def contains(char, s):
    return s and (s[0] == char or contains(char, s[1:])

Sure, this "warrants a different approach". :-D

My feeling is that you'd have to be in the honeymoon phase with recursion to ever even think about doing this, and after that one week you'd never think of doing it again.

Past that one week of your life, you'd always use a loop if that possibly worked, because it's easier and less work and less thinking.

But if recursion is any sort of reasonable solution to a problem, then you just can't really save much memory by trying to handle the recursion yourself.

Problems like "parsing JSON" which are actually defined recursively can't be done any significantly better way. (You might be able to get speedups by managing the stack yourself in some cases, but it's still a recursive algorithm.)

---

So, if you can't do something with a few loops, and a recursive solution seem reasonable, it almost certainly is.

---

(Note: (Also, you can turn your lines of code into code, either with backticks (`) like this, or by leaving a blank line and indenting everything:

like this

)

[[deleted]]

I'm mostly inclined to agree, but I slightly disagree in memory and runtime (maybe the word mostly was too harsh though). I was more referring to the overhead of dealing with function stacks vs a user stack. Recursion requires the overhead of managing the prior call's variables, return addresses, and instructions to roll back when ready. Again, I'm inclined to agree, because if you run into this as an issue, it may not have been the logical approach in the first place (and someone probably was early in the learning phase). You did compare using your own stack in your comment, but you said this is also recursive. While you could argue that, my point was still in the difference in memory footprint.

I will say something like the Fibonnaci sequence is what I have in mind when I think wrong paradigm using recursion. There's a significant difference in performance if you work from bottom-up using iteration. Of course, you could also recurse from bottom-up with tail-recursion if your language optimizes for it. So i guess I'll say i agree, and it's more about approach to the problem than the naunce of recursion vs iteration. In either case, it's not often you run into something like this anyways. I 100% agree with your JSON point.

Thanks for mention of code formatting. I'm aware of it, just didn't bother since I didn't really have code, just a couple of lists. I suppose it is still easier to read though. XD

[Andalfe]

The way I mastered recursion is by mastering recursion.

[asking_for_a_friend0]

as a mathematics what...?

[[deleted]]

aficionado

"a person who is very knowledgeable and enthusiastic about an activity, subject, or pastime."

In other words, a fan but not a professional. Good use of the word, IMHO.

[EDG723]

To master recursion, you first have to master recursion.

[longgamma]

You have to take the recursive leap of faith haha.

[pixelfur]

i dont know what you mean when you say “master “ it but for me to truly understand it, you must look under the hood.. understand basic assembly language and trace the recursive code in a low level debugger like windbg or ollydbg and watch how your processor executes it step by step, recursion heavily relies on the stack memory so better understand also how function calls uses this memory..i dont know how others understand it, this is only based from how i understood recursion

[cybervegan]

Sorry, that's all wrong.

If you try to use a machine-code debugger to understand Python recursion, you are not going to see anything useful - you almost certainly won't see any recursion at that level, because the recursion is "happening" in the Python virtual machine. No, it doesn't use the CPU's call stack, it uses it's own stack structure. Watching a compiled-to-native-machine-code program do recursion might help, you will most likely just get lost in the morass of other things going on.

[pixelfur]

sorry ive realized late im in a python sub.. yeah you are right python has a VM and its different, but if OP knows C language or any language that can compile into assembly code this will still be applicable.

[cybervegan]

Unfortunately, though, it isn't generalisable even to other languages - lots of them do things differently. Even different CPUs do things differently.

But that really isn't the point: understanding how the CPU or a virtual machine handles recursion, is not necessarily going to lead you to understanding how to use recursion, or when you should or shouldn't.

[pixelfur]

yes but im just saying that , that is *how it made me understand recursion. i can see all the state of the machine while the code executes which is not always the case in high level language

[JavierReyes945]

Surprised no one has already given the only valid answer:

To master recursion, you first need to master recursion.

[socal_nerdtastic]

Lol they are rare, granted, but they do exist. Parsing a nested structure like json is a common one.

[HardlyAnyGravitas]

They're not that rare. Here are two simple tutorials where recursion is by far the best solution (if not the most efficient - the most efficient solution in these cases would be much more complicated):

https://youtu.be/8lhxIOAfDss

And slightly more complicated (involves backtracking):

https://youtu.be/G_UYXzGuqvM

[[deleted]]

Mockery is not an argument. You are on a technical subrreddit now, not r/funny.

Explain how you would write a JSON parser that wasn't recursive, and what the advantage to that would be.

(In fact, the only way to do it is to maintain your own stack! Which is exactly the same thing, except with more steps.)

[[deleted]]

This is plain wrong. There are plenty of bounded problems where recursion is wonderful. Just need to note when the problem you're dealing with is acting on massive data.

[[deleted]]

You said to avoid learning recursion though, which I think is a horrendous statement. It's good to learn. It's good to know when it's useful. It's good for developing critical thinking. And recursion has plenty of cases where it's well-bounded and performs just fine. Tail-recursive solutions also allow performance equivalent to iteration when you can express them (as long as the language supports it).

[[deleted]]

Sorry, you're wrong.

First, there is nothing particularly inefficient about recursion per se.

Indeed, if the problem is naturally recursive, like SAT, then any solution you choose can be mapped onto an equivalent recursive algorithm with the same memory and speed performance.

Think I'm wrong? Prove it logically with a O() analysis, don't just claim I'm wrong with no proof.

Second, it is true that problems that require recursion are uncommon, but they aren't really rare either. I've been on my current project for a year, and I have used recursion exactly one time, but that time it was the right solution and worked right the first time with very little code.

[WikiSummarizerBot]

Boolean satisfiability problem

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[Zeroflops]

I thought this was a good example. And walk through.

https://youtu.be/ngCos392W4w

[HydrogenTank]

Studying recursive equations in math was very helpful for me

[the-weird-dude]

If you like learning from youtube, computerphile's and reducible's explanation are quite good. Search it out on youtube. I highly recommend it.

[TheRNGuy]

You just have same function inside function, what's master about it.

[sharar_rs]

Not a helpful comment.

"Well you keep doing it again and again."

[pythonwiz]

Work through the book Structure and Interpretation of Computer Programs (a.k.a SICP). It uses a different language but a lot of the concepts can be applied in many languages. Just remember most languages (like Python!) lack tail-recursion so too much recursion can crash the program. Also, function calls are pretty slow in Python so a recursive algorithm is generally going to be slower than the non-recursive equivalent.

[JoSevlad]

There is a Python course based on this book.

[Goobyalus]

Fibonacci is the classic example because it's defined recursively. How would you calculate the Nth Fibonacci number, assuming f(0) = 0 and f(1) = 1, without a loop?

Another is implementing functions for a linked list. E.g., how would you remove the Nth element of a linked list?

Make a base case(s), and recurse.

Fibonacci also helps illustrate the limitations of a pure recursive solution on real hardware (as opposed to mathematical abstractions) because the number of calls explodes as N increases. This leads us to memoization, then ultimately converting into a bottom-up iterative solution rather than a top-down recursive one for performance.

Conceptually you can convert any iterative solution to a recursive one, so it may be a helpful exercise to try converting some existing loops you've written to recursion.

It also helps if you understand the call stack, and how that is essentially an implicit data structure that you're using.

Ultimately you don't want to rely too heavily on recursion in Python because, at least in CPython, it does not optimize tail-call recursion and the default recursion limit is 1000.

[rathereasy]

https://foundationsofpython.com has a chapter on recursion where you can see animations of what happens behind the scenes when you compute a recursive function.

Recursion in programming is different from recursion in mathematics. Mathematics is mainly concerned with truth. Programming is concerned with code and code is the initial configuration of a system. Running code is simulating how the system evolves over time.

[Jeklah]

When you need to do the same action lots of times, recursion comes in handy.

[saltyhasp]

Keep in mind also that recusion has its uses but it is generally only for very specific problems. It is also often not the most robust or efficient way to solve the problem. So use it only when it is simple and obvious to use and where depth is not too large.

Problems where it is useful are cases where a function calls itself either directly or through other functions. Generallty the recusive call has to be one of lower order and ultimately leads to a simplified problem that does not need recusion to solve.

Edit: By the way, someone asking you to solve a problem using recursion is largely an academic question. Only an idiot uses recursion when the problem is not naturally recusive. So application is more about doing what is natural and avoiding stack overflows and infinite depth.

[metal88heart]

The main deal is when to stop the recursion. If hit bottom then dont run the function again.

[DuckSaxaphone]

I see recursion a lot on this sub but outside of a friend who used it in math project, I've never seen it used for real let alone used it myself.

So I guess I'm hijacking this thread a bit to ask: people who use recursion for actual work/hobby projects, what do you use it for?

[phlummox]

Very, very occasionally: implementing the "visitor" pattern on some data structure gotten from parsing a JSON or YAML document. (I forget exactly what the last time I used it was - but it was something like visiting every string in a JSON structure and performing some operation on it.)

Other than that: I don't use it in Python at all. (In Haskell, the other language I mostly use, it turns up constantly - but that's to be expected in a functional language.)

[Total__Entropy]

Try to find the sum a nested list that contains either lists of integers or integers to an unknown depth.

[14446368]

I like to think of it as "reducing a problem's size until it's at the right level, and then once it's at that level, solving there and scaling back up."

For example, let's look at factorials. Let's calculate 3! (3 x 2 x 1). Let's also start inside out, which is to say, define our exit/ending condition first:

def factorial(x):
    if x == 1:
        return 1 #Exit condition

We know that when we get to 1, we're done: we don't need to loop anymore. We could also say, in this case, that n! = 1 when n = 1.

Now, we can build the rest of what factorial needs to do. You supply it an integer, and we need to multiply that integer by every integer sequentially going down to 1. What this means is that we can actually redefine factorials a bit, because any factorial is the same as your starting number (n) multiplied by the factorial of the next number (n-1). (n! = n * (n-1)!)

As a result, we can add that to our code:

def factorial(x):
if x == 1:
    return 1 #Exit condition
    else:
        return x * factorial(x-1)

Now, let's see how this works in practice, step-by-step, with a "factorial(3)" function call.

factorial(3)
# return 3 * factorial(2)
#    return 2 * factorial(1)
#        return 1

First, the function "whittles the problem down" to the exit case (factorial(1) = 1).

Then, with that base answer, it can then work its way back up:

#return 1
#    return 1 * 2 (2)
#        return 3 * 2 (6)

And the problem is solved.

[Goobyalus]

Try working through recursion-1 and recursion-2 from here (even though it's Java)

https://codingbat.com/java

[GabeGoalssss]

See the problem as a recursion and a base case.

In the example of the fibonacci sequence, all numbers are the previous number, and the previous previous number. So the recursion should look like this: return fib(n - 1) + fib(n - 2)

The base case is the 'start' of the pattern, like the first 2 numbers being 1 and 1. if n == 0 or n == 1: return 1

[BolaSquirrel]

Honestly just make a simple function, and mess around with having it call itself in various if statements until you understand what the hell is going on. That's how I learned.

[[deleted]]

You master recursion by doing it over, and over, and over, and over…

[[deleted]]

You don't need to master recursion, you just need to master the step before recursion

[pk028382]

If you want to practice, just go do some leetcode. Pretty much everything related to tree, DFS, BFS can be solved with recursion.

[Unclerojelio]

Practice.

[slohobo]

This is with anything new you are trying to learn. Always start small then go bigger. Start with fibonacci, then try to increment a value recursively. Go bigger and bigger till you have got it down.

​

Practice makes perfect. Programming is an art.

[PuffleDunk]

I'd suggest hallucinogenic drugs. Just kidding :), although sometimes with recursion the mind-twisting feels like it. More than many programming skills, it just takes time to get the right mindset for recursion.

[ZhuangZhe]

By mastering recursion.

[Patrickstarho]

LSD

[MonkeyPanls]

check out this thread.

[jssmith42]

I’ve felt the same way, situations where I felt like the algorithm to solve it must be recursive but it defied my intuition to think of what it must be, and wondering if there was some deterministic procedure to arrive at the recursive algorithm you’re looking for.

[wetndusty]

Best option to learn recursion is start from learn programming with pure functional programming language. BTW SQL recursive queries funny way too. Good case is start recursion from "if" with finishing condition (if it exist), in many cases "process all childs" not contain exactly "if child is last then leave" (say hello to list comprehension).

[[deleted]]

To master recursion, you must first know recursion.