递归与迭代之间有什么区别？

2021年4月15日18:50:35 发表评论 998 次浏览

本文概述

当实体调用自身时, 该程序称为递归程序。有循环(或重复)时, 程序被称为迭代程序。

例子：

程序查找数字的阶乘

C++

//C++ program to find factorial of given number
#include<bits/stdc++.h>
using namespace std;
  
//----- Recursion -----
//method to find factorial of given number
int factorialUsingRecursion( int n)
{
     if (n == 0)
         return 1;
  
     //recursion call
     return n * factorialUsingRecursion(n - 1);
}
  
//----- Iteration -----
//Method to find the factorial of a given number
int factorialUsingIteration( int n)
{
     int res = 1, i;
  
     //using iteration
     for (i = 2; i <= n; i++)
         res *= i;
  
     return res;
}
  
//Driver method
int main()
{
     int num = 5;
     cout <<"Factorial of " <<num <<
             " using Recursion is: " <<
             factorialUsingRecursion(5) <<endl;
  
     cout <<"Factorial of " <<num <<
             " using Iteration is: " <<
             factorialUsingIteration(5);
  
     return 0;
}
  
//This code is contributed by mits

Java

//Java program to find factorial of given number
class GFG {
  
     //----- Recursion -----
     //method to find factorial of given number
     static int factorialUsingRecursion( int n)
     {
         if (n == 0 )
             return 1 ;
  
         //recursion call
         return n * factorialUsingRecursion(n - 1 );
     }
  
     //----- Iteration -----
     //Method to find the factorial of a given number
     static int factorialUsingIteration( int n)
     {
         int res = 1 , i;
  
         //using iteration
         for (i = 2 ; i <= n; i++)
             res *= i;
  
         return res;
     }
  
     //Driver method
     public static void main(String[] args)
     {
         int num = 5 ;
         System.out.println( "Factorial of " + num
                            + " using Recursion is: "
                            + factorialUsingRecursion( 5 ));
  
         System.out.println( "Factorial of " + num
                            + " using Iteration is: "
                            + factorialUsingIteration( 5 ));
     }
}

Python3

# Python3 program to find factorial of given number
  
# ----- Recursion -----
# method to find factorial of given number
def factorialUsingRecursion(n):
     if (n = = 0 ):
         return 1 ;
  
     # recursion call
     return n * factorialUsingRecursion(n - 1 );
  
# ----- Iteration -----
# Method to find the factorial of a given number
def factorialUsingIteration(n):
     res = 1 ;
  
     # using iteration
     for i in range ( 2 , n + 1 ):
         res * = i;
  
     return res;
  
# Driver method
num = 5 ;
print ( "Factorial of" , num, "using Recursion is:" , factorialUsingRecursion( 5 ));
  
print ( "Factorial of" , num, "using Iteration is:" , factorialUsingIteration( 5 ));
      
# This code is contributed by mits

C#

//C# program to find factorial of 
//given number
using System;
  
class GFG
{
  
     //----- Recursion -----
     //method to find factorial of 
     //given number
     static int factorialUsingRecursion( int n)
     {
         if (n == 0)
             return 1;
  
         //recursion call
         return n * factorialUsingRecursion(n - 1);
     }
  
     //----- Iteration -----
     //Method to find the factorial of
     //a given number
     static int factorialUsingIteration( int n)
     {
         int res = 1, i;
  
         //using iteration
         for (i = 2; i <= n; i++)
             res *= i;
  
         return res;
     }
  
     //Driver Code
     public static void Main(String[] args)
     {
         int num = 5;
         Console.WriteLine( "Factorial of " + num + 
                           " using Recursion is: " + 
                           factorialUsingRecursion(5));
  
         Console.WriteLine( "Factorial of " + num + 
                           " using Iteration is: " + 
                           factorialUsingIteration(5));
     }
}
  
//This code has been contributed by Rajput-Ji

PHP

<?php
//PHP program to find factorial of given number
  
     //----- Recursion -----
     //method to find factorial of given number
     function factorialUsingRecursion( $n )
     {
         if ( $n == 0)
             return 1;
  
         //recursion call
         return $n * factorialUsingRecursion( $n - 1);
     }
  
     //----- Iteration -----
     //Method to find the factorial of a given number
     function factorialUsingIteration( $n )
     {
         $res = 1;
  
         //using iteration
         for ( $i = 2; $i <= $n ; $i ++)
             $res *= $i ;
  
         return $res ;
     }
  
     //Driver method
         $num = 5;
         print ( "Factorial of " . $num . " using Recursion is: " .
                             factorialUsingRecursion(5). "\n" );
  
         print ( "Factorial of " . $num . " using Iteration is: " .
                             factorialUsingIteration(5). "\n" );
      
//This code is contributed by mits
?>

输出如下：

Factorial of 5 using Recursion is: 120
Factorial of 5 using Iteration is: 120

下面的详细示例说明了两者之间的区别：

  1. 时间复杂度：找到递归的时间复杂度比迭代要难。
    • 递归：递归的时间复杂度可以通过根据先前的调用找到第n个递归调用的值来找到。因此, 根据基本情况找到目标情况, 并根据基本情况进行求解, 可以使我们对递归方程的时间复杂度有所了解。请参阅解决重复更多细节。
    • 迭代：迭代的时间复杂度可以通过找到循环内重复的循环数来找到。
  2. 用法：这两种技术的使用都是时间复杂度和代码大小之间的折衷。如果时间复杂度是重点, 并且递归调用的数量很大, 则最好使用迭代。但是, 如果时间复杂度不是问题, 而代码很短, 那么递归将是解决之道。
    • 递归：递归涉及再次调用相同的函数, 因此, 其代码长度非常短。但是, 正如我们在分析中所看到的, 当存在大量的递归调用时, 递归的时间复杂度可能会成指数增长。因此, 递归的使用在较短的代码中是有利的, 但是在时间复杂度上较高。
    • 迭代：迭代是代码块的重复。这涉及较大的代码大小, 但是时间复杂度通常比递归要小。
  3. 高架：与迭代相比, 递归具有大量的开销。
    • 递归：递归具有重复调用函数的开销, 这是由于重复调用同一函数导致代码的时间复杂性增加。
    • 迭代：迭代不涉及任何此类开销。
  4. 无限重复：递归中的无限重复会导致CPU崩溃, 但在迭代中, 它将在内存耗尽时停止。
    • 递归：在递归中, 由于指定基本条件时会发生一些错误, 因此可能会发生无限递归调用, 这种错误永远不会变为假, 而是继续调用该函数, 这可能导致系统CPU崩溃。
    • 迭代：由于迭代器分配或增量错误或终止条件而导致的无限迭代将导致无限循环, 这可能会或可能不会导致系统错误, 但肯定会进一步停止程序执行。
属性 递归 迭代
定义 函数调用自身。 一组重复执行的指令。
应用 对于功能。 对于循环。
终止 通过基本情况, 将不会有任何函数调用。 当迭代器的终止条件不再满足时。
用法 当代码大小需要较小且时间复杂度不是问题时使用。 需要在时间复杂度和扩展代码大小之间取得平衡时使用。
代码大小 较小的代码大小 较大的代码大小。
时间复杂度 非常高(通常是指数级)的时间复杂度。 相对较低的时间复杂度(通常为多项式对数)。
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: