logo

Rekursiva funktioner

En rekursiv funktion kan definieras som en rutin som anropar sig själv direkt eller indirekt.

En rekursiv funktion är med andra ord en funktion som löser ett problem genom att lösa mindre instanser av samma problem. Denna teknik används ofta i programmering för att lösa problem som kan delas upp i enklare, liknande delproblem.



Behov av rekursiv funktion:

En rekursiv funktion är en funktion som löser ett problem genom att lösa mindre instanser av samma problem. Denna teknik används ofta i programmering för att lösa problem som kan delas upp i enklare, liknande delproblem.

1. Lösa komplexa uppgifter:

Rekursiva funktioner delar upp komplexa problem i mindre instanser av samma problem, vilket resulterar i kompakt och läsbar kod.



2. Dela och erövra:

Rekursiva funktioner är lämpliga för dela-och-erövra-algoritmer som att slå samman sortering och quicksort, dela upp problem i mindre delproblem, lösa dem rekursivt och slå samman lösningarna med det ursprungliga problemet.

3. Backtracking :

Rekursiv backtracking är idealisk för att utforska och lösa problem som N-Queens och Sudoku.

4. Dynamisk programmering:

Rekursiva funktioner löser effektivt dynamiska programmeringsproblem genom att lösa delproblem och kombinera deras lösningar till en komplett lösning.



bikupa arkitektur

5. Träd och grafstrukturer:

Rekursiva funktioner är utmärkta för att arbeta med träd- och grafstrukturer, förenkla traverserings- och mönsterigenkänningsuppgifter .

Hur man skriver en rekursiv funktion:

Komponenter i en rekursiv funktion:

Basfallet: Varje rekursiv funktion måste ha ett basfall. Basfallet är det enklaste scenariot som inte kräver ytterligare rekursion. Detta är ett uppsägningsvillkor som förhindrar att funktionen anropar sig själv på obestämd tid. Utan ett ordentligt basfall kan en rekursiv funktion leda till oändlig rekursion.

Rekursivt fall: I det rekursiva fallet anropar funktionen sig själv med de modifierade argumenten. Detta är kärnan i rekursion – att lösa ett större problem genom att dela upp det i mindre instanser av samma problem. Det rekursiva fallet bör flyttas närmare basfallet med varje iteration.

Låt oss överväga exemplet fakultet av numret :

I det här exemplet är basfallet när n är 0 , och funktionen returnerar 1 . Det rekursiva fallet multipliceras n med resultatet av den funktion som anropas med parameter n – 1 . Processen fortsätter tills basfallet uppnås.

Det är viktigt att säkerställa att den rekursiva funktionen har ett korrekt basfall och att de rekursiva anropen leder till basfallet, annars kan proceduren köras på obestämd tid, vilket leder till ett stackspill (överskrider det tillgängliga minnet som tilldelats för funktionsanrop).

Nedan är implementeringen av factorial av ett nummer:

C++
#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; }>
Java
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);  } }>
Pytonorm
# 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))>
C#
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));  } }>
Javascript
// 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();>

Produktion
Factorial of 4 is:24>

Tidskomplexitet: På)
Hjälputrymme: På)