Recursion
Summer is almost upon us and flowers are blooming! Let’s use this time to dicuss recursion. Although it can seem complicated at first, recursion occurs when a function calls itself. When set up correctly, it is a pleasing way to set-up code and may have less key strokes than other methods.
To start, we cannot discuss recursion without discussing the call stack. The call stack is the stack of called functions. As I explained in “Using A Stack in JavaScript”, a stack is a pile of items with the item on top being processed first. For the call stack, the most recent function (function at the top of the stack) will be resolved first, then the next function on the stack, ect. A recursive function will be the same function piled on top of itself with some minor changes to the input. But if the function keeps calling itself, how do we keep it from infinitely calling itself or causing an error?
A condition is used to signal the recursive function to stop calling itself and to exit the function. This is one of the most important parts of this type of function. If this is not done you will max out your call-stack and will receive an error message.
Let’s say we want to use a recursive function to show a countdown in our console. To stay on topic, let’s do a count down to summer. The first day of summer is June 21st and today is April 26th — so let’s do a countdown of 56 days. For our purposes we’ll say n is 56, and use n as our input. Since we want to start at 56, we will first console.log this using console.log(n). Then let’s call our function again, but now we want our input to be 55 or (n — 1). If we run this function without a condition it’s going to loop forever and break our program. Let’s add a condition to the first line — if (n < 1) return 0, since we want our countdown to end at 0. Now when we run our function it will console.log every number from 56 through 0.
Let’s move onto a function a that is a bit more complicated. With a recursive function it is possible to call the same function twice with different inputs before any recursion starts. For this example let’s use the Fibonacci Sequence. The Fibonacci Sequence is a sequence of numbers where each number is the sum of the two numbers to its left. Below shows up to 34, but it is an endless sequence. It was used to develop the Golden Ratio, which is often found in nature.
Our goal will be to input the position of an integer, and have the value of the integer be returned. So if we enter 1, the output should be 1. If we enter 3, the output should be 2. For 6, the output will be 8. Let’s have our input equal y.
Our condition will need to kick in if n= 2 or n= 1, because in both cases the output will be 1. Therefore, we will set our condition as if (n < = 2) return 1. Then we will want to use one recursion function to determine the first number to the left of n, and a second recursive function to determine the second number to the left of n. By adding these altogether we get the n number in the placement. Below is the code, showcasing n= 9, which will result in 34.
Using creativity, recursion can be used to solve a variety of mathematical equations or data related problems.
Sources:
JavaScript Recursion. Programiz. https://www.programiz.com/javascript/recursion
How Recursion Works — Explained with Flowcharts and a Video. freeCodeCamp. https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/
