Introduction
In this chapter, we will learn recursive functions in TypeScript. A recursive function is a function that calls itself to solve a problem. Each recursive call should bring the problem closer to a base case, which is a condition that stops the recursion.
Recursive Function Syntax
Syntax
function functionName(parameters: type): returnType { if (baseCondition) { return baseValue; } else { return functionName(modifiedParameters); } } Example
This example demonstrates a simple recursive function that calculates the factorial of a number.
function factorial(n: number): number { if (n === 0) { return 1; } else { return n * factorial(n - 1); } } console.log(factorial(5)); // Output: 120 Output
120 Basic Recursive Function
The basic structure of a recursive function includes a base case to stop the recursion and a recursive call to the function itself with modified parameters.
Example
This example demonstrates a recursive function that calculates the sum of all numbers from 1 to n.
function sumTo(n: number): number { if (n === 1) { return 1; } else { return n + sumTo(n - 1); } } console.log(sumTo(5)); // Output: 15 Output
15 Recursive Function with Parameters
Recursive functions can accept parameters to help solve the problem at each step of the recursion.
Example
This example demonstrates a recursive function that calculates the greatest common divisor (GCD) of two numbers using the Euclidean algorithm.
function gcd(a: number, b: number): number { if (b === 0) { return a; } else { return gcd(b, a % b); } } console.log(gcd(48, 18)); // Output: 6 Output
6 Tail Recursion
Tail recursion is a special case of recursion where the recursive call is the last operation in the function. Tail-recursive functions can be optimized by the compiler to prevent stack overflow issues.
Example
This example demonstrates a tail-recursive function that calculates the factorial of a number.
function tailFactorial(n: number, acc: number = 1): number { if (n === 0) { return acc; } else { return tailFactorial(n - 1, n * acc); } } console.log(tailFactorial(5)); // Output: 120 Output
120 Common Use Cases
Recursive functions are commonly used for problems that involve hierarchical or nested structures, such as:
- Calculating factorials
- Calculating Fibonacci numbers
- Traversing tree or graph structures
- Solving puzzles like the Tower of Hanoi
- Implementing algorithms like quicksort and mergesort
Example
This example demonstrates a recursive function that calculates the nth Fibonacci number.
function fibonacci(n: number): number { if (n <= 1) { return n; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } console.log(fibonacci(6)); // Output: 8 Output
8 Complete Example with Output
In this section, we will combine the examples into a single TypeScript file, compile it to JavaScript, and run it to see the output.
TypeScript Code
You can test the following code in the TypeScript Playground.
// Factorial using recursion function factorial(n: number): number { if (n === 0) { return 1; } else { return n * factorial(n - 1); } } console.log(factorial(5)); // Output: 120 // Sum to n using recursion function sumTo(n: number): number { if (n === 1) { return 1; } else { return n + sumTo(n - 1); } } console.log(sumTo(5)); // Output: 15 // GCD using recursion function gcd(a: number, b: number): number { if (b === 0) { return a; } else { return gcd(b, a % b); } } console.log(gcd(48, 18)); // Output: 6 // Factorial using tail recursion function tailFactorial(n: number, acc: number = 1): number { if (n === 0) { return acc; } else { return tailFactorial(n - 1, n * acc); } } console.log(tailFactorial(5)); // Output: 120 // Fibonacci using recursion function fibonacci(n: number): number { if (n <= 1) { return n; } else { return fibonacci(n - 1) + fibonacci(n - 2); } } console.log(fibonacci(6)); // Output: 8 Conclusion
In this chapter, we covered recursive functions in TypeScript, including their syntax, basic structure, use of parameters, tail recursion, and common use cases. We provided a complete example with its output to illustrate how recursive functions work in TypeScript. Understanding recursive functions is essential for solving complex problems that can be naturally divided into similar sub-problems.