递归练习题及解答

---

在本文中，我们将讨论一些递归练习题及其详细解答。

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

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

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

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

问题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

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

在这个问题中，我们将得到两个数字“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

求两个数的最大公约数 (GCD)。

GCD（最大公约数）是可以除以一组两个或多个数字而没有任何余数的最大数字。它也称为这些数字的最高公因子 (HCF)。

假设我们有两个不同的数字，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 

下面是一些更基本的练习题，可以帮助你掌握递归的基础知识：

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

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

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

编写一个函数对排序数组执行二分查找。