C++ 递归练习问题及解决方案

在本文章中，我们将讨论一些带有详细解决方案的递归练习问题。

首先让我们了解什么是递归，以及它是如何工作的：

递归 -递归是一种编程技术，其中一个函数或方法多次调用自身以解决问题。该函数将问题拆分为更小的子问题并解决，直到达到基本情况。

基本情况是一个停止条件，确保函数停止调用自身并在有限时间内返回结果。

递归是解决复杂问题的强大技术，但设计时需要小心，以避免无限循环，并确保函数正确终止，因为递归调用了函数多次。

问题1

这是与递归相关的最基本的问题。

使用阶乘的概念找出给定数字的阶乘。

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

输出

The factorial of 5 is 120

问题2

在这个问题中，我们需要打印从1开始的一系列数中的第n个数，其中第i个数是其前两个数的和，这个系列被广泛称为斐波那契数列。

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

输出

The 9th number of the Fibonacci series is 34

问题3

计算给定数字中各个数字的总和

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

输出

The sum of digits of the number 563 is 14

问题4

计算一个数的“幂”的值。

在这个问题中，我们会给出两个数“number”和“power”，我们的任务是找到数“number”的“power”次方。

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

输出

The number 2 To the power 6 is 64

问题5

找到两个数的最大公约数（Greatest Common Divisor）。

最大公约数（Greatest Common Divisor），又称最大公因数（Highest Common Factor），是能够整除一组两个或多个数的最大数，且没有余数。

假设我们有两个不同的数，14和28。

14的因数有1、2、7和14。

28的因数有1、2、4、7、14和28。

然后我们可以找出这两个数共有的因数，它们是1、2、7和14。能够整除14和28而没有余数的最大数是14，所以14和28的最大公约数是14。

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

输出

The Greatest common divisor of 36 and 60 is 12

问题 6

按逆序打印数组

给定一个包含 n 个整数的数组，我们的任务是按照顺序打印出来，其中第一个数字作为最后一个数字，第二个数字作为倒数第二个数字，依此类推。

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

输出

the given array is reverse order is 
5 4 3 2

以下是一些更多的基础实践问题，以掌握递归的基本水平：

编写一个递归函数来检查一个字符串是否是回文。

编写一个递归函数来使用尾递归找到给定数字的阶乘。

编写一个函数来解决汉诺塔问题。

编写一个函数来在已排序的数组上执行二分查找。