Typescript 处理递归问题

递归 是一个基本的编程概念，指的是一个函数调用自己。它可以是解决问题的强大工具，但也可以是混乱和沮丧的来源，特别是对于初学者。在本教程中，我们将探讨如何在TypeScript中有效地使用递归，这是一种流行的JavaScript超集，增加了可选的静态类型和其他功能。

在使用递归时，需要记住的一件事是定义一个基数，这是一个阻止函数再次调用自己的条件。如果没有基数，函数将无限期地调用自己，导致无限循环。

解决TypeScript中的递归问题，需要了解如何在TypeScript程序中有效使用递归函数。这包括定义一个基本情况，以阻止函数无限期地调用自己，考虑递归函数的性能，并可能使用诸如记忆化和尾部调用优化等技术来提高函数的性能。它还涉及到理解TypeScript的特定语法和功能，如可选的静态类型和编译器标志，这些都可以在递归函数中使用。

在TypeScript中使用递归的步骤

• 为工作选择正确的工具 – 递归可以很强大，但可能有更好的解决方案来解决一个问题。考虑迭代（基于循环）的解决方案或其他方法是否更合适。

• 彻底测试你的代码 – 递归函数在调试方面具有挑战性，因此必须测试你的代码以确保其正常工作。

• 了解递归的局限性 – 递归函数由于为每个函数调用创建新的堆栈框架，对大的输入会消耗大量的内存。堆栈溢出错误可能由此产生。

• 少用递归–虽然递归可以是一个有用的工具，但必须少用它，只有在它是解决问题的最合适方案时才使用。

通过牢记这些事情，你可以有效地解决在TypeScript程序中使用递归的问题。

示例 1

下面是一个如何在TypeScript中解决递归的例子。为了解决这个例子中的递归问题，我们首先定义了基本情况，以阻止函数无限期地调用自己。在本例中，基本情况是当n为0或1时。然后我们定义n大于1时的递归情况，并指定函数应如何计算斐波那契数列中的第n个数字。Fibonacci 函数接受一个参数 n 并返回一个数字。当n为0或1时，该函数使用一个基数情况，分别返回0或1。在递归情况下，该函数返回斐波那契数列中第（n – 1）个和第（n – 2）个数字之和。

最后，我们用不同的输入值测试该函数，以确保其正常工作。通过这些步骤，我们可以有效解决这个TypeScript函数中递归的使用问题。

// function that calculates the nth number in the Fibonacci sequence
function fibonacci(n: number): number {
   // the base case: when n is 0 or 1, return n
   if (n === 0 || n === 1) {
      return n
   }
   // In the recursive case, calculate the nth number by adding the
   // (n - 1)th and (n - 2)th numbers in the sequence
   return fibonacci(n - 1) + fibonacci(n - 2)
}

// Examine the function using various input values
console.log('Fibonacci of 0th term: ', fibonacci(0)) // 0
console.log('Fibonacci of 1st term: ', fibonacci(1)) // 1
console.log('Fibonacci of 5th term: ', fibonacci(5)) // 5
console.log('Fibonacci of 10th term: ', fibonacci(10)) // 55

// function that calculates the nth number in the Fibonacci sequence
function fibonacci(n) {

   // the base case: when n is 0 or 1, return n
   if (n === 0 || n === 1) {
      return n;
   }

   // In the recursive case, calculate the nth number by adding the

   // (n - 1)th and (n - 2)th numbers in the sequence
   return fibonacci(n - 1) + fibonacci(n - 2);
}

// Examine the function using various input values
console.log('Fibonacci of 0th term: ', fibonacci(0)); // 0
console.log('Fibonacci of 1st term: ', fibonacci(1)); // 1
console.log('Fibonacci of 5th term: ', fibonacci(5)); // 5
console.log('Fibonacci of 10th term: ', fibonacci(10)); // 55

输出

上述代码将产生以下输出 —

Fibonacci of 0th term:  0
Fibonacci of 1st term:  1
Fibonacci of 5th term:  5
Fibonacci of 10th term:  55

示例 2

为了解决这个例子中的递归问题，我们首先要定义一个基本情况，以阻止函数无限期地调用自己。在本例中，基本情况是当数组为空时。然后我们描述当数组不为空时的递归情况，并指定函数应如何计算数组元素的和。sum 函数接受一个数组并返回一个数字。当数组为空时，该函数使用一个基本情况返回0。在递归情况下，该函数返回数组中的第一个元素加上其余元素的总和。

最后，我们用不同的输入值测试该函数，以确保其正常工作。通过这些步骤，我们可以有效解决这个TypeScript函数中递归的使用问题。

// function that calculates the sum of all numbers in an array
function sum(arr: number[]): number {

   // the base case: when the array is empty, return 0
   if (arr.length === 0) {
      return 0
   }

   // In the recursive case, return the first element in the array plus the sum

   // of the remaining elements
   return arr[0] + sum(arr.slice(1))
}

// Test the function with different input values
console.log('Sum of array [1, 2, 3, 4, 5]: ', sum([1, 2, 3, 4, 5])) // 15
console.log('Sum of array [-1, 2, -3, 4, -5]: ', sum([-1, 2, -3, 4, -5])) // -3
console.log('Sum of array []: ', sum([])) // 0

// function that calculates the sum of all numbers in an array
function sum(arr) {

   // the base case: when the array is empty, return 0
   if (arr.length === 0) {
      return 0;
   }

   // In the recursive case, return the first element in the array plus the sum

   // of the remaining elements
   return arr[0] + sum(arr.slice(1));
}

// Test the function with different input values
console.log('Sum of array [1, 2, 3, 4, 5]: ', sum([1, 2, 3, 4, 5])); // 15
console.log('Sum of array [-1, 2, -3, 4, -5]: ', sum([-1, 2, -3, 4, -5])); // -3
console.log('Sum of array []: ', sum([])); // 0

输出

上述代码将产生以下输出 —

Sum of array [1, 2, 3, 4, 5]:  15
Sum of array [-1, 2, -3, 4, -5]:  -3
Sum of array []:  0