编程集训 day05 recursion & dynamic programming

1. recursion

“The process in which a function calls itself is known as recursion and the corresponding function is called the recursive function ”. Factorial function is a popular example to understand recursion.
diagram:

https://beginnersbook.com/wp-content/uploads/2017/08/Recursion_in_Cpp.jpg

code

#include <iostream>
using namespace std;

int factorial_function(int);

int factorial_function(int n){
	if(n <= 1){
		return 1;
	}
	else{
		return n*factorial_function(n-1);
	}
}
int main(){
	int num;
	cout << "Please enter a number." << endl;
	cin >> num;
	cout << "The factorial of " << num << " is " << factorial_function(num) << endl;
return 0;

Direction Recursion and Indirect Recursion
Direction Recursion: Function calls itself (function a calls function a). Factorial Recursion is Direction Recursion.
Indirect Recursion: Function calls another function that calls the calling function( function a calls function b and function b calls function a).

Example Code

#include <iostream>

using namespace std;

int functionA(int);
int functionB(int);

int functionA(int n){
	if(n <= 1){
		return 1;
	}
	else{
		return n*functionB(n-1);
	}
}
int functionB(int n){
	if(n <= 1){
		return 1;
	}
	else{
		return n*fucntionA(n-1);
	}
}
int main(){
	cout << "Please enter a number." << endl;
	cin >> num;
	cout << "The factorial of " << num << " is " << functionA(num) << endl;
	return 0;

2. dynamic programming

what is dynamic programming?
“Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming”(GeeksforGeeks).

Problem : Minimum Steps To One (“Tutorial For Dynamic Programming”)
Problem Statement: On a positive integer, you can perform any one of the following 3 steps. 1.) Subtract 1 from it. ( n = n - 1 ) , 2.) If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 ) , 3.) If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 ). Now the question is, given a positive integer n, find the minimum number of steps that takes n to 1

eg: 1.)For n = 1 , output: 0 2.) For n = 4 , output: 2 ( 4 /2 = 2 /2 = 1 ) 3.) For n = 7 , output: 3 ( 7 -1 = 6 /3 = 2 /2 = 1 )

code(“Tutorial For Dynamic Programming”):

int getMinSteps ( int n )

{

int dp[n+1] , i;

dp[1] = 0;  // trivial case

for( i = 2 ; i < = n ; i ++ )

{

dp[i] = 1 + dp[i-1];

if(i%2==0) dp[i] = min( dp[i] , 1+ dp[i/2] );

if(i%3==0) dp[i] = min( dp[i] , 1+ dp[i/3] );

}

return dp[n];

}

Dynamic Programming solves each subproblem only once. Therefore, it is very fast. In addition, it avoids to re-compute the answer.

Resources：
“C++ recursion with example”， https://beginnersbook.com/2017/08/cpp-recursion/
diagram: https://beginnersbook.com/wp-content/uploads/2017/08/Recursion_in_Cpp.jpg
"Recursion (Computer Science), https://en.wikipedia.org/wiki/Recursion_(computer_science)
“Dynamic Programming”, https://www.geeksforgeeks.org/dynamic-programming/
“Tutorial For Dynamic Programming”, https://www.codechef.com/wiki/tutorial-dynamic-programming
“What Is Dynamic Programming and How To Use It”, https://www.youtube.com/watch?v=vYquumk4nWw