Recursion: Difference between revisions
Mr. MacKenty (talk | contribs) |
Mr. MacKenty (talk | contribs) No edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
A simple definition: Recursion is the process of a subroutine calling itself. | A simple definition: Recursion is the process of a subroutine calling itself. | ||
== Example == | |||
= | <syntaxhighlight lang=python> | ||
def factorial(n): | |||
if n == 1: | |||
return 1 | |||
else: | |||
return n * factorial(n-1) | |||
</syntaxhighlight> | |||
== Identify a situation that requires the use of recursive thinking == | |||
Recursive thinking is a powerful tool that is useful in a variety of situations. Recursive thinking involves breaking a problem down into smaller and smaller subproblems until the subproblems are simple enough to solve directly. Here is an example of a situation that requires the use of recursive thinking: | |||
Computing factorials: | |||
Factorial is a mathematical operation that is denoted by the symbol "!". For a non-negative integer n, n! is defined as the product of all positive integers less than or equal to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120. | |||
To compute the factorial of a number n using recursive thinking, we can use the following algorithm: | |||
< | <syntaxhighlight lang="javascript"> | ||
== | function factorial(n) { | ||
if (n === 0 || n === 1) { | |||
return 1; | |||
} else { | |||
return n * factorial(n - 1); | |||
} | |||
} | |||
In | </syntaxhighlight> | ||
In this algorithm, we check if n is either 0 or 1. If it is, we return 1 since the factorial of 0 or 1 is 1. Otherwise, we compute n * factorial(n - 1) which calls the factorial function recursively with a smaller value of n. This process continues until n is reduced to 0 or 1, at which point the recursion stops and the final result is returned. | |||
Note that the recursive algorithm for computing factorials is elegant and concise. However, it may not be the most efficient way to compute factorials for very large values of n. In those cases, an iterative algorithm may be more appropriate. Nonetheless, the recursive algorithm demonstrates the power of recursive thinking and how it can be used to solve problems in a concise and elegant way. | |||
== Recursion == | |||
== | <html> | ||
<iframe width="560" height="315" src="https://www.youtube.com/embed/t4MSwiqfLaY" frameborder="0" allowfullscreen></iframe> | |||
</html> | |||
== Another look at recursion == | |||
== | <html> | ||
<iframe width="560" height="315" src="https://www.youtube.com/embed/VrrnjYgDBEk" frameborder="0" allowfullscreen></iframe> | |||
</html> | |||
== Standards == | == Standards == | ||
| Line 69: | Line 62: | ||
* [[Abstract data structures]] | * [[Abstract data structures]] | ||
== References == | == References == | ||
Latest revision as of 08:45, 9 May 2023
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem (as opposed to iteration). The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science [2]
A simple definition: Recursion is the process of a subroutine calling itself.
Example[edit]
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
Identify a situation that requires the use of recursive thinking[edit]
Recursive thinking is a powerful tool that is useful in a variety of situations. Recursive thinking involves breaking a problem down into smaller and smaller subproblems until the subproblems are simple enough to solve directly. Here is an example of a situation that requires the use of recursive thinking:
Computing factorials: Factorial is a mathematical operation that is denoted by the symbol "!". For a non-negative integer n, n! is defined as the product of all positive integers less than or equal to n. For example, 5! = 5 × 4 × 3 × 2 × 1 = 120.
To compute the factorial of a number n using recursive thinking, we can use the following algorithm:
function factorial(n) {
if (n === 0 || n === 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
In this algorithm, we check if n is either 0 or 1. If it is, we return 1 since the factorial of 0 or 1 is 1. Otherwise, we compute n * factorial(n - 1) which calls the factorial function recursively with a smaller value of n. This process continues until n is reduced to 0 or 1, at which point the recursion stops and the final result is returned.
Note that the recursive algorithm for computing factorials is elegant and concise. However, it may not be the most efficient way to compute factorials for very large values of n. In those cases, an iterative algorithm may be more appropriate. Nonetheless, the recursive algorithm demonstrates the power of recursive thinking and how it can be used to solve problems in a concise and elegant way.
Recursion[edit]
Another look at recursion[edit]
Standards[edit]
- Identify a situation that requires the use of recursive thinking.
- Identify recursive thinking in a specified problem solution.
- Trace a recursive algorithm to express a solution to a problem.