I am a 4th semester CS student from Germany and still don't grasp recursion, even though I already took the data structures & algorithms courses.
If you did have something like a magic moment where it made sense to you, please enlighten me as I would really like to truly gain an intuition (and implement a parallelized msd-radixsort for learning-purposes because I failed to do this assignment yesterday).
I had problems with recursion too, I think because the mind at first tries to follow in an abstract way and gets lost. You need to switch to concrete thinking, so you need specific things that you can rely on, these 3 things are solid, and you can rely on them if you get lost in recursion :
1) There is always an exit condition ( or it would run forever , we never want that)
2) There is always a value that changes and it is passed to the next execution, or otherwise it wouldn't make sense it would be always the same execution and the exit condition would never trigger.
3) Think like frames of a movie, in paper o whiteboard, write a table with a column for every variable and a row for every step, my first programming teacher taught me this, and 19 years later it save me in a white board interview, it helps to calm down and just go step by step seeing how values evolve.
So these 3 together, allow you to think in how the values change in every step, and how to get to the point that the exit condition is meet.
Just my two cents, I really grasped it when I read through Structure and Interpretation of Computer Programs and followed the online course from MIT. It's meant to be a first year course but it's done in Scheme (a kind of lisp) and it's very enlightening to see such a different way to program.
It forces you to learn recursion since for most of the book it only uses pure functional programming with no mutation, so the only way to do loops is with recursion. Overall I would say it gave me a strong base to understand not just recursion but functional programming which has helped me pick up new languages more easily during my career.
Also I used Clojure instead of scheme to do the exercises. It's a wonderful modern lisp that works on JVM and can land you a job. The examples usually work with minor modifications and I would say it's worth it to learn.
I'll pitch in with my own intuition; the easiest way to understand it is to view it as a call stack. Using this example function:
function RecFunc(n, max) {
let result; // intialize the return variable
if (n < max) {
result = RecFunc(n + 1, max) // the recursion
} else {
result = n; // the exit condition
}
return result;
}
RecFunc(0, 3);
When you call the function, we descend down the stack until it hits the exit condition. Notice that `result` is undefined in the upper levels of the stack; when `n` is equal to `max`, the function is finally able to assign a value to `result` and exit:
| RecFunc
v n: 0, max: 3, result: undefined
| RecFunc
v n: 1, max: 3, result: undefined
| RecFunc
v n: 2, max: 3, result: undefined
| RecFunc
v n: 3, max: 3, result: 3
Now that the exit condition has been met, we go back up the stack, returning the result at each step:
I remember what made me click was using a bit of assembly.
If you imagine your code as a sequence of instructions, recursion is basically a `JMP` to the start of the stack again, normally with different values.
Once a condition is met, instead of jumping back to the start, it returns something. That condition then repeats itself inside all the repetitions eventually returning the value to the original caller.
# imagine we're recursing to subtract to zero
1. call function subtract with 10 (set x = 10)
2. subtract x by 1
3. if zero, return 0
4. else return the result of calling the function with x-1 (jump to 2)
Once I realized deep down at the CPU level it's all a sequence of instructions, recursion is nothing but moving the pointer. With higher level languages there's a bit more involved, but the gist is the same.
The best way I've found is to imagine a physical tree, and perhaps go outside and stand in front of a big one...
Notice there are 2 types of parts:
- A leaf, which is the end (has no children)
- A branch, which may have leaves or more branches (has children)... and because a branch can have more branches, this is recursion, so we abstract to a 3rd type of part:
- A node, which could be a branch or a leaf...
Imagine if you were blind and had to feel your hand up the stem, and when you reach a node, you'd move your hand up the node to check 'is this a leaf, or a branch'
If it's a leaf, you mark it; but if it's a branch, you move your hand along the branch and do the same check for the next nodes 'is this a leaf, or a branch'...
function int getNumLeaves(Node node):
foreach childNode in node:
if childNode.IsLeaf(): leafCount++
else: return getNumLeaves(childNode) // NOT a leaf -> check this branch's children
print getNumLeaves(tree.stem); // (start with the outermost 'node')
The pseudocode above could have errors, but it's simple enough to get started for understanding;)
Have you seen the movie 'Inception' [0] ? This is the idea behind recursion: you are in some context, then dive into another (similar although not identical) context, then dive into another (similar although not identical) context, etc.
The 'reality' is the top level context.
You dive down to level 2 context by falling asleep; that would be the recursive function call.
In that dream, fall asleep and enter level 3 context. You are now recusrsively falling asleep.
In the movie, the characters wait for a signal to wake up and going one level up. This is the 'stopping condition' of a recursive call.
You can also see that as Matryoshka dolls.
Regarding the 'Inception' movie that's funny, because it popularized the '-ception' suffix to describe a recursive phenomenon [1]
Sometimes the best way to grasp an abstract concept is to translate it to a real life example (usually a stupid example).
So I'll try to explain recursion to you with an <stupid> example, let's say that you want to take a shower, but you have your pijamas and your underwear on. What you must do is take all your clothes, one by one, and then get into the shower and take the bath.
You first take off your pijama shirt (you have 2 pieces left), you then remove your pijama pants (1 piece left) and finally you remove your underwear. Notice that this is a repetitive pattern that must be repeated a couple of times in this case (in other case, you might have more clothe pieces, so you will do this process more). Finally when you're naked, you ask yourself: do I need to remove another piece? NO!, you reply, and you proceed to go and take the bath.
In recursion, you have 3 main components:
-A function that performs the same action a repeated number of times, except for when you meet a base case (end of the recursion)
-A value that must be tracked and modified in order to perform the said action n times, and know when to stop doing it
-A base case that stops the repeating action, and usually performs another 1 time action.
In our example, our components are:
- Function <undress to take a shower> that performs the repeated action of taking a piece of cloth off.
- Value tracked, which is the <number of pieces of cloth you have left to get naked>, and on each iteration or call of the function will be reduced by 1 (asuming you're taking 1 piece at a time).
- Base case, which would be <when you have no pieces of cloth left to remove = you're naked> and you can perform the last 1 time executed action which is <take the bath>.}
Notice the importance of the base case, otherwise your program will keep iterating and the program will get stucked.
I think they easiest way to grasp it is by writing simple examples, eg write a function that prints the last item in a list and returns the rest and then call it recursively to print the whole list. You can do it in about 5 lines in python or js and thinking it through often helps to grok stuff. I just did that myself and on the 5th attempt it worked(!).
I had two A-level maths teachers at school. One always started by getting the class to do a simple as possible example like the above before launching into more complicated stuff, the other started off explaining complex stuff. The first approach worked far better, with the second our minds just kind of glazed over.
There's something a little counter intuitive about it like your neurones have to wire up on the simple example before getting the more complex. Doing the simple stuff then sleeping on it and doing the complex the next day works better still I think.
My first time doing recursion was implementing an indentation level calculation for showing threaded/nested child comments in a mailing list display UI, one of my first web apps. The mysql table I had populated had an id and a parent and I just repeatedly queried the db for any objects that had the current item as parent, depth-first.
I didn’t realize that it was a threshold moment, and I didn’t even know if it was syntactically legal or allowed for a function to call itself (I had no formal CS training) but I remember struggling with the “how much should these child elements be indented” problem and eventually trying it and it worked; it was quite a rush for 14-year-old me.
Maybe try implementing something simple and straightforward that uses it, like a web front end that displays a directed graph of nested comments/message replies?
Recursion works when you can break solving a big problem down to solving a smaller version of the same problem. So, like, if you want to balance a heap, you can start at the root node, and call "balance" on the left heap and right heap.
So, each step needs to get you closer to the goal, working on a smaller problem, until you reach a base case, a really small problem that you don't solve in terms of recursion. You check for the base case, a really small problem you actually solve directly instead of handing it off to another recursive call, and you actually return your solution to the caller.
Recursion is simple: It is just a function calling itself. The difficult part is that it is not getting out of control (e.g. never stops).
To make sure your function will stop calling itself you need an exit-condition. So whenever you want to write a recursive function, simply start with a template like this:
function myFunc(list) {
// exit condition
if (list.length == 0) {
// What should the function do if the exit condition is true
return
} else {
// before recursion
console.log(list[0])
// recursion
myFunc(list.slice(1))
// after recursion
}
}
So basically you have to think about when your function aborts the recursion, what it does before the recursion (e.g. extract an element from a list), how the recursive call is different from the original call (e.g. the list got reduced by one element) and after what it does after the recursive call (e.g. push a modified element to a stack). By answering those questions you should be able to solve a whole bunch of recursive problems.
Before I learned this pattern, my recursive functions were a mess. Now, they all adhere to that very template and I find it actually fun to write recursive functions as there are some problems which are a lot easier to solve with them.
Comments
I am a 4th semester CS student from Germany and still don't grasp recursion, even though I already took the data structures & algorithms courses. If you did have something like a magic moment where it made sense to you, please enlighten me as I would really like to truly gain an intuition (and implement a parallelized msd-radixsort for learning-purposes because I failed to do this assignment yesterday).
I had problems with recursion too, I think because the mind at first tries to follow in an abstract way and gets lost. You need to switch to concrete thinking, so you need specific things that you can rely on, these 3 things are solid, and you can rely on them if you get lost in recursion :
1) There is always an exit condition ( or it would run forever , we never want that)
2) There is always a value that changes and it is passed to the next execution, or otherwise it wouldn't make sense it would be always the same execution and the exit condition would never trigger.
3) Think like frames of a movie, in paper o whiteboard, write a table with a column for every variable and a row for every step, my first programming teacher taught me this, and 19 years later it save me in a white board interview, it helps to calm down and just go step by step seeing how values evolve.
So these 3 together, allow you to think in how the values change in every step, and how to get to the point that the exit condition is meet.
Hope it helps! good luck!
Just my two cents, I really grasped it when I read through Structure and Interpretation of Computer Programs and followed the online course from MIT. It's meant to be a first year course but it's done in Scheme (a kind of lisp) and it's very enlightening to see such a different way to program.
It forces you to learn recursion since for most of the book it only uses pure functional programming with no mutation, so the only way to do loops is with recursion. Overall I would say it gave me a strong base to understand not just recursion but functional programming which has helped me pick up new languages more easily during my career.
Also I used Clojure instead of scheme to do the exercises. It's a wonderful modern lisp that works on JVM and can land you a job. The examples usually work with minor modifications and I would say it's worth it to learn.
I'll pitch in with my own intuition; the easiest way to understand it is to view it as a call stack. Using this example function:
When you call the function, we descend down the stack until it hits the exit condition. Notice that `result` is undefined in the upper levels of the stack; when `n` is equal to `max`, the function is finally able to assign a value to `result` and exit: Now that the exit condition has been met, we go back up the stack, returning the result at each step: Notice how the call stack resembles stepping through a for-loop: If you really want to see a mind-blowing example of recursion, step through an implementation of the `compose`[0] function some time. :)[0] https://github.com/reduxjs/redux/blob/master/src/compose.js
I remember what made me click was using a bit of assembly.
If you imagine your code as a sequence of instructions, recursion is basically a `JMP` to the start of the stack again, normally with different values.
Once a condition is met, instead of jumping back to the start, it returns something. That condition then repeats itself inside all the repetitions eventually returning the value to the original caller.
Once I realized deep down at the CPU level it's all a sequence of instructions, recursion is nothing but moving the pointer. With higher level languages there's a bit more involved, but the gist is the same.The best way I've found is to imagine a physical tree, and perhaps go outside and stand in front of a big one...
Notice there are 2 types of parts:
Imagine if you were blind and had to feel your hand up the stem, and when you reach a node, you'd move your hand up the node to check 'is this a leaf, or a branch' If it's a leaf, you mark it; but if it's a branch, you move your hand along the branch and do the same check for the next nodes 'is this a leaf, or a branch'... The pseudocode above could have errors, but it's simple enough to get started for understanding;)Have you seen the movie 'Inception' [0] ? This is the idea behind recursion: you are in some context, then dive into another (similar although not identical) context, then dive into another (similar although not identical) context, etc.
The 'reality' is the top level context.
You dive down to level 2 context by falling asleep; that would be the recursive function call.
In that dream, fall asleep and enter level 3 context. You are now recusrsively falling asleep.
In the movie, the characters wait for a signal to wake up and going one level up. This is the 'stopping condition' of a recursive call.
You can also see that as Matryoshka dolls.
Regarding the 'Inception' movie that's funny, because it popularized the '-ception' suffix to describe a recursive phenomenon [1]
[0] https://www.imdb.com/title/tt1375666/ [1] https://en.wikipedia.org/wiki/Inception#In_popular_culture
Sometimes the best way to grasp an abstract concept is to translate it to a real life example (usually a stupid example). So I'll try to explain recursion to you with an <stupid> example, let's say that you want to take a shower, but you have your pijamas and your underwear on. What you must do is take all your clothes, one by one, and then get into the shower and take the bath. You first take off your pijama shirt (you have 2 pieces left), you then remove your pijama pants (1 piece left) and finally you remove your underwear. Notice that this is a repetitive pattern that must be repeated a couple of times in this case (in other case, you might have more clothe pieces, so you will do this process more). Finally when you're naked, you ask yourself: do I need to remove another piece? NO!, you reply, and you proceed to go and take the bath.
In recursion, you have 3 main components: -A function that performs the same action a repeated number of times, except for when you meet a base case (end of the recursion) -A value that must be tracked and modified in order to perform the said action n times, and know when to stop doing it -A base case that stops the repeating action, and usually performs another 1 time action.
In our example, our components are: - Function <undress to take a shower> that performs the repeated action of taking a piece of cloth off. - Value tracked, which is the <number of pieces of cloth you have left to get naked>, and on each iteration or call of the function will be reduced by 1 (asuming you're taking 1 piece at a time). - Base case, which would be <when you have no pieces of cloth left to remove = you're naked> and you can perform the last 1 time executed action which is <take the bath>.}
Notice the importance of the base case, otherwise your program will keep iterating and the program will get stucked.
Hope that this helps.
I think they easiest way to grasp it is by writing simple examples, eg write a function that prints the last item in a list and returns the rest and then call it recursively to print the whole list. You can do it in about 5 lines in python or js and thinking it through often helps to grok stuff. I just did that myself and on the 5th attempt it worked(!).
I had two A-level maths teachers at school. One always started by getting the class to do a simple as possible example like the above before launching into more complicated stuff, the other started off explaining complex stuff. The first approach worked far better, with the second our minds just kind of glazed over.
There's something a little counter intuitive about it like your neurones have to wire up on the simple example before getting the more complex. Doing the simple stuff then sleeping on it and doing the complex the next day works better still I think.
My first time doing recursion was implementing an indentation level calculation for showing threaded/nested child comments in a mailing list display UI, one of my first web apps. The mysql table I had populated had an id and a parent and I just repeatedly queried the db for any objects that had the current item as parent, depth-first.
I didn’t realize that it was a threshold moment, and I didn’t even know if it was syntactically legal or allowed for a function to call itself (I had no formal CS training) but I remember struggling with the “how much should these child elements be indented” problem and eventually trying it and it worked; it was quite a rush for 14-year-old me.
Maybe try implementing something simple and straightforward that uses it, like a web front end that displays a directed graph of nested comments/message replies?
Recursion works when you can break solving a big problem down to solving a smaller version of the same problem. So, like, if you want to balance a heap, you can start at the root node, and call "balance" on the left heap and right heap.
So, each step needs to get you closer to the goal, working on a smaller problem, until you reach a base case, a really small problem that you don't solve in terms of recursion. You check for the base case, a really small problem you actually solve directly instead of handing it off to another recursive call, and you actually return your solution to the caller.
Recursion is simple: It is just a function calling itself. The difficult part is that it is not getting out of control (e.g. never stops).
To make sure your function will stop calling itself you need an exit-condition. So whenever you want to write a recursive function, simply start with a template like this:
So basically you have to think about when your function aborts the recursion, what it does before the recursion (e.g. extract an element from a list), how the recursive call is different from the original call (e.g. the list got reduced by one element) and after what it does after the recursive call (e.g. push a modified element to a stack). By answering those questions you should be able to solve a whole bunch of recursive problems.Before I learned this pattern, my recursive functions were a mess. Now, they all adhere to that very template and I find it actually fun to write recursive functions as there are some problems which are a lot easier to solve with them.
I suggest studying "A Regular Expression Matcher" by Rob Pike:
https://www.cs.princeton.edu/courses/archive/spr09/cos333/be...
You just always start with the base case. It could be recursion is just so simple that your mistake is thinking there must be something complicated.
Also, if the algorithm is not tail recursive, you may be missing that there is an implicit call stack where intermediary results are pushed to.
Try the "Recurrence Relation" chapter of https://larc.unt.edu/ian/books/free/poa.pdf
Read "The Little Schemer"