C Recursive Function

Summary: in this tutorial, you will learn about the C recursive function, which is a function that calls itself.

C c recursive functionrecursive function definition

A recursive function is a special function that calls to itself. Like other programming languages, C allows you to define recursive functions easily.

Why recursive function

A recursive function allows you to break down a complex problem into identical sub-problems recursively until the sub-problems are simple enough to solved directly. The solutions are then combined to produce the solution to the original problem. This is a famous programming technique called divide and conquer.

Notes of using recursive function

A recursive function must have at least one exit condition that must be satisfied. Otherwise, the recursive function will call itself indefinitely until a stack overflow error occurs.

C recursive function example

A recursive function is closely related to a definition of function in mathematics. For example, the factorial number of a positive integer N is calculated as the following formula:

N! = N*(N-1)*(N-2)…2*1;

Or defined by using a recursive function:

N! = 1 if N <=1 and N! = N*(N-1)! if N > 1

The C recursive function to calculate the factorial of a positive integer N is as follows:

How it works.

  • Calculate the factorial of n via factorial of n-1 recursively until n is equal to 1.
  • If n is less than or equal to 1, the factorial of n is 1.

The output of the program when you enter 4 to calculate its factorial number is:

In theory, all recursive functions can be rewritten by a loop statement such as while loop, do while loop or for loop. In case the number of recursive calls exceeds, a stack overflow error occurs. In this situation, you have to re-implement the recursive function by using a loop statement.

For example, we can rewrite the factorial calculation function that use the while loop statement as follows:

Recursion technique is applied in many algorithms e.g., it is implemented in the quicksort algorithm and binary search algorithm.

In this tutorial, we’ve shown you how to use recursive functions. The recursion technique can be effective if you apply it appropriately.