Difference between revisions of "W2222 Recursion"
Tatsat-jha (talk | contribs) (add basic structure) |
Tatsat-jha (talk | contribs) (add basic intro and concept) |
||
| Line 6: | Line 6: | ||
* [https://www.youtube.com/watch?v=Mv9NEXX1VHc What on Earth is Recursion?] (YouTube - Computerphile) | * [https://www.youtube.com/watch?v=Mv9NEXX1VHc What on Earth is Recursion?] (YouTube - Computerphile) | ||
== Introduction == | == Introduction == | ||
'''Recursion''' is a very common topic within computer science and often one of the most confusing to understand. The Basic premise of recursion is having a function that executes over and over again until some base condition is met and the problem is solvable. Many forms of sorts, traversals, and searches rely on the usage of '''Recursive functions''' and it will be a concept you should be familiar with. | |||
=== Concept of Recursion === | === Concept of Recursion === | ||
The idea behind recursion is that a recursive function essentially breaks up a given problem into several smaller problems which can be more easily solved. Therefore a recursive function will call itself until the given problem is easy to solve and the several small solutions can be used together to solve the larger problem. | |||
Most recursive functions have essentially two sections. There's the '''base case''' and the '''recursive step.''' The recursive step is where the function will call itself again, but the base case is where a developer tells the program what is that small enough problem that can be solved immediately. In other words, the base case is where the function no longer needs to break down the problem. | |||
Let's look at this with a simple Recursive function. All we'll do is make a function called printReverse, this will print a String that counts down from a given number so the function call printReverse(5) will print "5, 4, 3, 2, 1" Note that this function can be implemented with iteration as well, recursion should generally not be seen as a counterpart to iteration as they function differently, but for the sake of demonstration we'll start here and later move onto more recursive specific examples. | |||
Notice the base case. | |||
=== Quiz === | |||
=== Usages === | === Usages === | ||
=== Quiz === | === Quiz === | ||
Revision as of 16:12, 3 February 2022
Background[edit]
- Recursion (Wikipedia)
- Factorial (Wikipedia) Read only until the section "Number Theory", exclusive
- Fibonacci Number (Wikipedia) Read only until the section "Mathematics", exclusive
- What on Earth is Recursion? (YouTube - Computerphile)
Introduction[edit]
Recursion is a very common topic within computer science and often one of the most confusing to understand. The Basic premise of recursion is having a function that executes over and over again until some base condition is met and the problem is solvable. Many forms of sorts, traversals, and searches rely on the usage of Recursive functions and it will be a concept you should be familiar with.
Concept of Recursion[edit]
The idea behind recursion is that a recursive function essentially breaks up a given problem into several smaller problems which can be more easily solved. Therefore a recursive function will call itself until the given problem is easy to solve and the several small solutions can be used together to solve the larger problem.
Most recursive functions have essentially two sections. There's the base case and the recursive step. The recursive step is where the function will call itself again, but the base case is where a developer tells the program what is that small enough problem that can be solved immediately. In other words, the base case is where the function no longer needs to break down the problem.
Let's look at this with a simple Recursive function. All we'll do is make a function called printReverse, this will print a String that counts down from a given number so the function call printReverse(5) will print "5, 4, 3, 2, 1" Note that this function can be implemented with iteration as well, recursion should generally not be seen as a counterpart to iteration as they function differently, but for the sake of demonstration we'll start here and later move onto more recursive specific examples.
Notice the base case.
Quiz[edit]
Usages[edit]
Quiz[edit]
Swift Implementations[edit]
Quiz[edit]
Key Concepts[edit]
Exercises[edit]
- M2222-10 Complete Merlin Mission Manager Mission M2222-10.
