Swift - 递归

Swift中的递归

递归是一种技术，其中函数直接或间接地调用自身来解决问题。它不是一次性解决整个问题，而是将问题分解成更小的子问题，然后通过反复调用自身来解决这些子问题，直到达到基本条件。递归函数有两个主要组成部分：

基本条件 - 基本条件负责停止递归调用。或者说它是一个终止点，防止函数无限地调用自身。如果在递归函数中没有指定基本条件，那么它将无限地调用自身，程序将永远不会结束。
递归调用 - 递归调用是指函数使用修改后的参数调用自身来解决任务。通过迭代，递归调用应该朝着基本条件移动，以便它能够成功终止而不会进入无限递归。

语法

以下是递归函数的语法：

func functionName(){
   // body
   functionName()
}
functionName()

Swift中递归的工作原理

如果在一个函数内部调用自身，则称为递归函数。Swift支持函数递归。让我们通过一个例子来了解递归的工作原理。

示例

使用递归的Swift程序，用于查找给定数字的阶乘：

import Foundation

// Function to find the factorial of the specified number
func factorial(number: Int) -> Int {

   // Base condition
   if number == 0 || number == 1 {
      return 1
   } else {
    
      // Recursive call with modified parameters
      return number * factorial(number:number - 1)
   }
}
let num = 4
let output = factorial(number: num)
print("Factorial of \(num) is: \(output)")

输出

它将产生以下输出：

Factorial of 4 is: 24

在上面的代码中，我们有一个名为factorial()的递归函数。因此，该函数的工作原理如下：

1st function call with 4: factorial(4) = 4 * factorial(3)
2nd function call with 3: factorial(3) = 3 * factorial(2)
3rd function call with 2: factorial(2) = 2 *  factorial(1)
4th function call with 1: factorial(1) = 1(Here the value meets the base condition and the recursive call terminated)
Returned from 4th function call: 1 * 1 = 1
Returned from 3rd function call: 2 * 1 = 2
Returned from 2nd function call: 3 * 2 = 6
Returned from 1st function call: 4 * 6 = 24
Hence the factorial of 4 is 24.

示例

使用二分查找的Swift程序，用于查找指定元素的索引：

import Foundation

// Function to find a number from the given array using binary search
func binarySearchAlgorithm(_ arr: [Int], num: Int, leftNum: Int, rightNum: Int) -> Int? {
   if leftNum > rightNum {
      return nil
   }
    
   let midValue = leftNum + (rightNum - leftNum) / 2
    
   if arr[midValue] == num {
      return midValue
   } else if arr[midValue] < num {
      return binarySearchAlgorithm(arr, num: num, leftNum: midValue + 1, rightNum: rightNum)
   } else {
      return binarySearchAlgorithm(arr, num: num, leftNum: leftNum, rightNum: midValue - 1)
   }
}

let myArray = [11, 12, 13, 14, 15, 16, 17, 18, 19]
if let resIndex = binarySearchAlgorithm(myArray, num: 16, leftNum: 0, rightNum: myArray.count - 1) {
   print("Element found at index \(resIndex)") 
} else {
   print("Element Not found")
}

输出

它将产生以下输出：

Element found at index 5

Swift中递归的必要性

递归是一种非常容易地解决大型编程问题的强大技术。我们可以在以下场景中使用递归：

分治法 - 递归算法使用分治法，它们将复杂问题分解成小的相同子问题，并在每次递归调用中解决这些子问题。
树和图遍历 - 递归函数通常用于遍历数据结构中的树和图。
代码可读性 - 与迭代方法相比，递归结果更易于阅读和管理。
数学计算 - 使用递归，我们可以解决各种数学问题，例如阶乘、斐波那契数等。
自然表示 - 递归为具有递归属性的问题提供了自然和直观的表示。

递归的优点和缺点

以下是递归的优点：

递归函数易于调试，因为每次递归调用都专注于任务的一小部分，这允许更具针对性的测试和调试。
递归函数通常使用并行处理，从而提高其性能。
递归解决方案更易于阅读和维护。
递归函数灵活且允许抽象。

以下是递归的缺点：

处理更复杂的问题时，递归的执行流程难以跟踪。
它比迭代循环的开销更大。
如果我们没有提供正确的基本条件，它将导致无限递归。
递归并不适用于所有类型的问题，有些问题更适合用迭代方法解决。

打印页面