En rekursiv funksjon kan defineres som en rutine som kaller seg selv direkte eller indirekte.

Med andre ord er en rekursiv funksjon en funksjon som løser et problem ved å løse mindre forekomster av samme problem. Denne teknikken brukes ofte i programmering for å løse problemer som kan brytes ned i enklere, lignende delproblemer.

Behov for rekursiv funksjon:

En rekursiv funksjon er en funksjon som løser et problem ved å løse mindre forekomster av samme problem. Denne teknikken brukes ofte i programmering for å løse problemer som kan brytes ned i enklere, lignende delproblemer.

1. Løse komplekse oppgaver:

Rekursive funksjoner deler komplekse problemer i mindre forekomster av det samme problemet, noe som resulterer i kompakt og lesbar kode.

2. Del og hersk:

Rekursive funksjoner er egnet for dele-og-hersk-algoritmer som flette sortering og quicksort, dele opp problemer i mindre delproblemer, løse dem rekursivt og slå sammen løsningene med det opprinnelige problemet.

3. Tilbakesporing :

Rekursiv tilbakesporing er ideell for å utforske og løse problemer som N-Queens og Sudoku.

4. Dynamisk programmering:

Rekursive funksjoner løser dynamiske programmeringsproblemer effektivt ved å løse delproblemer og kombinere deres løsninger til en komplett løsning.

5. Tre og grafstrukturer:

Rekursive funksjoner er flotte for å jobbe med tre- og grafstrukturer, forenkle traversering og mønstergjenkjenningsoppgaver .

Hvordan skrive en rekursiv funksjon:

Komponenter av en rekursiv funksjon:

Grunnboks: Hver rekursiv funksjon må ha et grunntilfelle. Grunnfallet er det enkleste scenariet som ikke krever ytterligere rekursjon. Dette er en oppsigelsesbetingelse som hindrer funksjonen i å kalle seg selv på ubestemt tid. Uten et skikkelig basiscase kan en rekursiv funksjon føre til uendelig rekursjon.

Rekursivt tilfelle: I det rekursive tilfellet kaller funksjonen seg selv med de modifiserte argumentene. Dette er essensen av rekursjon – å løse et større problem ved å dele det opp i mindre forekomster av det samme problemet. Det rekursive tilfellet bør bevege seg nærmere basistilfellet for hver iterasjon.

La oss vurdere eksemplet på faktorial av tall :

I dette eksemplet er grunntilfellet når n er 0 , og funksjonen returnerer 1 . Det rekursive tilfellet multipliserer n med resultatet av funksjonen kalt med parameter n – 1 . Prosessen fortsetter til grunntilfellet er nådd.

Det er viktig å sikre at den rekursive funksjonen har et riktig grunntilfelle og at de rekursive kallene fører til grunntilfellet, ellers kan prosedyren kjøre på ubestemt tid, noe som fører til stabeloverflyt (overskrider det tilgjengelige minnet som er tildelt for funksjonskall).

Nedenfor er implementeringen av faktorial av et tall:

#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>

Tidskompleksitet: På)
Hjelpeplass: På)