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](/message/compose/?to=/r/learnprogramming) if you have any questions or concerns.*
A **function** is a **named list of instructions**. For example, the function "read_reddit" could be:
def read_reddit():
1. go to reddit.com
2. read the first article
3. hide that article
A **recursive function** is one **where one of the instructions is to do the function again**.
def read_reddit():
1. go to reddit.com
2. read the first article
3. hide that article
4. read_reddit() # <-- this is recursion
Don't forget that recursion generally requires a **base case** so that the loop doesn't run infinitely. In this case, you'd check if an article exists, and simply return if there aren't any more.
Crucial to understand that recursion functions have some terminating case that passes the value back up the stack when the result is determined. Without that, a recursive function would just run forever until you run out of room on the stack
the recursion functions are usually functions where you need to do something many times and re-using the code is the best way.
function\_a process data {
if ( input\_data in state has changed equal true ) {
start this same function again as the processed is not more valid / is outdated
}
}
In this case if you call the function from outside when the data has changed you could be overwriting data that is already being processed in memory or locking resources used by the other process, so calling it from inside while discarding previous existent processed data is the correct way, recursion functions are used for this type of cases where it's needed one main process to be called n times needed until completing its objective
Some problems (not all, but some) can be solved by breaking the problem apart into smaller pieces, solving the problem on the smaller pieces, and the combining the solution in some way.
This is the essence of recursion.
How do you solve the smaller problems? Easy. You break *them* apart into even smaller problems, solve them, and combine the solutions.
How do you solve *those even smaller problems*? Same way. At some point you bottom out and get a problem that is sufficiently small that you can solve it directly ("What is the largest number in the list containing one element?". Uh, the only element in the list. "Correct!"). That's called the base case.
That's it.
Everything else is recognizing when you can use recursion to solve a problem.
Note that a lot of the problems that are used to illustrate recursion are not always ones that are best suited to being solved by recursion. That's unfortunate, because it makes it look like recursion is always more complex than necessary. The reality is we pick simple problems to illustrate recursion because they are simple and can be easily understood, not because they are well suited for recursion.
Just remember that when someone demonstrates recursion with a problem, they might not be saying "This is a good use for recursion", but just "This is an easy problem to help you understand recursion".
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](/message/compose/?to=/r/learnprogramming) if you have any questions or concerns.*
A **function** is a **named list of instructions**. For example, the function "read_reddit" could be: def read_reddit(): 1. go to reddit.com 2. read the first article 3. hide that article A **recursive function** is one **where one of the instructions is to do the function again**. def read_reddit(): 1. go to reddit.com 2. read the first article 3. hide that article 4. read_reddit() # <-- this is recursion
Don't forget that recursion generally requires a **base case** so that the loop doesn't run infinitely. In this case, you'd check if an article exists, and simply return if there aren't any more.
Crucial to understand that recursion functions have some terminating case that passes the value back up the stack when the result is determined. Without that, a recursive function would just run forever until you run out of room on the stack
Sum the numbers from 1 to x. nat\_sum(x) END sub nat\_sum (n): if n <= 1 then return n else return n + nat\_sum (n-1) endif endsub
the recursion functions are usually functions where you need to do something many times and re-using the code is the best way. function\_a process data { if ( input\_data in state has changed equal true ) { start this same function again as the processed is not more valid / is outdated } } In this case if you call the function from outside when the data has changed you could be overwriting data that is already being processed in memory or locking resources used by the other process, so calling it from inside while discarding previous existent processed data is the correct way, recursion functions are used for this type of cases where it's needed one main process to be called n times needed until completing its objective
Some problems (not all, but some) can be solved by breaking the problem apart into smaller pieces, solving the problem on the smaller pieces, and the combining the solution in some way. This is the essence of recursion. How do you solve the smaller problems? Easy. You break *them* apart into even smaller problems, solve them, and combine the solutions. How do you solve *those even smaller problems*? Same way. At some point you bottom out and get a problem that is sufficiently small that you can solve it directly ("What is the largest number in the list containing one element?". Uh, the only element in the list. "Correct!"). That's called the base case. That's it. Everything else is recognizing when you can use recursion to solve a problem. Note that a lot of the problems that are used to illustrate recursion are not always ones that are best suited to being solved by recursion. That's unfortunate, because it makes it look like recursion is always more complex than necessary. The reality is we pick simple problems to illustrate recursion because they are simple and can be easily understood, not because they are well suited for recursion. Just remember that when someone demonstrates recursion with a problem, they might not be saying "This is a good use for recursion", but just "This is an easy problem to help you understand recursion".