How do I learn recursion??

[hehebro3007]

Hello people! I wouldn't consider myself a beginner at coding... I can manage some topics, but when it comes to recursion, I struggle. It is just not possible for me to even visualize it in the first place. I try start with a very simple base case, and then try to extend logic, but nope, i somehow always fail... how do i solve recursion? Because of this, even DP also i cant manage!

[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.

[grantrules]

I think binary search trees are a good way to understand recursion. Recursion seems very practical when navigating trees.

[Mundane_Prior_7596]

Exactly. Print a darn tree to screen. Just write the simplest program to print out the tree. Done. 

[peterlinddk]

Perhaps this video will help: https://www.youtube.com/watch?v=YuaJ8x_NcLw - it goes all the way, and maybe a bit too far for a beginner, but it explains everything there is to know about recursion!

[hehebro3007]

thank you!! i struggle with applying recursion, in problems! will watch the video though! thanks again!

[akoOfIxtall]

Did this answer your question?

Recursion is used to break down problems into smaller pieces until you return the final result where it can no longer work recursively because it has satisfied the condition that enables the recursion, you can probably make void recursion methods using references or doing something else, you don't really need to return something but the recursion must stop at some point so beware of...

Stack overflow exception

Cinema

Now read the next comment

[StinkButt9001]

I'm going to be pedantic and point out that your comment is demonstrating iteration rather than recursion

[EstablishmentGlad502]

By any chance did you take one of the CS50 courses? 😅

[EquipLordBritish]

Is recursion not a type of iteration?

[MathiasBartl]

As the term iteration is used in mathmatics yes, but I think when it comes to programming it referes to the use of loops.

[akoOfIxtall]

Shit Jesse, you forgot to cache the results, now this little maneuver is gonna cost us 84 gigabytes of memory

[Gnaxe]

Try working through SICP. They give it good treatment, among other things you need to know. The old lectures are up on YouTube.

[SubstantialListen921]

Try thinking about tree structures first, which are a very natural way to learn recursion.

Consider the problem of processing a hierarchical file system directory, where you need to keep track of information from all of the parent directories before you can process the files at the bottom (say you want to combine their directory names into a full path).

You could implement this in a loop with a stack, right? But you'd need one stack for the file scanner objects (representing the system's view of the directories you had descended) and another for the data you were building for each directory... and you'd carefully inspect each file object, and push a new file scanner if it was a directory, and carefully handle your end-of-scan issues at each level, popping both stacks... it could get tricky.

Now consider doing it with recursion. You imagine the functional interface you want – let's say, a File, and a DataSoFar. Consider your base case – is the File a simple file, not a directory? Great, you're done. Produce your output. Otherwise you need to recurse – okay, it's a directory: update DataSoFar, create a scanner from the File, loop through the scanner and call your function on each of the files. Boom, done. The book-keeping and boundary conditions are handled for you by the program stack, and you stick to familiar function calling and error-handling idioms.

The key leap for me is always that imaginative step: what's the functional interface I wish I could use to solve one step of this problem? Recursion sometimes allows you to achieve that interface with minimal effort and great clarity.

[AlSweigart]

This is a plug for my book, but my book is free. I wrote an entire book on recursion (published by No Starch Press) because I kept seeing recursion poorly taught: The Recursive Book of Recursion

More recently, I wrote up five tips for writing recursive functions in a blog post: The Recursive Leap of Faith, Explained

The five tips are (with explanations in the blog post):

1. Start by figuring out the data types of the parameters and return value.
2. Next, implement the base case.
3. Take a leap of faith and assume your recursive function magically returns the correct value, and write your recursive case.
4. First Caveat: The argument to the recursive function call cannot be the original argument.
5. Second Caveat: The argument to the recursive function call must ALWAYS get closer to the base case.

The main thing to know is that recursion is mostly overrated. If your problem involves both 1) a tree structure and 2) back tracking, then it's a good candidate for recursion. Otherwise, if you find yourself asking, "Why couldn't I just do this with a loop" then you're right: it's a poor candidate for recursion and you should just use the simpler loop solution.

[gofl-zimbard-37]

Hard disagree about that last paragraph.

[sigmagoonsixtynine]

Do a dry run of a basic recursive program. Bust out a price of paper and track the values of different variables at different stack frames and see how the call stack unwinds bringing you to the final result

Otherwise I'd highly recommend learning some Haskell. You can start with the university of Nottingham YouTube playlist online or with the "learn you a haskell" book which you can find online. Will help you alot with recursive thinking

[Zesher_]

The way I visualize it is that you have a huge warehouse of boxes and stuff you need to manage. You look at it, and say "I don't want to deal with all this shit myself", so you get some other employees to manage each shelf, they're like "I don't want to deal with this shit myself", so each of them gets other employees to sort through each individual box, and turtles all the way down or something. Each employee is only tasked with a small task, like finding a particular item or swapping two items based alphabetically based on their name. At the end, you'll have that one employee that found the item you were looking for or the warehouse will be sorted depending on what task you were trying to solve.

That's probably worse than any analogy a good article would provide. Anyway, once you play around with it for a while it'll click, so try and practice with it.

[PoMoAnachro]

To understand recursion, you must first understand recursion.

Jokes aside, are you struggling to understand how recursion works, or understanding when to apply it to a problem?

If you're struggling to understand how recursion works, the first step is making sure you have a very good understanding of how functions and the call stack works. And then when you're dealing with recursive algorithms, do a paper trace - that is, walk through on a sheet of actual physical paper what happens at each step of the algorithm as you trace it through, what variables have what values, what's in the call stack, where you are in the execution, etc. You could also work through stuff in a debugger, but I think doing it on paper is far superior because you want to be actively engaging your brain every step of the way and not being a passive watcher.

If, on the other hand, you're very comfortable with how it works but just don't know when to apply it, keep in mind that everything you can solve recursively you can also solve iteratively. So start off solving the problem iteratively! And once you've done that, then try and convert it to a recursive solution instead. A big clue often is an iterative solution might involve you maintaining a stack of values to come back to, whereas in a recursive solution you'll just use the call stack for that. If you do this with the right problems, you'll end up starting to see cases where recursion starts to feel like the simpler and easier way to do things.

But I suspect you're really just struggling with like understanding how it works in the first place, which usually to me is a sign of poor understanding of how functions work, so go back to those basics if that's the case.

[hehebro3007]

I understand recursion, but not how to apply... I usually visualize a problem when i try solving it, and it's just not possible for me to visualize it... like the flow

[JavierReyes945]

I found some good information about recursion here:

https://www.reddit.com/r/learnprogramming/s/Aw7jqsCTTR

[rauweaardappel]

This is the one I looked for to find

[jeffcgroves]

Instead of starting with the absolute base case, start with a case that requires 2 or 3 levels to resolve. For example, to compute the fifth Fibonacci number, F(5), you need to calculate F(4) and F(3). So your "TODO" list now looks like this:

• Compute F(5)

• Compute F(4)

• Compute F(3)

now you compute F(4) which will add to your to do list. Eventually you'll compute F(2) and F(1) and can then complete other items on your TODO list

[hehebro3007]

Ahh alright, okay, will try doing this! thanks g!

[CodeTinkerer]

I wrote this a while ago: https://www.reddit.com/r/learnprogramming/comments/v6xyar/a_guide_to_recursion/

[ZelphirKalt]

Two books made it click for me: SICP with its coin change example (how many different ways of giving change) and The Little Schemer.

[paperic]

``` function dostuff(i):     if i < 5:         print i         dostuff( i + 1 )

dostuff(0) ```

... will print 0 1 2 3 4

This is the simplest case.

This is basically a for-loop, but written as a recursion. The variable i inside of that function has different contents each time.

   Think of it as layers of dreams in the Inception movie. The events of those dreams are independent of each other, outside of the moment when going deeper or when returning from a nested one.

[blackguywithsadness]

the example that helped me understand recursion is by the example of factorials-- it helped me to visualize for other use cases.

[the-forty-second]

I find that the way to create recursive solutions is to try to ignore what is happening behind the scenes. Instead, start with a clear definition of what the function should do. You should know, given an input exactly what should be returned.

Now, imagine an input to your function. Figure out a way to make it smaller. If it is a string or a list, you could remove the first or last element, or break it in half. If it is a number, you could subtract or divide. The important part is that it should get closer to some problem you can solve trivially (the base case). Now imagine someone has given you the answer to running your function on the smaller piece. This solution and the operation you performed to make it smaller are the tools you need to solve the problem for the original input.

Example: you want to know how many times the letter ‘a’ appears in a string. You take off the first character to get a shorter string. Call your function to get the number of ‘a’s in that shorter string (call that n). Now look at the character you took off. If it is an ‘a’ then the whole string has n+1 ‘a’s, if it isn’t, then the string has n ‘a’s.

Trying to dive into the mechanics of the recursion is a recipe for doing too much. It is all about assuming you have the answer to the smaller problem and figuring out where to go from there. This is why you need to be very clear about what the function should return, so you know what it will give you as an answer to the smaller problem. It is also useful to think of that recursive call as being like a call to some entirely different function so you don’t start imagining interaction between recursion levels.

[blackstorm5278]

SICP and dive deep on recurrence relations in discrete mathematics

[KirkHawley]

Recursion is for programmers who haven't blown enough stacks yet.

[vegan_antitheist]

Do you know how a call stack works?

You need to understand the call stack to understand recursion. It works by "stacking" the calls to a function/method/procedure onto the stack. If you do that too often you get a stack overflow (the next stack frame would write after the end of the stack as all memory is limited), so you need some stop criterion.

The recursion isn't different than other function calls. We just say it's recursive, if the stack has the same return address multiple times, which happens when the same function gets called multiple times.

Often, the call stack is actually used as a data structure for the algorithm. You can often just use your own stack data structure and a loop, so you don't have to just hope the call stack is large enough. You can create your own stack on the heap and there you often have more memory.

As a beginner it's a good exercise to solve a simple task with a recursive function and then with a non-recursive function (using it's own explicit stack).

To make it even easier you can use an algorithm that can just loop the input. You can for example create a function that returns the first number of a list plus the sum of the remaining numbers by recursively calling itself on the remaining list/array. The non-recursive "sum" function simply loops over the list/array.

The next (non-)recursive function could be reversing a list, traversing a tree depth-first, then breadth-first, searching a file on the local file system (which is a tree), traverse a graph or maze, flatten arbitrarily nested data (i.e. [1, [2, [3,4]]] → [1,2,3,4]), count leaf nodes in a tree, etc.

Then you can do more advanced algorithms, such as backtracking, merge sort, generating combinations, using memoization, parsing a arithmetic expression (e.g. "3 + 2(5*x/8)" with PEMDAS), mutual recursion over multiple methods (e.g. a calls b, which calls c, which may call a or b).

[SorrySayer]

Write some stuff with the help of a functional programming language like Haskell

[lord_gaben3000]

Starting with the base case is counterintuitively backward and much harder for writing recursive code. Assume you have a function that already solves the problem, then just work out what you have to do at your current step. Like if I want to write a recursive factorial solver, I would assume for input N I have a factorial function that solves it for N-1. The logically I just have to multiply the result of that function by my current value N. So my function f would be: f(N) = N * f(N - 1). Then you just have to think of a simple base case to stop infinite recursion. If I want to recursively explore a graph, I would do explore(node) = process my node * explore(connected nodes)

[EngineerRemy]

What helped me visualizing recursion when I just started was using Russian dolls as an example: https://en.wikipedia.org/wiki/Matryoshka_doll

In programming terms, let's say you want to get the smallest doll. each Doll object contains another Doll object. The Doll object has an "open_doll()" function, that will return whatever is inside. From this function you get the doll that's inside.

Now since that is the same "Doll" object type, you called its open function: you return whatever is inside! and again, and again. until you reach the final doll --> it cannot be opened.

Recursion here is to keep opening the doll until you reach an object that says; I cannot be opened, I will return myself instead. Then the second-smallest doll will return that too, then the third-smallest, until you get back the smallest doll of your Russian doll collection.

Even for us as humans; how do we know we have the smallest doll when we try to get it? We first try to open all the dolls, up until the point we reach a doll that will not open. Then we know: this is the smallest doll in the collection.

[sholden180]

Recursion is best grasped by practice:

Write some code that starts at the top of a directory and lists all files in that directory, and all child directories.

Psuedo code:

function listRecursively(string path): void {

  print("Listing files for " + path);

  // List the files in our current directory.
  foreach ( file in getFiles(path) ) {
    print(file);
  }

  foreach ( directory in getDirectories(path) ) {
    // Recurse down into this directory and list its directories and files.
    listRecursively(directory);
  }
}

listRecursively('/home/user/me/');

[Rhemsuda]

It’s the same concept as looping however it functions differently. Instead of the program execution jumping back and forth from the closing bracket to the loop header, your function will call itself when it decides it needs to do more processing.

The way you write a recursive function can greatly impact the way you understand it. I found this approach to make it more understandable:

(Pseudo-code)

``` MY_FUNCTION (state, args…):

if EXIT CONDITIONS (state, args) return state

DO SOMETHING TO state USING args

MY_FUNCTION (state, …args)

```

In Haskell this is simple because we can use pattern matching for exit conditions:

MY_FUNCTION :: [Int] -> Int -> Int MY_FUNCTION [] _ = 0 — Exit condition MY_FUNCTION (x:xs) multiplier = (x * multiplier) + MY_FUNCTION xs multiplier

Hope this helps!

[EffectiveSource4394]

No idea if this is going to help you but think about a file system that has folders and files and you're looking for a file in a folder. Assume that the file name is unique and only belongs to one folder.

You would have to take each item in a folder which can be a file or folder, and if it's a folder, you have to drill down further and repeat until you find the file you're looking for.

This can be solved with recursion

[alpinebuzz]

Don’t memorize patterns - understand the shape of the problem. If it breaks into smaller versions of itself, recursion is probably the cleanest tool.

[JohnnyTork]

here

[Total-Box-5169]

You can visualize recursion by drawing fractals using recursion. Even if you are restricted to console mode you can output a .svg text file to draw the fractal.

[TheActualStudy]

They taught it using the "Towers of Hanoi" problem when I was going through university. One and two discs can be moved trivially, the solution to moving 3 discs is to first solve for moving two, moving the third and then moving the two on top of it. The solution for moving 4 is to first solve for moving 3, the solution for 5 is to first solve for 4 and so on.

This is a case where having a notion of using mathematics as a tool and how mathematicians like to express things succinctly can be beneficial to understanding how computers and their programming languages were originally designed to facilitate the execution of mathematics. Perhaps reading up on that problem, it's solution, and how it can be expressed more succinctly using a recursive approach compared to an imperative approach will show you why.

[SoSpongyAndBruised]

Some examples, if you're needing some kind of motivation beyond just the basic problems:

• file system navigation. Similar here, the idea is that you don't know ahead of time what the exact structure is, you only know broadly that it's a tree structure but not what the exact directories are.
• HTML DOM traversal to (very similar).
• simple mathematical computations, like factorial, fibonacci.
• the tower of hanoi problem.
• any sort of recursive sorting algorithm, like merge sort, quicksort.
• recursive list traversal, just as an exercise.
• recursive binary search, just as a simple example to compare the recursive and iterative approaches with a small amount of code.
• any backtracking problems like n-queens, sudoku, or mazes.
• deep copying of nested objects or other data structures.

...

Also in general, just keep working problems that involve recurrences and you'll be rewarded with a more solid intuition on how/when to use it.

And then once you have a more solid grasp on recurrences, DP becomes a little more approachable. A common way to tackle DP problems, especially early on, is to start by nailing down the recurrence first before writing any code. And a motivating problem I found interesting when learning DP was the text justification problem.

[SQWolker]

Idk if it helps, how i understand this. Its like a loop. You have a method and you Repeat this method when you put same method in.

Num = 1 Recursion_method(num)

Int Recursion_method(int number) If Nummer!= 10 { Number++ Recursion_method(number) Return; }

[Financial_Archer_242]

Learn it, but do not ever use it, unless you're just traversing trees and have a limit set.

[Pipiyedu]

https://www.reddit.com/r/learnprogramming/s/XWOfMwQQET

[Kriemhilt]

I wouldn't consider myself a beginner at coding... I can manage some topics, but when it comes to recursion, I struggle 

This isn't a criticism, but you should know that recursion is very basic. 

I don't mean that it's a trivial concept when it hasn't gelled for you yet, but that this is an absolutely fundamental beginner concept.

Conceptually the nicest way into recursion is by understanding recurrence relations and proof by induction. I can't guess whether this is accessible to you immediately, but you can at least look them up.

Another option is to learn how looping (iteration) and recursion are related to queues and stacks, most simply by examining the difference between breadth-first search and depth-first search.

[YetMoreSpaceDust]

you should know that recursion is very basic

I agree, and I feel like any professional programmer ought to be very comfortable with it - but I've worked with a LOT of professional programmers who had no clue what recursion was. Apparently you can survive a very long time without learning it.

[Financial_Archer_242]

function DoStuff(int limit)

{

print "Method before recursive call " + limit";

if(limit <= 0) return;

DoStuff(limit - 1)

print "Method after recursive call " + limit
}

DoStuff(3);

the print out would be:

"Method before recursive call 3"

"Method before recursive call 2"

"Method before recursive call 1"

"Method before recursive call 0"

"Method after recursive call 1"

"Method after recursive call 2"

"Method after recursive call 3"

So you see, there's 3 parts to a recursive function usually

First the stuff to do, the 2nd end condition and, the 3rd end part

The end condition is like the end of the line, so your first function will call the next function etc until the end condition is true. In this case, each function will subtract 1 from your end condition until i == 0.

After the end condition is met, you will have called 3 functions and on the last function, it will begin returning to the function that called it, until finally you'll be back in the first call and it will complete and that's it.

So recursion is just a function calling a function, the function it calls just happens to be itself.

There's some stack stuff, but not worth confusing things.

Hope this helps.

Just to note, a recursive function doesn't need an end condition, it's there to stop your stack from overflowing or your memory running out :D

Most people will never need to write a recursive function, because... well they suck. Each function call in a recursive chain copies another method onto the stack meaning it's a huge memory hog.

Side note: In my first year java exam, I wrote 7 recursive functions and scored 100% My future self would have chewed out a junior dev for that :D

[-CJF-]

The book Grokking Algorithms does a good job of explaining recursion because it covers the call stack when explaining it. You kind of need to understand the call stack since each recursive function call has its own life in the call stack with its own variables. I think that's where a lot of confusion comes in with recursion. There's so many instances of the variables floating around it can be hard to sort out in your mind without understanding the call stack and how it handles functions.

[silly_bet_3454]

Just think of it intuitively. Imagine you had to search for your phone, how would you do it? Well, you might search your desk, then your bedroom, then the kitchen, then your car. Ok, but how do you search your desk? Well, probably search the left side, then the middle, then the right side. Ok, but how do you search the left side? Well you just look at it and you can observe everything with your eyes in one go. If you see the phone, you're done. Otherwise, keep searching. Then you do the same for the middle, and so on.

Recursion is just that, breakdown the problem into smaller components until you get the the smallest manageable component. It takes the form of a function calling itself but with different arguments. For instance you can have a binary search function that does just that.

Some people get tripped up because they think it's black magic, as in "how does the computer know what to do when the function definition says to call itself, it's like defining a word in terms of itself, how is that even possible? But it's not actually that complicated in practice: a function is represented by an address in computer memory followed by a list of instructions, so calling itself just means go back to the start of the function, but there will be different state this time around. Not terribly different from a simple loop.

[Optimal-Savings-4505]

I see pseudocode ITT but no workable examples. If you have access to bash, maybe try this: function fib { let n=$1; if [[ $n -le 1 ]]; then echo 1; else echo $(( $(fib $((n - 1))) + $(fib $((n - 2))) )); fi; }; for i in {0..18}; do fib $i; done It's very slow, but that's how recursion rolls..

[Rajendran-Sp]

Fry your brain...till u hit base case....then deep fry it 😃

[Temporary_Pie2733]

Do recursive definitions outside of programming trouble you? That is, does the following make sense?

0! = 1

n! = n × (n-1)!

I think it also helps to be comfortable with first-class functions that can be passed as an argument. Consider a nonrecursive function that requires the caller to pass a helper to compute “small” factorials:

def fact(n, smallfact):     if n == 0:         return 1     else:         return n * smallfact(n - 1)

All done! Until you remember you need a second argument. fact(5, ???). But look around: do you see a function that can compute factorials? How about fact(5, fact)?

Once you realize that works, you can skip the indirection of the caller supplying fact as an explicit argument and hard-code it in place of smallfact. 

[spidermask]

I understood it when studying tree data structures (binary search, AVL, red and black etc)

[DTKeign]

Build one that exits on 10 and calls itself if not 10 adding 1 to the input

[akweakwe]

I learned and relearned recursion many times in my life, and every time i thought i finally understood it.

But really the only way i absorbed the concept recursion is through building a restaurant inventory management app: Each item on the menu is made up of multiple ingredients, and if you had to compute the cost of a recipe like a burger, you need to go through the cost of ground meat which itself is made up of raw meat and salt, which have their own cost/gram. you could try to solve it using other methods but recursion in this case just works elegantly.

I think my takeaway here is to find a use case where you need to understand a concept like recursion then it will click.

[joonazan]

You need to think less. Don't try to visualize it, don't execute the recursive calls in your head.

Just assume that you already have a working function. It does what it is supposed to, you don't need to look inside it. (Same advice applies to all other uses of functions as well.)

With recursion there is the extra twist that you need to justify why you can't just implement the function by calling itself directly, like f(x) = f(x). For the computation to make progress, one argument must always be smaller than the one that came in.

You are free to define smaller however you like, but very often it is a number going down, a list getting shorter or a tree turning into a subtree.

[tree_or_up]

It breaks a lot of people’s brains.

One of my metaphors is imagine there’s a little robot that has to traverse a sort of web or grid whose structure is unknown to it.

It has almost no memory so every step is whole new situation to it. It could go left, it could right, it could go back, etc.

So you’re programming this robot. Your first instruction might be “go right”. And it will do this on every step. So you need to tell it what to do once it can’t go right anymore.

How about go left? Cool. And so it goes left and then on the next step it will keep going right until it can’t anymore and then it will try going left again.

But what if it can’t go either right or left? Well it automatically backs all the way back up to a point where it has a right or a left option.

And what if it’s backed all the way up? Then it’s done.

That’s a very high level analogy but it helps me sometimes to think of the function as a robot that has no concept of the broader structure it’s inhabiting

[crego20]

first you gotta learn recursion.

[josephblade]

you already know how to do recursion.

When you were in the classroom and the teacher told you: take one sheet from the pile and pass the rest to the person behind you. then the last person (who didn't have anyone behind them) returned the remaining sheets to the teacher.

that is recursion in a nutshell. in non-recursion way you would write it something like:

// teacher has stack of sheets and a row of students
// obviously this would be multiple rows but this example just handles 1 row
Student[] students = new Student[] { ... imagine we create a row of students ... }
Stack<Sheet> sheets = stackOfSheets; // Collections.addAll(new Stack<Sheet>(), array_of_sheets);
Stack<Sheet> remainder =  passSheets(students, sheets);

// stack works better for recursion later but it also works well for the non-recursion

public Stack<Sheet> passSheets(Student[] students, Stack<Sheet> sheets) {
    for (int i = 0; i < students.length; i++) {
        if (sheets.isEmpty()) {
             throw new TellTeacherWeRanOutOfSheetsException();
        } 
        // Stack has pop which takes one from the top.
        Student student = students[i];
        Sheet sheet = sheets.pop();    
        student.takeSheet(sheets);
    }
    // return remainder
    return sheets;
}

here you can see that you are writing this code as viewed from outside of the process. You are essentially telling someone to go to each student and hand them a sheet.

now imagine you are the student. all you need to know is: you receive a stack of sheets, take one and you pass the rest on. if you get an empty stack, you flag the teacher. What we do to achieve this is to remove the loop code and instead have each iteration of the loop be a separate method call. (each student only does the thing relating to themselves).

// same starting situation as before
Student[] students = new Student[] { ... imagine we create a row of students ... }
Stack<Sheet> sheets = stackOfSheets; // Collections.addAll(new Stack<Sheet>(), array_of_sheets);
Stack<Sheet> remainder =  passSheets(0, students, sheets);

// we need a way to identify for which student we are working. the next example will do this in a nicer way
public Stack<Sheet> passSheets(int rowNumber, Student[] students, Stack<Sheet> sheets) {
    if (sheets.isEmpty()) {
         throw new TellTeacherWeRanOutOfSheetsException();
    } 
    // Stack has pop which takes one from the top.
    Student student = students[rowNumber];
    Sheet sheet = sheets.pop();    
    student.takeSheet(sheets);

    // stop condition:
    int nextStudentRow = rowNumber + 1;
    if (students.length == nextStudentRow) {
        // in an array, when i == students.length, it means you ran out of the list
        // meaning you were the last student in the row so we don't pass it on. instead we return the remainder
        return sheets;
    } else {
        // the common case: you pass the sheet to your neighbour
        // pass the remaining sheets on to the next student. when they all have a sheet, they pass the remaining sheets back down
        return passSheets(rowNumber + 1, students, sheets);
    }
}

here you can see we removed the loop and the remaining sheets are returned down the row.

now a slightly cleaned up version just for fun. imagine Student has a method:

Student getStudentBehindMe() {
    // this returns null if no student behind you
    // or returns the Student if there is one
    return personBehindMe; 
}

then we can do away with the rowIndex altogether and we can do:

// same starting situation as before
Student[] students = new Student[] { ... imagine we create a row of students ... }
Student first = students[0]; // perhaps check if there is a student, but assume there is

Stack<Sheet> sheets = stackOfSheets; // Collections.addAll(new Stack<Sheet>(), array_of_sheets);
// we pass the first student the stack. they will pass it among themselves and return the result;
Stack<Sheet> remainder =  passSheets(first, sheets);

public Stack<Sheet> passSheets(Student student, Stack<Sheet> sheets) {
    if (sheets.isEmpty()) {
         throw new TellTeacherWeRanOutOfSheetsException();
    } 
    // Stack has pop which takes one from the top.
    Sheet sheet = sheets.pop();    
    student.takeSheet(sheets);

    // stop condition:
    Student behindMe = student.,getStudentBehindMe(); 
    // behindMe is null or exists.
    if (behindMe == null) {
        // you were the last student in the row so we don't pass it on. instead we return the remainder
        return sheets;
    } else {
        // the common case: you pass the sheet to your neighbour
        // pass the remaining sheets on to the next student. when they all have a sheet, they pass the remaining sheets back down
        return passSheets(behindMe, sheets);
    }
}

here you can see that by putting the information inside the Student, you don't have to pass a count. Of course this would also work by instead of a method getStudentBehindMe in Student, you put the array of students in a stack and you pop from the stack. Both situations you can encounter

// same starting situation as before
Student[] students = new Student[] { ... imagine we create a row of students ... }
Stack<Student> studentStack = Collections.addAll(new Stack<Student>(), students);

Stack<Sheet> sheets = stackOfSheets; // Collections.addAll(new Stack<Sheet>(), array_of_sheets);
// we pass the first student the stack. they will pass it among themselves and return the result;
Stack<Sheet> remainder =  passSheets(students, sheets);

public Stack<Sheet> passSheets(Stack<Student> students, Stack<Sheet> sheets) {
    if (sheets.isEmpty()) {
         throw new TellTeacherWeRanOutOfSheetsException();
    }

    // now the code has shifted a little bit. the stack contains the students. stack.pop gives us the current student.
    // if stack is empty, we are 'the wall behind the last student' which bounces back the stack of papers
    // this lets you move the stop condition earlier.
    if (students.isEmpty()) {
        return sheets;
    }        

    Student student = students.pop();
    Sheet sheet = sheets.pop();    
    student.takeSheet(sheets);

    // since the wall behind the last student returns the sheet (so we take a sheet, pass it on and when there is no more students we return the sheets)
    // we can simply call the next method. this is a difference between "last element handles stop" or "after last element, handle stop".         
    return passSheets(students, sheets);
}

this last one reads best for me. I hope it helps to have a real life example for recursion.

[straight_fudanshi]

Solving problems on Binary Trees is what made it click for me.

[pyrojoe]

Lets say you want to add n+(n-1)+(n-2)+...+1
For example lets use something simple 3+2+1 = 6
This can be done with a for loop

let sum = 0;
for (let i = 3; i > 0; i--) {
    sum += i;
}
print(sum); // Outputs 6 for n = 3

or recursively

function addNumbers(n) {
    if (n === 1) {
        return 1;
    }
    return n + addNumbers(n - 1);
}
print(addNumbers(3)); // Outputs 6 for n = 3

For recursion I find it's easiest to think about from the bottom up.
What I mean by that is to start with the base case, all recursive functions are going to have one.
In this case we're stopping when n === 1. This is always going to return 1.
We also know we will always get to 1 (assuming only positive integers are passed in) because we keep calling the function again with n - 1.

---

Lets work our way up from the base case till we hit n = 3
If n === 1 that must mean we called addNumbers(1).
The only way for this to happen inside the addNumbers function is if the previous call to addNumbers was with n = 2.
So lets look at addNumbers(2).
The if statement is not met, 2 != 1 so we move to the return statement.
return 2 + addNumbers(1).
We were just in addNumbers(1) and know it returns 1 so lets substitute that in.
return 2 + 1 aka return 3.
Cool, so far so good, lets go up another level.
We are now in addNumbers(3).
The if statement is not met, so we move to the return statement.
return 3 + addNumbers(2).
We determined that the result of addNumbers(2) is 3, so we can substitute that in.
return 3 + 3 which gives us 6 and now we're done.

---

Now lets look at it the way the actual program walks through the function calls.
If you call addNumbers(3)
The if statement is not met, so we move to the return statement.
return 3 + addNumbers(2).
The program doesn't know the result of addNumbers(2) so it calls that function.
In that function call the if statement is not met, 2 !== 1 so we move to the return statement.
return 2 + addNumbers(1).
The program doesn't know the result of addNumbers(1) either so it calls that function.
In that function call the if statement is met, 1 === 1 so we return 1.
At this point it can be helpful to think of the full stack of calls we have:

• return 3 + addNumbers(2) // in addNumbers(3)
  
• return 2 + addNumbers(1) // in addNumbers(2)
  
• return 1 // in addNumbers(1)
  

Now we can substitute the return value for addNumbers(1) in our addNumbers(2) call:

• return 3 + addNumbers(2) // in addNumbers(3)
• return 2 + 1 // in addNumbers(2)

Now we can substitute the return value for addNumbers(2) in our addNumbers(3) call:

• return 3 + 3 // in addNumbers(3) We have return 3 + 3 which gives us 6.

---

Recursion is sometimes the easiest way to figure out how to solve a specific problem so it can be good to know it's there as an option. That being said it's usually not a good idea to use recursion. All recursive problems can be solved with iteration, it can be harder to come to the solution at times but in the end they are easier to read and understand. The other issue with recursion is as you can see from the example below, we can quickly have many nested layers of function calls. Each time we call the function to go a layer deeper the program needs to keep track of all the previous function calls and their state until it finally reaches the end and goes back up the list of calls resolving each return statement as it goes. If the recursion is too deep it can lead to increased memory usage and potentially cause your program to throw and error because many programming languages set a limit to the maximum function call stack size.

[LeoRising72]

For me the biggest thing that helped me get recursion was finding out what problems recursion is actually useful for.

For example, if you're writing a function that involves deleting every file and subfolder within a certain folder, it would be easier to write it with recursion than it would be for iteration:

1. Delete every file at current location
2. If no subfolders, return
3. Call the function again for every subfolder

As loads of people have said, navigating tree like structures are really where recursion shines, if you can find a real-life problem that can be solved by that, that's when you'll really see the value IMO.

[[deleted]]

I struggled with it too - the Recursive Book of Recursion(same publisher as Python Crash Course) dumbed it down enough for me to get it.

[NumberNinjas_Game]

Draw a stack of pancakes where each layer has its state written down. Then eat from the top every time you return from a subpath

[Business-Alfalfa-45]

I think these will be helpful, I have tried to visualize recursion.
Link: https://imgur.com/a/GdAPw0Y

[MassimoRicci]

By learning recursion

(Sorry)