What is Recursion?
Recursion is a way of programming where a function calls itself to solve smaller parts of the same problem.
printf(“This function does not stop!!!.n“);
fun(); // Recursive call without a base case
}
int main() {
fun();
return 0;
}
This is not a recursive program because a recursive program is expected to have a base case.
How does a base case function in recursion?
A base case helps stop the recursion in programs.
Example:-
if(n == 0){
return 1; // base case
}
return n * factorial(n – 1);
}
int main() {
int n = 3;
int result = factorial(n);
printf(“%d”, result);
return 0;
}
6
How does this program work? Step-by-step explanation:-
Step1:-
if(3 == 0){ // false
return 1; // base case
}
return 3 * factorial(2); // 3 – 1 = 2
}
int main() {
int n = 3;
int result = factorial(3); // n = 3
println(“%d”, result);
return 0;
}
Call the main function to the factorial function, passing a parameter n.
Step2:-
factorial(3) called to factorial(2)
if(2 == 0){ // false
return 1; // base case
}
return 2 * factorial(1); // 2 – 1 = 1
}
Step3:-
factorial(2) called to factorial(1)
if(1 == 0){ // false
return 1; // base case
}
return 1 * factorial(0); // 1 – 1 = 0
}
Step4:-
factorial(1) called to factorial(0)
if(2 == 0){ // true
return 1; // base case
}
return 0 * factorial(–1); // 0 – 1 = -1 *this line not executed*
}
Return values
|
factorial(1) = 1 * 1 = 1 // return 1 to factorial(2)
|
factorial(2) = 2 * 1 = 2 // return 2 to factorial(3)
|
factorial(3) = 3 * 2 = 6 // return 6 to result variable
// after print result
