1. Introduction Any function which calls itself is called recursive. A recursive method solves a PRoblem by calling a copy of itself to work on a smaller problem. It is important that the recursion terminates. Each time the function calls itself with s slightly simpler version of the original problem. The results of smaller problems must converge back on the base case.
2. General format
if(test for base case) return base case valueelse if(another base case) return other base case value//The recursive caseelse return (some work and then a recursive call)Example: To calculate factorial using recursive function:
int Factorial(int n){ if(n==0||n==1){ return 1; } else{ return n*Factorial(n-1); }}3. Problems and solutions
1. Towers of Hanoi
int Count=0;void Move(int n, char from, char middle, char to){ if(n==1){ cout<<"move "<<from<<" to "<<to<<endl; Count++; } else{ Move(n-1,from,to,middle); cout<<"move "<<from<<" to "<<to<<endl; Count++; Move(n-1,middle,from,to); }}2. Check of sorted array
bool Check(int a[],int n){ if(n==1||n==0){ return true; } else if(a[n-1]<a[n-2]){ return false; } else{ return Check(a, n-1); }}3. Fibonacci Sequence
int Fib(int a){ if(a==1||a==2){ return 1; } else{ return Fib(a-1)+Fib(a-2); }}新聞熱點(diǎn)
疑難解答
