Masalah dan penyelesaian amalan rekursi

Dalam artikel ini, kita akan membincangkan beberapa masalah amalan rekursi dan penyelesaian terperincinya.

Mari kita fahami apa itu rekursi dan cara ia berfungsi:

Rekursi - Rekursi ialah teknik pengaturcaraan di mana fungsi atau kaedah memanggil dirinya beberapa kali untuk menyelesaikan masalah. Fungsi ini memecahkan masalah kepada sub-masalah yang lebih kecil dan menyelesaikannya sehingga kes asas dicapai.

Kes asas ialah keadaan berhenti yang memastikan fungsi berhenti memanggil dirinya sendiri dan mengembalikan hasilnya dalam masa yang terhad.

Rekursi ialah teknik yang berkuasa untuk menyelesaikan masalah yang kompleks, tetapi adalah penting untuk mereka bentuknya dengan teliti untuk mengelakkan gelung tak terhingga dan untuk memastikan bahawa fungsi ditamatkan dengan betul apabila fungsi dipanggil secara rekursif beberapa kali.

Soalan 1

Ini adalah soalan paling asas yang berkaitan dengan rekursi.

Cari faktorial bagi nombor yang diberi menggunakan konsep faktorial.

Pelaksanaan dalam 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;
}

Output

The factorial of 5 is 120

Soalan 2

Dalam masalah ini, kita perlu mencetak nombor ke-n dalam urutan bermula dari 1, di mana nombor ke-i ialah hasil tambah dua nombor pertamanya, biasanya dikenali sebagai jujukan Fibonacci.

Pelaksanaan dalam 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;
}

Output

The 9th number of the Fibonacci series is 34

Soalan 3

Kira jumlah digit dalam nombor yang diberi

Pelaksanaan dalam 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;
}

Output

The sum of digits of the number 563 is 14

Soalan 4

Kira nilai "kuasa" sesuatu nombor.

Dalam soalan ini, kita akan diberikan dua nombor "nombor" dan "kuasa", dan tugas kita adalah untuk mencari kuasa "kuasa" nombor "nombor".

Pelaksanaan dalam 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;
}

Output

The number 2 To the power 6 is 64

Soalan 5

Cari GCD (pembahagi sepunya terhebat) bagi dua nombor.

GCD bermaksud Pembahagi Sepunya Terhebat, iaitu nombor terbesar yang membolehkan dua atau lebih nombor boleh dibahagikan tanpa baki. Ia juga dipanggil faktor sepunya tertinggi (HCF) bagi nombor ini.

Andaikan kita mempunyai dua nombor berbeza: 14 dan 28.

Faktor 14 ialah 1, 2, 7 dan 14.

28 ialah 1, 2, 4, 7, 14 dan 28.

Kita kemudiannya boleh mencari faktor sepunya bagi dua nombor ini, iaitu 1, 2, 7 dan 14. Nombor terbesar yang boleh membahagi kedua-dua 14 dan 28 tanpa meninggalkan baki ialah 14, jadi pembahagi sepunya terbesar bagi 14 dan 28 ialah 14.

Pelaksanaan dalam 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;
}

Output

The Greatest common divisor of 36 and 60 is 12

Soalan 6

Cetak tatasusunan dalam susunan terbalik

Kami mendapat tatasusunan yang mengandungi n integer, dan tugas kami ialah mencetak tatasusunan yang sama mengikut tertib, dengan nombor pertama sebagai nombor terakhir, nombor kedua sebagai nombor kedua hingga nombor terakhir, dan seterusnya .

Pelaksanaan dalam 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;
}

Output

the given array is reverse order is 
5 4 3 2 

Berikut ialah beberapa lagi soalan latihan asas untuk menguasai tahap asas rekursi -

Tulis fungsi untuk menyemak secara rekursif sama ada rentetan ialah palindrom.

Tulis fungsi menggunakan rekursi ekor untuk mencari pemfaktoran nombor tertentu.

Tulis fungsi untuk menyelesaikan masalah Menara Hanoi.

Tulis fungsi untuk melakukan carian binari pada tatasusunan yang diisih.

Atas ialah kandungan terperinci Masalah dan penyelesaian amalan rekursi. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!