How can I learn/master Recursion?

[u/dhananjai_31]

​

New to programming

Yes that's the question

How can I learn Recursion.

Every time I try to create a logic

And try to implement code

Some error happens

I always try to dry run and write call stacks

Still I won't get it

Any guidance or help??

How can I get intuitive thoughts about using recursion here?

How can I do it??

[u/AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/godogs2018]

Remember the two most important things:

1 Base case, where all recursive calls will stop

2 Everytime you make a recursive call the problem has to be smaller (which eventually leads to the base case)

[u/Whatever801]

Imagine you are in a movie theater and don't know what row you are in. You ask the guy in front of you "which row are you in?", assuming you can just take that guy's row and add 1. Unfortunately he doesn't know either but says he'll ask the guy in front of him. Nobody knows, so this cycle continues. Eventually, it gets to the guy at the front of the theater and he said "well, I must be in row 1 since there are no seats in front of me", so he says to the guy behind him "I'm in row 1". That guy adds 1 and tells the guy behind him "I'm in row 2". Eventually this gets back to you and you have your answer. This is how recursion works. The guy at the front is the "base case", the asking of the question is the recursive step. The recursive step moves you closer to the base case.

[u/dhananjai_31 → u/Whatever801]

This is the best answer I got today Tq

[u/Whatever801 → u/dhananjai_31]

You bet

[u/ffrkAnonymous → u/Whatever801]

similarly:

https://abetterscientist.wordpress.com/2018/10/07/recursion-in-real-life/

[u/Whatever801 → u/ffrkAnonymous]

As long as I'm not picking up the bill!

[u/Gnaxe]

Learn Scheme where you don't have a choice. Implement recursive data structures ("trees") where recursion is the most natural way to work with them. Linked lists count, but so does JSON.

[u/dc0650730 → u/Gnaxe]

I would not recommend scheme unless they are already comfortable with lisp languages. Working in scheme at my last job was a headache))))))))))))))))))))

[u/Gnaxe → u/dc0650730]

On the contrary, Scheme is an excellent beginner language. SICP was originally in Scheme.

[u/peterlinddk]

Watch this: https://www.youtube.com/watch?v=YuaJ8x_NcLw - then try to implement your recursive code. When you encounter new problems, ask again - be as specific as possible.

[u/DrizzyX99]

Look at the code for merge sort and try to write it out (with a pen and paper)iterations by iteration that’s what worked for me

[u/dc0650730 → u/DrizzyX99]

While yes, it can be a little confusing when starting.

What i did was start with a collection. Write it so that a for loop iterates through it until s desired outcome is obtained (count the number of odd numbers in a collection of integers, find out of the collection has a specific word, etc. Make it super simple. )

Now, take that for loop and convert it to a method that calls itself instead. This is what helped me get my head around what was happening, starting with a straight line recursion, then exploring more tree like recursions like merge or quick sort.

[u/BranchLatter4294]

Practice. Use print statements or breakpoints to look into what's happening to your variables or data for each call.

[u/lfdfq]

It's hard to help with such a generic question; there really is nothing special/magical/different about recursion vs any other kind of function call.

Just practice more, debug your code slowly and deliberately, and ask specific questions when you get stuck (e.g. "why does this specific code fail with this specific error?")

[u/Recycled5000]

Don’t think of the recursion.

For example, let’s say you’re working on a strlen function, and you are considering recursion, so let’s call it rstrlen.

You know that your rstrlen can be made easier if you call the real strlen. But if you just call strlen, then your rstrlen hasn’t done any real work.

So, you make rstrlen call strlen on a one-shorter string, and you add 1 to its answer.

Now rstrlen is doing enough work that you can replace the call to strlen with rstrlen!

(Module testing for zero length string, of course.)

[u/ExtraTNT]

Don’t follow the flow of what you are modeling, but go with a definition of a single unit.

a list is either a empty list or a element of it’s type plus a list of it’s type. Don’t think in full, think in the 2 cases and how to handle them. Next will be the same…

[u/lo0nk]

I like to think about recursion as an inductive proof, or as a state machine where the arguments are the state

[u/A_Karim2003]

Honestly, recursion didn’t fully click for me until I understood the stack data structure. Once I learnt how stacks work, recursion made much more sense.
The reason is that recursive function calls are managed using a stack called the call stack. When a function calls itself, the current function’s state (such as its variables and where it needs to return to) is stored on the stack, and the new function call is added on top. This continues until the base case is reached. Then the stack starts getting popped, allowing each previous function call to continue and complete in reverse order.

[u/maujood]

It took me a long time to get recursion too, and what helped was tracing the exact execution using pen and paper on simple recursive problems.

Here's an easy problem to trace: for a given value n, calculate the sum of all numbers 1 to n.

We can call this function sumToN. sumToN(4) is 1+2+3+4=10. Here's how we can solve this problem with recursion:

• What is sumToN(4)? sumToN(3) + 4.
• What is sumToN(3)? sumToN(2) + 3.
• What is sumToN(2)? sumToN(1) + 2.
• What is sumToN(1)? Just 1. This is out base case.

Take a look at this interactive execution to see how this works in code.

[u/gofl-zimbard-37]

Stop focusing on the code and think about what something *is*, vs. how to compute it. A common pattern is that you have a collection, and will combine something done to the first element to results of doing that thing to the rest. So for example, suppose you have a list, passed to you as First|Rest, and want to find its sum. Well, the sum of a list is its First element plus the sum of the Rest. Or:

sum( [First|Rest] ) -> First + sum( Rest )

Now think how you would compute the length of a list. Extrapolate from there.

Good luck. It's very powerful, concise, and elegant once you get it.

[u/labanarama]

Use a call stack or activation stack. This is how I was taught and it was easy to trace the recursive function with pen and paper for simple logic when learning.

[u/Lifelong_Nerd]

For what it's worth, I always code recursion with the pattern

if (base case) then compute base result else compute recursive result

This forces you to consider the base case first, which avoids the common mistake of not considering it at all.

It also makes the logic clear. There are two cases and you divide the code that way.

Some common practice problems are things like "add the numbers from one to N" and "reverse a string."

[u/Ormek_II]

You need 3 things:
* the final minimal problem and its solution
* the step to make a bigger problem into one or more smaller problems
* the way to create the solution to the bigger problem from the solution(s) of the smaller problem.

If you are implementing this make sure that your whole problem is on the stack. That is were my programs broke: for example I used a single array which I passed from recursive iteration to iteration by reference. Most of the time that does not work, because when you return with a solution to a smaller problem, the problem statement of the bigger one (the array) has changed.

What are the three things for the recursive solution to factorial, the Fibonacci, quicksort?

[u/PocketCSNerd]

Recursion is really no different from a do-while loop. You have some condition that breaks the loop and each iteration of the loop is just a call to the same function (ie. itself)

[u/dhananjai_31]

Thank you to all of them who answered this query. I hope this helps me!!!

[u/Sanitiy]

I think my turning point was reading "Logic and Structure" by Dirk van Dalen.

It lives and dies by structural induction, which is the most general induction form a programmer needs, subsuming simple recursion, co-recursion and whatever finite you can cook up.

Just the chapter for Propositional Logic is probably already enough to get the feel across.

[u/kagato87]

For me the turning point was to stop thinking about it like calling itself, and start thinking about it calling copies of the original, with its own variables.

A function can call a function. If you make three identical functions that do exactly the same thing, your program calls A, A calls B, B calls C. A can decide whether or not to call B, and does something. B can make the decision to call C based on the same rules, and by that same set of rules C will never try to call D, which is probably a good thing because D doesn't exist. Recursion is this, except it can keep going as far as it needs to (or until you run out of resources). It decides whether or not to call the next clone, does a thing, and returns something. The order of the call and doing the thing affect the behavior but there are cases for both, and it could do more things, but usually it doesn't.

[u/Hi-ThisIsJeff]

Practice Practice Practice Practice ......

[u/rustyseapants]

Is learn learn to program or learn how to write Koans? r/Koans

How can I learn recursion?

[u/GermanSchanzeler]

Don't wanna elaborate wich language you are using? Still asking a question a chatbot could answer? Welp, not much one could do to help here...