Una funció recursiva es pot definir com una rutina que s'anomena directament o indirectament.

En altres paraules, una funció recursiva és una funció que resol un problema resolent instàncies més petites del mateix problema. Aquesta tècnica s'utilitza habitualment en programació per resoldre problemes que es poden desglossar en subproblemes més simples i similars.

cadena en java

Necessitat de la funció recursiva:

Una funció recursiva és una funció que resol un problema resolent instàncies més petites del mateix problema. Aquesta tècnica s'utilitza sovint en programació per resoldre problemes que es poden desglossar en subproblemes més simples i similars.

1. Resolució de tasques complexes:

Les funcions recursives divideixen problemes complexos en instàncies més petites del mateix problema, donant com a resultat un codi compacte i llegible.

2. Divideix i vencerà:

Les funcions recursives són adequades per a algorismes de dividir i conquerir, com ara l'ordenació per fusió i l'ordenació ràpida, dividint els problemes en subproblemes més petits, resolent-los de manera recursiva i fusionant les solucions amb el problema original.

comentaris java

3. Fes marxa enrere :

El retrocés recursiu és ideal per explorar i resoldre problemes com N-Queens i Sudoku.

4. Dinàmica programació:

Les funcions recursives resolen de manera eficient problemes de programació dinàmica resolent subproblemes i combinant les seves solucions en una solució completa.

5. Arbre i estructures gràfiques:

Les funcions recursives són excel·lents per treballar amb estructures d'arbres i gràfics, simplificant les tasques de recorregut i reconeixement de patrons. .

Com escriure una funció recursiva:

Components d'una funció recursiva:

Cas base: Tota funció recursiva ha de tenir un cas base. El cas base és l'escenari més senzill que no requereix més recursivitat. Aquesta és una condició de terminació que impedeix que la funció es cridi a si mateixa indefinidament. Sense un cas base adequat, una funció recursiva pot conduir a una recursivitat infinita.

Cas recursiu: En el cas recursiu, la funció s'anomena amb els arguments modificats. Aquesta és l'essència de la recursivitat: resoldre un problema més gran dividint-lo en instàncies més petites del mateix problema. El cas recursiu s'ha d'apropar al cas base amb cada iteració.

eina de curació gimp

Considerem l'exemple de factorial de nombre :

En aquest exemple, el cas base és quan n és 0 , i la funció torna 1 . El cas recursiu es multiplica n amb el resultat de la funció cridada amb paràmetre n-1 . El procés continua fins que s'arriba al cas base.

intel·ligència artificial i agents intel·ligents

És essencial assegurar-se que la funció recursiva té un cas base correcte i que les trucades recursives condueixen al cas base, en cas contrari, el procediment podria executar-se indefinidament, provocant un desbordament de la pila (superant la memòria disponible assignada per a les trucades de funció).

A continuació es mostra la implementació del factorial d'un nombre:

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

Complexitat temporal: O(n)
Espai auxiliar: O(n)