Recursive programming

catalog

Experiment content

The following questions are designed by recursion method, and the recursion exit (the condition of the end of recursion) and recursion expression of each question are given. At the same time, whether the problem can be designed as a non recursive method, if possible, design a non recursive algorithm.
1. A person drives ducks to sell in every village, and sells half and one duck after each village. After passing seven villages, he had two ducks left. How many ducks did he catch when he set out? How many ducks are sold through each village?
2. Angle Valley theorem. Enter a natural number. If it's even, divide it by 2. If it's odd, multiply it by 3 plus 1. After such a finite number of operations, the natural value 1 can always be obtained. How many times can we get the natural number 1.
For example, enter 22,
Output 22 11 34 17 52 26 40 20 10 5 16 8 2 1
STEP=16

Topic analysis

1. It passes through seven villages in total, so the termination condition of recursion can be set as num < 8, i.e. it passes through the 7th village to terminate recursion.
2. After finite operations, the natural value 1 is obtained, and the operation ends, so the recursive termination condition is num = 1.

Algorithm construction

1. Start from passing the first village (num=1), execute the recursion body statement circularly until num is added to 8, no recursion body is executed, and return the total count of ducks in each village.
While (Num < 8) / / the number of recursive termination condition villages is 7
{
Count = (count + 1) * 2; / / count is the total number of ducks in each village
Sale = count / 2 + 1; / / sale indicates the number of ducks sold
printf("passing village% d: selling duck% d\n", num, sale);
num=num+1;
}
return count;
2. Input the number num to be calculated, and execute the recursive body. Every time step is executed, add 1 to get the num value of 1, jump out of the loop and return to step.
while(num!=1) {/ / recursion termination condition num is 1
if(num%2==0){
num/= 2;
printf("%d ",num);
return count(num,step+1);
}
else{
num=num*3+1;
printf("%d ",num);
return count(num,step+1);
}
}
return step;

Algorithm implementation

//recursive algorithm
#include<stdio.h>
int count =2;
int duck(int num)
{
	int sale = 0;	//Ducks sold
	while (num <8)   	//Number of villages with recursion termination condition is 7
	{
		count = (count + 1) * 2;   //count is the total number of ducks in each village
		sale = count / 2 + 1;      //sale indicates the number of ducks sold
		printf("After%d Villages:Sell duck%d only\n", num, sale);
		num=num+1;
	}
	return count;
}

void main(){
	int num =1;  //First village
    count = duck(num);	//Call recursive function to find the total number of ducks
	printf("We were in a hurry at the time of departure%d Duck\n", count);
}
//non-recursive algorithm 
#include <stdio.h>
int main(){
	int i,sale;
	int x =2;
	for(i=1;i<8;i++){
		x =(x+1)*2;
		sale =(x/2)+1;
		printf("After%d Villages: selling ducks%d only\n",i,sale);
	}
	printf("We were in a hurry at the time of departure%d Duck\n",x);
}
//recursive algorithm
#include<stdio.h>
int count(int num,int step)
{
	//Recursive termination condition num is 1
	while(num!=1){
		if(num%2==0){	
			num/= 2;
			printf("%d ",num);
			return count(num,step+1);
		}
		else{
			num=num*3+1;
			printf("%d ",num);
			return count(num,step+1);
		}
	}
	return step;
}

int main(){
int num=0;	
	int step=1;	//Steps initialized to 1
	printf("Please enter a natural number to calculate the angle Valley theorem:\n");
	scanf("%d", &num);
	step=count(num,step);	//Call recursive function to find steps
	printf("\nStep=%d\n", step);
	return 0;
}
//non-recursive algorithm 
#include<stdio.h>	
int count(int num,int step)
{
	for(step;num!=1;step++)
	{
		if(num%2==0){
			num/=2;
			printf("%d ",num);
		}
		else{
			num= num*3+1;
			printf("%d ",num);
		}
	}
	return step;
}

int main(){
	int step=1;	//Non recursive step initialization
	int num;
	printf("Please enter a natural number to calculate the angle Valley theorem:\n");
	scanf("%d", &num);
	step=count(num,step);	//Call non recursive function to find steps
	printf("\nStep=%d\n",step);
	return 0;
}

Operation results


Posted on Sun, 07 Jun 2020 01:12:38 -0700 by CAPTAINCAPSLOCK