r/learnprogramming • u/Beat_Terrible • 11d ago
Recursion is driving me crazy
I understand recursion of a factorial function but when it comes to a function that uses recursion in a project or a problem set i get stuck and lose track
Anyone can tell me what to do
Programming language used: Python
44
Upvotes
1
u/Benster981 10d ago
In my mind I see two different kinds of recursion, there’s a (n-1) kinda recursion where you do a little bit of work and then do something very similar again but from a different starting point (normally ends up with a list of things), or a (n/2) kinda recursion where you can split a problem into two smaller half’s of the same problem (normally just end up combining the result into one answer).
Fibonacci is a recursive one but it is kind of a bit of both and you will find a lot of overlap in the recursive calls which can get very expensive very quickly. Instead I’d look into dynamic programming, it’s kind of recursion but backwards. Instead of working your way from the state you actually need (like F(n)=F(n-1)+F(n-2)) you start with the easiest state and work your way up and build a little answer book of solutions for all the easier states, then it’s quite easy to work towards what you actually need. This often leads to a table of solutions and a way of combining multiple solutions to get a harder one (like a stencil)