Rekurzivní funkci lze definovat jako rutinu, která se přímo nebo nepřímo volá.

Jinými slovy, rekurzivní funkce je funkce, která řeší problém řešením menších instancí stejného problému. Tato technika se běžně používá v programování k řešení problémů, které lze rozdělit na jednodušší, podobné dílčí problémy.

Potřeba rekurzivní funkce:

Rekurzivní funkce je funkce, která řeší problém řešením menších instancí stejného problému. Tato technika se často používá v programování k řešení problémů, které lze rozdělit na jednodušší, podobné dílčí problémy.

1. Řešení složitých úkolů:

Rekurzivní funkce rozdělují složité problémy na menší instance stejného problému, což vede ke kompaktnímu a čitelnému kódu.

2. Rozděl a panuj:

Rekurzivní funkce jsou vhodné pro algoritmy rozděl a panuj, jako je slučovací třídění a rychlé třídění, rozdělení problémů na menší dílčí problémy, jejich rekurzivní řešení a sloučení řešení s původním problémem.

3. Zpětné sledování :

Rekurzivní backtracking je ideální pro zkoumání a řešení problémů, jako jsou N-Queens a Sudoku.

4. Dynamický programování:

Rekurzivní funkce efektivně řeší problémy dynamického programování řešením dílčích problémů a kombinováním jejich řešení do kompletního řešení.

5. Strom a grafové struktury:

Rekurzivní funkce jsou skvělé pro práci se stromovými a grafovými strukturami, zjednodušují úlohy procházení a rozpoznávání vzorů .

Jak napsat rekurzivní funkci:

Komponenty rekurzivní funkce:

Základní případ: Každá rekurzivní funkce musí mít základní případ. Základní případ je nejjednodušší scénář, který nevyžaduje další rekurzi. Toto je podmínka ukončení, která brání funkci, aby se sama volal po neomezenou dobu. Bez správného základního případu může rekurzivní funkce vést k nekonečné rekurzi.

Rekurzivní případ: V rekurzivním případě funkce volá sama sebe s upravenými argumenty. To je podstata rekurze – řešení většího problému jeho rozdělením na menší instance stejného problému. Rekurzivní případ by se měl při každé iteraci přibližovat k základnímu případu.

Podívejme se na příklad faktoriál čísla :

V tomto příkladu je základní případ kdy n je 0 a funkce se vrátí 1 . Rekurzivní případ se násobí n s výsledkem funkce volané s parametrem n – 1 . Proces pokračuje, dokud není dosaženo základního případu.

Je nezbytné zajistit, aby rekurzivní funkce měla správný základní případ a aby rekurzivní volání vedla k základnímu případu, jinak by procedura mohla běžet donekonečna, což by vedlo k přetečení zásobníku (překročení dostupné paměti přidělené pro volání funkcí).

Níže je implementace faktoriálu čísla:

java polymorfismus

#include  using namespace std; // Recursive Function to calculate Factorial of a number int factorial(int n) {  // Base case  if (n == 0) {  return 1;  }  // Recursive case  return n * factorial(n - 1); } // Driver Code int main() {  int n = 4;  cout << 'Factorial of ' << n  << ' is:' << factorial(n);  return 0; }>

import java.util.Scanner; public class Factorial {  // Recursive Function to calculate the factorial of a number  static int factorial(int n) {  // Base case: If n is 0, the factorial is 1.  if (n == 0) {  return 1;  }  // Recursive case: Calculate the factorial by multiplying n with the factorial of (n - 1).  return n * factorial(n - 1);  }  public static void main(String[] args) {  int n = 4;  // Calculate and print the factorial of n.  int result = factorial(n);  System.out.println('Factorial of ' + n + ' is: ' + result);  } }>

# Recursive Function to calculate Factorial of a number def factorial(n): # Base case if n == 0: return 1 # Recursive case return n * factorial(n - 1) # Driver Code if __name__ == '__main__': n = 4 print('Factorial of', n, 'is:', factorial(n))>

using System; class Program {  // Recursive Function to calculate Factorial of a number  static int Factorial(int n)  {  // Base case  if (n == 0)  {  return 1;  }  // Recursive case  return n * Factorial(n - 1);  }  // Driver Code  static void Main()  {  int n = 4;  Console.WriteLine('Factorial of ' + n + ' is: ' + Factorial(n));  } }>

// Function to calculate the factorial of a number using recursion function factorial(n) {  // Base case: If n is 0, the factorial is 1.  if (n === 0) {  return 1;  }  // Recursive case: Calculate the factorial by multiplying n with the factorial of (n - 1).  return n * factorial(n - 1); } // Main function function main() {  // Given number  let n = 4;  // Calculate the factorial of n.  let result = factorial(n);  // Print the result  console.log('Factorial of ' + n + ' is: ' + result); } // Call the main function main();>

Factorial of 4 is:24>

Časová náročnost: Na)
Pomocný prostor: Na)