Problèmes et solutions de pratique de récursion

Dans cet article, nous discuterons de certains problèmes de pratique de récursivité et de leurs solutions détaillées.

Commençons par comprendre ce qu'est la récursivité et comment elle fonctionne :

Récursion - La récursion est une technique de programmation dans laquelle une fonction ou une méthode s'appelle plusieurs fois pour résoudre un problème. Cette fonction divise le problème en sous-problèmes plus petits et les résout jusqu'à ce que le cas de base soit atteint.

Le cas de base est une condition d'arrêt qui garantit que la fonction cesse de s'appeler et renvoie le résultat dans un temps limité.

La récursion est une technique puissante pour résoudre des problèmes complexes, mais il est important de la concevoir avec soin pour éviter les boucles infinies et pour garantir que la fonction se termine correctement lorsqu'une fonction est appelée de manière récursive plusieurs fois.

Question 1

C'est la question la plus fondamentale liée à la récursivité.

Trouvez la factorielle d'un nombre donné en utilisant le concept de factorielle.

Implémentation en C++

#include <bits/stdc++.h>
using namespace std;
// recursive function to 
// calculate factorial of number
int Numberfact(int number) {
// base condition
    if(number == 1) {
        return 1;
    } else {
        return number * Numberfact(number-1);
    }
}
// main code
int main() {
   int number = 5;
   cout<< " The factorial of 5 is " << Numberfact(number);
   return 0;
}

Sortie

The factorial of 5 is 120

Question 2

Dans ce problème, nous devons imprimer le n-ème nombre de la séquence commençant à 1, où le i-ème nombre est la somme de ses deux nombres précédents, communément appelé séquence de Fibonacci.

Implémentation en C++

#include <bits/stdc++.h>
using namespace std;
// function to 
// calculate nth number of
// Fibonacci series
int Numberfib(int number) {
   // base condition
   if(number <= 1) {
      return number;
   } else {
      return Numberfib(number-1)+Numberfib(number-2);
   }
}
// main code
int main() {
   int number = 9;
   cout<< " The 9th number of the Fibonacci series is " << Numberfib(number);
   return 0;
}

Sortie

The 9th number of the Fibonacci series is 34

Question 3

Calculer la somme des chiffres d'un nombre donné

Implémentation en C++

#include <bits/stdc++.h>
using namespace std;
// recursive method to 
// calculate sum of digits
int Sumofdigits(int number) {
// base case
   if(number <=10) {
      return number;
   }
   else {
      return number%10 + Sumofdigits( number/10 );
   }
}
// main code
int main() {
   int number = 563;
   cout<< " The sum of digits of the number " << number << " is "<< Sumofdigits(number);
   return 0;
}

Sortie

The sum of digits of the number 563 is 14

Question 4

Calculez la valeur "puissance" d'un nombre.

Dans cette question, on nous donnera deux nombres « nombre » et « puissance », et notre tâche est de trouver la puissance de « puissance » du nombre « nombre ».

Implémentation en C++

#include <bits/stdc++.h>
using namespace std;
// recursive method to 
// generate the nth power
// of a given number
int powerofx( int nums , int pow) {
   // termination condition
   if(pow == 0) {
      return 1;
   } else {
      return nums*powerofx(nums, pow-1);
   }
}
// main code
int main() {
   int nums = 2;
   int pow =6;
   cout<< " The number " << nums << " To the power "<< pow <<" is "<< powerofx(nums, pow);
   return 0;
}

Sortie

The number 2 To the power 6 is 64

Question 5

Trouvez le PGCD (plus grand diviseur commun) de deux nombres.

GCD signifie Plus grand diviseur commun, qui est le plus grand nombre par lequel deux nombres ou plus peuvent être divisés sans reste. On l'appelle également le facteur commun le plus élevé (HCF) de ces nombres.

Supposons que nous ayons deux nombres différents : 14 et 28.

Les facteurs de 14 sont 1, 2, 7 et 14.

Les facteurs de 28 sont 1, 2, 4, 7, 14 et 28.

On peut alors trouver les facteurs communs de ces deux nombres, qui sont 1, 2, 7 et 14. Le plus grand nombre qui peut diviser 14 et 28 sans laisser de reste est 14, donc le plus grand diviseur commun de 14 et 28 est 14.

Implémentation en C++

#include <bits/stdc++.h>
using namespace std;
// function to recursively
// calculate the gcd
int greatestcommondivisor(int num1, int num2) {
   if (num2 == 0) {
      return num1;
   } else {
      return greatestcommondivisor(num2, num1 % num2);
   }
}
// main code
int main() {
   int num1 = 36;
   int num2 =60;
   cout<< " The Greatest common divisor of " << num1 << " and "<< num2<<" is "<< greatestcommondivisor(num1, num2);
   return 0;
}

Sortie

The Greatest common divisor of 36 and 60 is 12

Question 6

Imprimer le tableau dans l'ordre inverse

Nous obtenons un tableau contenant n entiers et notre tâche est d'imprimer le même tableau dans l'ordre avec le premier nombre comme dernier nombre, le deuxième nombre comme avant-dernier nombre et ainsi de suite.

Implémentation en C++

#include <bits/stdc++.h>
using namespace std;
// recursive function to 
// =reverse print the given array
void reverseprint(int nums[], int begining, int end) {
   if (begining >= end) {
      return ;
   } else {
      cout << nums[end-1] << " ";
      reverseprint(nums, begining, end - 1);
   }
}
// main code
int main() {
   int size =4;
   int nums[] = { 2, 3, 4, 5 } ;
   cout<< " the given array is reverse order is " << endl ;
   reverseprint(nums, 0, size);
   return 0;
}

Sortie

the given array is reverse order is 
5 4 3 2 

Voici quelques questions pratiques de base pour maîtriser un niveau de récursion de base -

Écrivez une fonction pour vérifier récursivement si une chaîne est un palindrome.

Écrivez une fonction en utilisant la récursion de queue pour trouver la factorielle d'un nombre donné.

Écrivez une fonction pour résoudre le problème de la Tour de Hanoï.

Écrivez une fonction pour effectuer une recherche binaire sur un tableau trié.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!