-
Notifications
You must be signed in to change notification settings - Fork 0
/
recursion.html
47 lines (39 loc) · 2.79 KB
/
recursion.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
<!DOCTYPE html>
<html lang="en">
<head>
<title>Recursion</title>
<meta name="viewport" content="width=device-width, height=device-height, initial-scale=1">
<link rel="stylesheet" href="style.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css">
<script src="index.js"></script>
<link rel="icon" type="image/x-icon" href="images/star.png">
</head>
<body onload="head(); dateTime(); foot();">
<header id="header" style="position:fixed;"></header>
<h1 class="title">Recursion</h1>
<div class="text">
<h3>What is Recursion?</h3>
<p>Recursion is when a method invokes itself. It is often used to solve complex problems by breaking it down into smaller problems of the same type until the simplest case is reached. Recursion works on the basis of a base case and a recursive case. The recursive case keeps calling the method but for a smaller, less complex task until the base case is reached. The base case makes no recursive calls. Once it is reached, the base case is then plugged into 2nd last method call. This allows another value to be calculated, which can be used to solve for the 3rd last method call. This process repeats until the original method call value is calculated.<br><br>Visualization:<br><img src="images/recursion.jpg" width="60%" height="auto"><br>This example is used to calculate 4!, which is 4x3x2x1. The algorithm begins by splitting 4! into 4x3!, then 3! into 3x2!, and so on, breaking up each factorial into smaller components. Eventually, 1! is reached, which is 1. This is then returned to calculate 2x1!=2, then that is returned, all the way up to 4!.</p>
<h3><br>Stack Overflow</h3>
<p>Recurison can be visualized with a stack diagram. Every time method calls itself it greates a new frame that contains a new version of method’s parameters and variables. The bottom of the stack is the base case.<br><br>Diagram: Here, n=0 is the base case.
<br><img src="images/stack.png" width="40%" height="auto"><br>
However, when the base case is never reached, the stack will go on infinitely. This is called stack overflow as the recursion never stops and the stack will run out of space, causing a stack overflow error.</p>
<h3><br>Example Recursion Code</h3>
<p>This is the Java implementation of the factorial visualization shown above.</p>
<div class="code">
<pre>
public int factorial(int n){
if (n == 1) return 1;
return n*factorial(n-1);
}
</pre>
</div>
<h2><br>Common Mistakes</h2>
<ol>
<li>Forgetting a base case</li>
<li>Incorrect implementation of recursive algorithm</li>
</ol>
</div>
<footer id="footer"></footer>
</body>
</html>