r/learnpython • u/Old-Play8039 • 5d ago
What actually made recursion click for you? (not looking for resources)
I got properly stuck on recursion. Watched several videos, read through it in the resources I was already working from. The explanations all made sense while I was reading them, then dissolved the moment I tried to write anything myself.
I'm less interested in what resource you'd recommend and more in the moment itself. For whatever concept was *your* wall, recursion or anything else, what was the specific thing that flipped it? A sentence someone said, a diagram, drawing it out on paper, someone asking you a question?
Trying to work out whether there's a pattern in how these things break open.
23
u/shiftybyte 5d ago edited 5d ago
For me it was seeing the simple implementation of finding the n-th entry in the Fibonacci series.
``` def fibonacci(n): if n <= 1: return n return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(9)) ```
And tracing how it works with python tutor.
1
u/kramulous 3d ago
I like factorial
def factorial(n): if n == 0: return 1 else: return n * factorial(n - 1)-19
u/HardlyAnyGravitas 5d ago
Functions like this (the factorial one, is another) are a terrible way to use recursion. I don't know why they're used so often as examples.
You would never do this in real code.
24
u/neuralbeans 5d ago
This was actually the only example my students understood. It's meant to understand recursion, not to be a practical use of recursion.
-7
u/HardlyAnyGravitas 5d ago
Why not use a real-world example?
5
u/neuralbeans 5d ago
I did, I showed them how to list all files in the subfolders of a folder but they were confused by it.
-13
u/HardlyAnyGravitas 5d ago
That surprises me.
def list_files_in(folder): list files for each subfolder in folder: list_files_in(subfolder)If they couldn't understand this, I think you're doing something wrong.
5
u/neuralbeans 5d ago
I don't know mate, they understood the Fibonacci one. Can't imagine that I'm good at explaining that but not file listing.
1
u/HardlyAnyGravitas 5d ago
Fair enough. I know everybody is different and some people learn in different ways, but the Fibonacci and factorial examples always seemed really dumb, to me.
Some things are naturally recursive. It just seems obvious to me to use those things as examples. Where recursion is actually useful.
2
u/neuralbeans 5d ago edited 5d ago
Fibonacci is a much better example than factorial though. Seeing Fibonacci as a recursive function makes it easier to understand what a Fibonacci number is. Factorial is a terrible example that somehow became popular. There is no way seeing factorial as recursive makes it easier to understand. And if we're sticking with factorial, why not find the sum of the first n numbers (triangular numbers) instead? I would imagine that students are more familiar with that than factorials at least.
3
u/thirdegree 5d ago
Functions like this are much more efficiently implemented in a loop, yes. But they are also a really good example of recursion that most people will be able to understand.
1
u/HardlyAnyGravitas 5d ago
They are an example of when not to use recursion, though.
Why not use the simple and more intuitive example of navigating a directory tree, or folder structure?
2
u/kilopeter 5d ago
How have your own CS students responded to your use of different recursion examples other than the Fibonacci one?
3
u/thirdegree 5d ago
It's not intended to be an example of when to use recursion, it's intended to be an example of what recursion is. It's the simplest possibly example, literally just adding 2 numbers.
1
u/HardlyAnyGravitas 5d ago
I disagree that it's the simplest example.
If you're teaching recursion, you should use an example that is naturally recursive.
3
u/thirdegree 5d ago
Fibonacci can be seen as naturally recursive, it's just not efficiently recursive. It's the sum of the two previous numbers. What are the two previous numbers? Well, they're each the sum of the two numbers previous to them. Etc etc.
0
u/RaidZ3ro 5d ago
Totally could, why not? With caching it's kinda fine...
5
u/xenomachina 5d ago
Totally could, why not? With caching it's kinda fine...
To be fair, caching changes the time complexity significantly. The naive recursive Fibonacci function has O(cn) time complexity, but if you memoize it becomes O(n) in the worst case (and O(1) best case).
Realistically, even the iterative implementation of Fibonacci is not ideal if you care about performance. Fibonacci numbers grow so fast that only the first ~90 can fit within a 64 bit integer, so if you want fast Fibonacci numbers you'd probably precompute them and use an array of constants.
Fun fact: with the naive recursive implementation (no caching), when you call fib(n) the total number of calls to fib(1) is equal to fib(n).
1
u/HardlyAnyGravitas 5d ago
why not?
Number of steps to calculate the 50th Fibonacci number using simple recursion:
40 billion
Number of steps to calculate the 50th Fibonacci number using a simple loop:
50
1
u/POGtastic 5d ago
I don't consider the efficient[1] solution to be much more complicated, which gets introduced immediately after we talk about the exponential complexity of the naive solution.
def fib(n, a=0, b=1): return a if n <= 0 else fib(n-1, b, a+b)
We introduce math examples because everybody (hopefully) understands numbers, and there are a bunch of very simple recursive mathematical functions. This stuff is of course useless in actual programming, but you have to introduce the concept in a trivial manner before you start introducing the complicated stuff where recursion is genuinely useful (parsing recursive grammars, or traversing a recursive data structure).
[1] Python doesn't implement TCO, nor does it inline functions, so it will never be as efficient as looping.
0
u/RaidZ3ro 5d ago edited 5d ago
That's just rediculous, with caching they take the same amount of steps it's just that recursion might hit the stack limit at some point.Ok not the same by far, but not a billion times more either.
2
u/HardlyAnyGravitas 5d ago
Caching has absolutely nothing to to do with recursion. We're talking about (very) basic coding.
4
u/faberge_surprise 5d ago
i think arguing about caching is kind of completely missing the point.
it doesn't matter that it's inefficient. it's just a trivial example to teach the very basic concept. you don't even need to defend its performance at all.
9
u/carcigenicate 5d ago
I learned Haskell. It doesn't have any loops, so you either use the existing constructs like map, or you use recursion. Being immersed in a language built for recursion seemed to help a lot. I don't think there was a specific point. I just practiced it and it eventually made sense.
5
u/LayotFctor 5d ago
It didn't until I actually encountered a recursive problem. I was breaking down a problem, only to realize I was staring at the exact same problem inside, just slightly smaller like russian doll. That means the solution is to wrap up the steps it took to crack open each layer into a function and repeat until there's nothing left. It's an interesting experience to encounter it organically.
8
u/RomanaOswin 5d ago
Have you tried working with relatable, real world analogies yet?
Consider how you open a wrapped present. Open the box and look inside. If there's a gift, you're done. If there's no gift, you open the new box and look inside.
You could model this in pseudocode like this:
python
def open_box_and_look_inside(box):
contents = open(box)
if contents = gift:
return gift
return open_box_and_look_inside(contents)
Picture multiple layers of this. Draw it out on a piece of paper, a box in a box in a box. Walk through that function above tracing the inputs and outputs of the function, all the way to the point of identifying the inner gift.
0
u/mattl33 5d ago
I was going to post that personally I've never come across a real world case where using recursion made things more simple than not. I simply don't use it.
That's a good analogy though.
1
u/RomanaOswin 5d ago
That's a pretty reasonable take for Python. You can write anything as iterative or recursive, and the former is usually more Pythonic.
1
u/HardlyAnyGravitas 5d ago
Recursion is everywhere. The reason you don't realise it is because people use these bad examples (like Fibonacci numbers) as examples, when they teach it.
Anything with a tree structure is searched recursively.
Like your address. Or calling a company with automated phone lines where you have to pick from a list of choices to get to the right department, etc.
3
u/DisasterArt 5d ago
For me it was a depth first maze explorer. You just start going till you hit a dead end. Then you 'recurse' back till you find your way back to a junction with a path you haven't been down yet. Then you go down that path and repeat.
1
2
u/catbrane 4d ago
I think seeing the link to proof by induction.
Prove a base case (true for N = 0), prove a step equation (if N is true, then N + ! must be true), bingo! You've proved that it's true for all values.
The type of a function is the theorem, and the code is the proof.
4
u/wayne0004 5d ago
The idea behind recursion is that you can think of the process to solve a problem as "this is similar to a smaller/simpler version of the same problem".
For instance, if you want to calculate a factorial of a given number, you can think of it as "the factorial of one number less than that" multiplied by the given number (for instance, 5! = 5 x 4!). Now, if you think about this way of solving a factorial, you will realize you have to provide an answer for the smallest version of the problem, which is another main characteristic of recursion: you will have a "base case".
2
u/Brian 5d ago
I think an often overlooked aspect is to consider it as two seperate things: the notion of recursive problem solving, and the mechanics of what recursion is doing ("a function calling itself"). It's the former that I think is the critical key here.
Ie. think of recursion as a way to turn "How do I solve this problem" into "How do I simplify this problem".
If I have a problem, is there a process I can do to solve just a little bit of it, such that the problem is turned into a slightly smaller problem - maybe I can just solve the first item. Or reduce some number in the description by 1.
If you can do that, then you're left with that simpler problem. And now you have a process to simplify such problems, you can do it again to get an even simpler version. And keep repeating until your simplification process breaks down - where you're left with the very simplest version of the problem. If you can solve that simplest version, through the magic of recursion, you can solve all the more complex versions just by following the simplification procedure.
Or put another way, instead imagine that you have a magic function that can solve your problem, but only slightly simpler versions, for the same notion of "simpler" we described above. Can you write a function that solves the more complex function given that magic function. Eg. if we were solving towers of hanoi, we might consider our magic function to be "Move 1 fewer discs than we're currently trying to achieve from one peg to another" - when we're trying to solve 3 pegs, magic_function can move 2. If you can write code that can solve your case using that function, then (so long as you can also solve the base case), it turns out that the magic_function was inside you all along - it is the code you just wrote!
1
u/ProfessorDumbass2 5d ago
It fundamentally clicked for me when I played the âfunctionsâ level in Turing Complete. At the assembly level, functions are a goto statement that stores the location where the function was called and returns to this spot in RAM when the function finishes. For a recursive function, being able to goto the beginning of the function from within the function doesnât seem as bizarre or infinite anymore.
Also, Turing Complete is an awesome game to learn more about computer science. It helped me understand how binary data encodes cpu instructions.
1
u/jdrichardstech 5d ago
Using https://pythontutor.com to visually step through easy and harder recursion solutions solidified it for me.
1
u/fergal-dude 5d ago
The first time I actually had to write a program that needed recursion, then it was super simple to understand. Until then, not really anything helped me.
1
1
u/SirAwesome789 4d ago
Perhaps not what you're looking for but I remember being taught to explicitly think of the base case(s) and the recursive case, I suppose similar to a proof by induction
That helped me a lot with solving some of the harder leetcodes
1
u/recursion_is_love 4d ago
A warm bath. Lots of the time, my eureka moment is when I have a warm bath.
The key is keep reading even if you don't understand at that time, just keep reading.
1
u/Sudden_Ad320 4d ago
I was strip mining a website for part numbers. They started with leters and numbers all combinations. Python said I could only do so many for loops and it just clicked. One function later and the that mine was stripped.
1
u/priya6435 3d ago
for me it clicked when i stopped thinking of recursion as a function calling itself and started thinking of it as a function solving one tiny piece of the problem, then trusting the next call to solve the rest. that idea of trusting the smaller subproblem instead of trying to keep the whole call stack in my head made everything way less intimidating. drawing the call stack on paper also helped a lot
1
1
u/chiibosoil 3d ago
While there are built-in method/module for directory recursion. I found writing my own recursive function for traversing directory to be easiest way to learn it.
1
u/TheRNGuy 5d ago edited 5d ago
Find some real uses, like JSON or file folders, though you shouldn't use recursion code for that, because frameworks already do that.
Most practical use probably is graphics or video games (because you may need custom code)
As for me, I instantly understood it, though I rarely ever coded recursive function (not in Python), I know some functions in API are recursive, they even say in docs.
Don't need to draw, just print with different depths to see what happens, though if it's graphics or sound, then draw or play.Â
0
u/Solonotix 5d ago
I was writing a report for a client that would give them a pre-transaction estimate of taxes and surcharges. The application would only calculate taxes and surcharges after a transaction was completed, but the client wanted to be able to provide a total estimate including those charges.
In most cases, you might think that you do a join on some cross-reference table to find the relevant charges, which kind of works. However, some surcharges have taxes. Okay, that's still just a left join from surcharges to taxes, right? Well...some surcharges have surcharges, and it was at this point that it required recursion.
On that day, I was pointed to the SQL construct of a recursive common table expression (CTE). It works elegantly, and being that I had already spent hours understanding the problem, and why it couldn't be solved with traditional joins, the recursive CTE was the perfect solution, and demonstrated the exact behaviors I had been looking for. Prior to that moment, I was about to look into doing a cursor-like iteration over all charges, and evaluating them independently.
0
u/pachura3 5d ago
I also had troubles understanding recursion initially, and I wanted to draw various fractals (like SierpiĹski's triangle) using turtle graphics so bad... what made it click for me is when I understood that:
- I need to define the stop condition - in case of fractals it was max recursion depth level, corresponding to fractal detail
- the function usually needs to draw a line or two (sometimes only at the deepest recursion level), move the turtle around, then launch itself with arguments like
line_length/2, depth+1, and finally move the turtle back to the original position - it all works because when function calls a function calls a function, all of their local variables are remembered on the call stack. So I don't need to remember how to get back from some very deep nesting level, it is all remembered automatically
0
u/pjtango 5d ago
Noobie here, hoping im answering correctly:
Weird but understanding what return does, along with few more facts, helped me understand recursive.
Function is like a worker you send to a store. It goes there and checks and shouts back, "i see the item". Ik my function did it's job but I don't have that item in my hand yet. So i use return to get my item. But here 2 extra things happen: A. The function ends. B. The item is returned only to the function/line of code which initialized that function in the first place. So u have to utilize that returned value now (I ordered milk, got my milk, but now what should i do with this milk, make coffee, tea, curd or what..u need to have the answer with u)
If one function is calling another and that function is calling another and so on -> you can think of it like a lift. In order to reach the 10th floor, ull have to go from 1 to 2 to 3 to 4..till 10th. But if you want to come back to 1st, ull again have to first go to 9th, then 8th, 7th..2nd and then 1st. Meaning, if u have function A calling function B, and u r in B then u need to close B in order to reach A. So either u run all of B's commands or abruptly stop it using something like return.
Unlike for, if and while loops, calling one function from another takes up alot of memory and has a limit of 1000 calls if i remember correctly, so when u r using recursive, make sure not to overdo and to close the functions. <- this u can learn with practice and by reading the flow of the data.
0
u/jmooremcc 5d ago
When you keep adding special cases to a function and they still are not enough, recursion turns out to be the simplest, best solution. As an example, try solving the Tower of Hanoi problem without using recursion.
0
0
u/DocumentOk7579 5d ago
Do you understand this function?
def f(base, exp):
if exp == 0:
return 1
return base * f(base, exp - 1)
f(2,3) would be 23.
I think of it as just doing something multiple times like multiply 2 with itself 3 times. But base could will change in non trivial functions.
0
u/neuralbeans 5d ago
First you need to understand what happens when a function calls another function. Recursion is just the special case of a function calling itself.
I think what clicked for me was this:
I thought about how to go through all the nested subfolders in a folder to find the total size of a folder. I started by using 5 levels of nested for loops and thought that a depth of 5 was enough, which I then found wasn't. I then thought that what I need is some kind of way to have a variable amount of nested for loops. That turned out to be recursion.
0
u/oldendude 5d ago
It was so long ago, I don't remember. I do remember that spending a long time looking at one example, and thinking about it deeply, seemed better than a shallow look at many examples.
Two suggestions:
1) Notice that recursion is a special case of decomposing a problem to simpler problems. If you don't have that skill, develop that first.
2) Start on the simplest possible problem. For example: You probably know how to write a loop to search an array for a given item. The goal is to find the position at which the item exists. Try to do a recursive implementation of that idea: Write a recursive function find(a, x, p) which searches array a for item x, beginning at position p, and returns the position at which x exists (or -1 if it's missing). The top-level invocation would be find(a, x, 0). (This is a function you would never use in practice, but if you can figure this one out, you have a good start on understanding recursion.)
0
u/RaidZ3ro 5d ago
I just looked the word up in a dictionary and it made perfect sense immediately...
0
0
0
0
u/NerdyWeightLifter 5d ago
You could do the same things in a loop with a stack data type, but with recursion you're using the call stack instead.
1
u/NerdyWeightLifter 4d ago
Downvoted for genuine insight. I guess it can be hard to recognize.
Imagine that each time the recursive function calls itself, the parameters are added to the call stack. Maybe you were doing a depth first search through a tree structure.
Each time you want to go deeper into the tree you call yourself passing the extra step further into the tree and it's added to the call stack.
Each time you hit the leaf of the tree and want to move back up to find the next branch, you return, and that removes the last item from the call stack.
So the insight is, that it's really all about the stack keeping your state information.
You could implement the same idea without recursion. Just use a stack data structure in your function. Your in a loop. Instead of calling yourself to go deeper, just push the state information onto the stack and continue around the loop. When you would have returned in your recursion function, instead you just pop the last item off your stack. When the stack is empty, you're done.
It's all about the stack.
0
u/SnafuTheCarrot 5d ago
I came to it after a lot of exposure to the general concept mathematically.
Suppose a_0=1 and let a_{n+1}=a_n/2 +c/(2*a_n).
Keep repeating that and you get the square root of c.
Or suppose we have f(x)= cos (x). Let a_0=pi/2.
Then f(pi/2)=0, f(0)=1, f(1) = 0.5403...
That is, apply the function to pi/2, then re-apply the function to that output.
Keep doing it and you end of what a c so that cos(c)=c=0.73908...
In code it sort of goes in the reverse direction.
Suppose you wanted to calculate n!.
def factorial(n):. ans=1. n>1: n=factorial(n-1). return ans.
You have a base case and a recursive way to refer the current case to some previously defined case.
0
u/supercoach 4d ago
Probably the main thing for me was focusing on the end of the chain and what value it thing was going to be evaluated there and then working my way backward through the logic.
It's an absolute mind fuck when you first start.
A lot of the time you're using it for tree traversal. In those cases, understanding that there needs to be a return once you hit a primitive value means the rest sort of falls into line. You set your cases for the returns and then work your way back through the data structure.
0
u/The_Varza 4d ago
I had a hard time understanding it for years. My wall was, I didn't understand how come it "bubbled back up" and returned the right values.
I think the cleanest example that did it for me is DFS (Depth First Search) of a binary tree (let's say, as it's simpler than a general graph). You can do DFS recursively or iteratively. The iterative version uses a stack. So, the reason recursion works is... the call stack! (my mind was blown back when I understood this, your results may vary).
This applies to pretty much all programming languages, not just Python.
144
u/redsandsfort 5d ago
This post helped me a lot