TypeScript Recursive Functions

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:

1. Calculating factorials
2. Calculating Fibonacci numbers
3. Traversing tree or graph structures
4. Solving puzzles like the Tower of Hanoi
5. 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.