In this chapter, we will learn about JavaScript recursive functions. Recursive functions are functions that call themselves in order to solve a problem. We will cover:
- What are Recursive Functions?
- Syntax
- Base Case and Recursive Case
- Benefits and Drawbacks of Recursion
- Simple Programs using Recursive Functions
What are Recursive Functions?
A recursive function is a function that calls itself in order to solve smaller instances of the same problem. Recursion can be used for solving problems that have a natural recursive structure, such as tree traversal, factorial calculation, and more.
Syntax
The syntax for a recursive function is similar to a regular function, but it includes a call to the function itself within its body:
function functionName(parameters) { // base case to stop recursion if (condition) { return result; } // recursive case return functionName(modifiedParameters); } Base Case and Recursive Case
A recursive function must have two main components:
- Base Case: The condition under which the recursion stops. Without a base case, the function would call itself indefinitely, resulting in a stack overflow.
- Recursive Case: The part of the function where it calls itself with modified parameters to work towards the base case.
Example
function factorial(n) { // Base case: if n is 0, return 1 if (n === 0) { return 1; } // Recursive case: call factorial with n-1 return n * factorial(n - 1); } console.log(factorial(5)); // Output: 120 In the example above, the factorial function calculates the factorial of a number using recursion. The base case is when n is 0, and the recursive case calls factorial with n-1.
Benefits and Drawbacks of Recursion
Benefits
- Simplicity: Recursion can simplify the code for problems that have a natural recursive structure.
- Readability: Recursive solutions can be more readable and easier to understand.
Drawbacks
- Performance: Recursive functions can be less efficient than iterative solutions due to the overhead of repeated function calls.
- Memory Usage: Each recursive call consumes stack space, which can lead to a stack overflow for deep recursion.
Simple Programs using Recursive Functions
Program 1: Calculate the Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.
function fibonacci(n) { // Base cases: if n is 0 or 1, return n if (n === 0 || n === 1) { return n; } // Recursive case: sum of the two preceding numbers return fibonacci(n - 1) + fibonacci(n - 2); } console.log(fibonacci(6)); // Output: 8 Program 2: Sum of an Array of Numbers
function sumArray(arr) { // Base case: if the array is empty, return 0 if (arr.length === 0) { return 0; } // Recursive case: sum of the first element and the sum of the rest of the array return arr[0] + sumArray(arr.slice(1)); } let numbers = [1, 2, 3, 4, 5]; console.log("Sum:", sumArray(numbers)); // Output: Sum: 15 Program 3: Find the Greatest Common Divisor (GCD)
function gcd(a, b) { // Base case: if b is 0, return a if (b === 0) { return a; } // Recursive case: GCD of b and the remainder of a divided by b return gcd(b, a % b); } console.log("GCD of 48 and 18:", gcd(48, 18)); // Output: GCD of 48 and 18: 6 Program 4: Reverse a String
function reverseString(str) { // Base case: if the string is empty, return an empty string if (str === "") { return ""; } // Recursive case: last character + reverse of the rest of the string return str.charAt(str.length - 1) + reverseString(str.slice(0, -1)); } console.log("Reversed string:", reverseString("hello")); // Output: Reversed string: olleh Program 5: Check if a Number is a Power of Two
function isPowerOfTwo(n) { // Base case: if n is 1, return true if (n === 1) { return true; } // Base case: if n is less than 1 or not divisible by 2, return false if (n < 1 || n % 2 !== 0) { return false; } // Recursive case: check if n / 2 is a power of two return isPowerOfTwo(n / 2); } console.log("Is 16 a power of two?", isPowerOfTwo(16)); // Output: Is 16 a power of two? true console.log("Is 18 a power of two?", isPowerOfTwo(18)); // Output: Is 18 a power of two? false Conclusion
In this chapter, you learned about JavaScript recursive functions, including their syntax, the importance of base and recursive cases, and their benefits and drawbacks. We also provided various use cases with simple programs to demonstrate the usage of recursive functions. Recursion can be used for solving problems with a natural recursive structure, but it should be used judiciously to avoid performance and memory issues.