Recursive functions
Recursive functions are functions that call themselves. Several problems are naturaly defined recursively. Those problems may be solved by using recursive functions.
Example: Factorial of a positive integer number.
0! = 1
1! = 1
n! = n * (n-1)! , if n > 1
int factorial(int val){
if(val <= 1) //stop condition.
return 1;
else
return val * factorial(val-1); //recursive call.
}
Stop condition: Condition to stop recursive calling and return. Written before recursive calling.
Recursive calling: The problem to solve should be simpler than the previous problem. The recursive calling ends at stop condition.
Advantages: compact code, easier to write and understand.
Disadvantages: intensive stack usage, recursive functions aren't faster than equivalent non recursive functions.
Some usage examples: String manipulation, linked list operations, binary tree operations.
Example: Count number of characters in a string.
int count(char *st)
{
if(*st == '\0')
return 0;
else
return 1+conut(st+1);
}
Example: Count number of characters in a string.
int count(char *st)
{
if(*st == '\0')
return 0;
else
return 1+conut(st+1);
}
Example: reverse a string.
void puts_inv(char *st)
{
if(*st == '\0')
return;
else
{
puts_inv(st+1);
putchar(*st);
}
}
Examples of incorrect recursive functions:
long int factorial(long int val)
{
return val * factorial(val-1);
if(val <= 1) return 1;
}
long int factorial(long int val)
{
if(val <= 1) return 1;
else return val * factorial(val);
}
long int factorial(long int val)
{
if(val <= 1) return 1;
else return val * factorial(val+1);
}
