在本文中,我们将讨论一些递归练习问题及其详细解决方案。
让我们首先了解什么是递归以及它是如何工作的:
递归 - 递归是一种编程技术,其中函数或方法多次调用自身以解决问题。该函数将问题分解为更小的子问题并解决它们,直到达到基本情况。
基本情况是一个停止条件,确保函数停止调用自身并在有限时间内返回结果。
递归是解决复杂问题的强大技术,但仔细设计它以避免无限循环并确保函数在递归多次调用函数时正确终止非常重要。
问题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
求两个数的 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
以下是一些更基础的练习问题,以掌握递归的基本水平 -
编写一个函数来递归检查字符串是否为回文。
使用尾递归编写一个函数来找到给定数字的阶乘。
编写一个函数来解决汉诺塔问题。
编写一个函数来对排序数组执行二分搜索。