Recursive Functions

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: 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);

}