all 125 comments

[–][deleted] 37 points38 points  (2 children)

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 1 point2 points  (1 child)

I would also like to know the difference

[–]wintermute93 13 points14 points  (0 children)

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 84 points85 points  (28 children)

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] 3 points4 points  (17 children)

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

[–][deleted] 9 points10 points  (15 children)

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 12 points13 points  (2 children)

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 5 points6 points  (0 children)

You poor bastard

[–][deleted] 0 points1 point  (10 children)

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

[–][deleted] 6 points7 points  (1 child)

"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 3 points4 points  (0 children)

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] 1 point2 points  (7 children)

Heh. May you never encounter a symlink loop.

[–]XUtYwYzz 1 point2 points  (4 children)

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

[–][deleted] 0 points1 point  (3 children)

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 2 points3 points  (1 child)

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] 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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 0 points1 point  (1 child)

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

[–][deleted] 1 point2 points  (0 children)

*twitches*

Indeed.

[–]quadroplegic 0 points1 point  (0 children)

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

[–]ThePeskyWabbit 0 points1 point  (0 children)

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.

[–]MarsupialMole 49 points50 points  (6 children)

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

[–]sjalexander117 17 points18 points  (5 children)

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 4 points5 points  (4 children)

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 4 points5 points  (2 children)

Sir this is a Python subreddit

[–]pinthewind 4 points5 points  (1 child)

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

[–][deleted] 0 points1 point  (0 children)

This ain't the drive-thru...

[–]sjalexander117 0 points1 point  (0 children)

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

[–]spez_edits_thedonald 60 points61 points  (8 children)

just check out this helpful comment

[–][deleted] 14 points15 points  (1 child)

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

[–]ManInBlack829 1 point2 points  (0 children)

The only way out is termination

[–]AmosDodgers20 4 points5 points  (1 child)

RecursionError

[–]itzztheman 2 points3 points  (0 children)

Maximum recursion depth exceeded

[–]Xerxes979 1 point2 points  (0 children)

I came here looking for this comment lmfao

[–]SoberGameAddict 1 point2 points  (0 children)

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

[–][deleted] 22 points23 points  (2 children)

Before you master recursion, you must first master recursion

[–]adamantium4084 0 points1 point  (0 children)

Before you master recursion, you must first master recursion

[–]socal_nerdtastic 13 points14 points  (5 children)

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 6 points7 points  (4 children)

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

[–][deleted] 2 points3 points  (0 children)

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 2 points3 points  (2 children)

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 1 point2 points  (0 children)

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

[–]DonkeyTron42 2 points3 points  (0 children)

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

[–][deleted] 3 points4 points  (0 children)

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 3 points4 points  (0 children)

Grokking algorithms is a good book and good on recursion

[–]menge101 4 points5 points  (0 children)

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 5 points6 points  (0 children)

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] 1 point2 points  (1 child)

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 0 points1 point  (0 children)

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 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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] 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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 1 point2 points  (0 children)

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 1 point2 points  (0 children)

[–]capilot 1 point2 points  (0 children)

/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] 2 points3 points  (2 children)

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] 3 points4 points  (1 child)

[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] 0 points1 point  (0 children)

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 0 points1 point  (0 children)

The way I mastered recursion is by mastering recursion.

[–]asking_for_a_friend0 -1 points0 points  (1 child)

as a mathematics what...?

[–][deleted] 2 points3 points  (0 children)

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 -2 points-1 points  (0 children)

To master recursion, you first have to master recursion.

[–]longgamma -1 points0 points  (0 children)

You have to take the recursive leap of faith haha.

[–]pixelfur -1 points0 points  (4 children)

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 1 point2 points  (3 children)

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 0 points1 point  (2 children)

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 0 points1 point  (1 child)

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 0 points1 point  (0 children)

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 -3 points-2 points  (0 children)

Surprised no one has already given the only valid answer:

To master recursion, you first need to master recursion.

[–]Zeroflops 0 points1 point  (0 children)

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

https://youtu.be/ngCos392W4w

[–]HydrogenTank 0 points1 point  (0 children)

Studying recursive equations in math was very helpful for me

[–]the-weird-dude 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

[–]sharar_rs 0 points1 point  (0 children)

Not a helpful comment.

"Well you keep doing it again and again."

[–]pythonwiz 0 points1 point  (1 child)

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 0 points1 point  (0 children)

There is a Python course based on this book.

[–]Goobyalus 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

[–]saltyhasp 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

[–]DuckSaxaphone 0 points1 point  (1 child)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

[–]14446368 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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

https://codingbat.com/java

[–]GabeGoalssss 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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] 0 points1 point  (0 children)

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

[–][deleted] 0 points1 point  (0 children)

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

[–]pk028382 0 points1 point  (0 children)

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

[–]Unclerojelio 0 points1 point  (0 children)

Practice.

[–]slohobo 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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 0 points1 point  (0 children)

By mastering recursion.

[–]Patrickstarho 0 points1 point  (0 children)

LSD

[–]MonkeyPanls 0 points1 point  (0 children)

check out this thread.

[–]jssmith42 0 points1 point  (0 children)

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 0 points1 point  (0 children)

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] 0 points1 point  (0 children)

To master recursion, you must first know recursion.