Introduction

A recursive function can be defined in two ways. It can be defined as a function that keeps calling itself repeatedly, until a specified condition is met. It can also be defined as a function that keeps calling itself; and for each call, some code of the function definition, or the whole function definition call, is stored in memory, until a base case is reached. Just after the base case is reached, the code that was stored in memory or the whole function definition call, is executed in reverse order, from the order that it was stored in memory.

Four different problems are addressed in this tutorial (article). For each problem, the problem is first solved with a while-loop, then using the first definition above, then using the second definition above, and then considering the case when the calling function is returned. In the case of the calling function being returned, the calling function may be returned together with an operation. The problems are: a recursive function that returns void; a recursive function that returns a value; a recursive array summation, and a recursive function for factorial of a whole number.

A Recursive Function that returns void

while-loop

The following function counts integers from 0 to 4. The condition to be met or base case, is that the incrementing variable, i should not be equal to 5 or greater.

    #include <stdio.h>

    void fn (int i) {
        while (i<5) {
            printf("%i ", i);    //i in "%i " means integer and not index
            i = i + 1;
        }
    }

    int main(int argc, char *argv[])
    {
        fn(0);
        printf("\n");

        return 0;
    }

The output is:

0 1 2 3 4

Read through the code to understand the while-loop and appreciate the use of the condition met (or base case). The number of main operations in the while loop are 5, beginning from i=0 and ending at i=4. i cannot be equal to 5 or greater.

The function, fn() with the while-loop here, is not a recursive function. The aim of using the while-loop here, is to show that a recursive function can be written as a while-loop.

Repeated Calling of function until Condition is met

The following code solves the same problem above, by iterating until a condition is met in recursion:

    #include <stdio.h>

    void fn (int i) {
        printf("%i ", i); //i in "%i " means integer and not index
        i = i + 1;
        if (i < 5)
            fn(i);
    }

    int main(int argc, char *argv[])
    {
        fn(0);
        printf("\n");

        return 0;
    }

The output is the same as above; that is: 0 1 2 3 4

Read through the code. fn() here, is a recursive function.

The function of interest is fn(). It has only one argument. When called the first time, the argument is 0. The first statement in the function prints the current number, and a space. The second statement increments the number: that is, 1 is added to the previous value of i on the right-hand-side of = ; and the result becomes the new value of i, which is on the left-hand-side of = . The condition to stop the function calling itself is in the if-statement. As long as (i < 5) is true, fn(i) is called again, where i here is the next number. The stopping condition can be considered as the base case.

There are 5 main operations here, which consist of the 5 calls. The first call is from the C main() function. The calls with 1, 2, 3 and 4, are from the if-condition.

Store some Code in Memory until Base Case is reached, then have Stored Code executed in Reverse Order

Consider the following program that solves the same problem above:

    #include <stdio.h>

        void     fn(int no) {
            if (no == 0)
                return;
        no = no - 1;
        fn(no);
        printf("%i ", no);
    }

    int main(int argc, char *argv[])
    {
        fn(5);
        printf("\n");

        return 0;
    }

The output is the same as before, that is:

0 1 2 3 4

Read through the code.

The base case is now:

    if (no == 0)

        return;

Note that the return statement does not have any value. This is because the function returns void.

The first input to the function is 5, this time, and not 0. Five calls of the function definition are made, and for each call, 1 is subtracted from no. When the subtraction reaches 0, the base case is reached. The code: printf("%i ", no); below the function call, fn(no); that was stored in memory (RAM) for each call, is then executed in reverse order of storage, before the running of the function closes up completely.

Again, note that the last statement in the function definition fn(), prints no. Just before this code "printf("%i ", no);", is the recalling of the function itself, with fn(no) . For the 5 forward calls of the function, the code printf("%i ", no) is stored in memory. After the 5 calls, when the based case has just been reached, the code printf("%i ", no) is executed in reverse order, in which they were stored. This is because, the recalling of fn(no) was made before printf("%i ", no) in the function code. And so, for each pass through the body of the whole function fn(), printf("%i ", no) is stored in memory, leading to Last-In-First-Out execution of the stored printf("%i ", no) (stack behavior). In this situation there are 10 iterations, with the first 5 doing the whole body of the function definition, and the second 5 doing only the printf("%i ", no) statement (in reverse order).

Returning Calling Function

When the calling function is returned in the returned statement, no statement below the principal returned statement and the closing } for the function, are kept in memory for later execution in reverse order. The following program illustrates this for the same problem above:

    #include <stdio.h>

    void fn(int no) {
        if (no == 5)
            return;
        printf("%i ", no);
        no = no + 1;
        return fn(no); //return calling function
        printf("%i ", no); //not stored in memory and not executed, i.e. ignored
    }

    int main(int argc, char *argv[])
    {
        fn(0);
        printf("\n");

        return 0;
    }

The output is the same as before, i.e. 0 1 2 3 4

Read through the code.

Since the code after the principal (last) return statement and before the end of the function definition is not executed. The input from the C main() function is 0 and not 5. "no = no - 1;" was changed to "no = no + 1;" compared to the previous example. The base case was changed from

    if (no == 0) return;

to

    if (no == 5) return;

Since the return type for the function is void, the statement, "return fn(no);" still does not return anything. Rather, it returns by recalling the function. Recalling a function in the return statement is still returning void. In this case the principal return statement serves two purposes, which are: it indicates the end of the evaluation (pass) through the function body from top to bottom; and it recalls the function for the next iteration (until base case is reached).

Here, the return statement of the base case, marks the end of the forward iterations. There are no reverse order iterations (calls) for this example.

A Recursive Function that returns a Value

The above problem of displaying numbers from 0 to 4 will be repeated here, in this section. There will be two arguments for the function, just to show that the function can have more than one argument. The second argument will deliberately not be changed in the body of the function definition.

while-loop

The following function counts integers from 0 to 4.

    #include <stdio.h>

    int fn (int i, int z) {
        while (i<5) {
            printf("%i ", i);
            i = i + 1;
        }
        return z;
    }

    int main(int argc, char *argv[])
    {
        int ret = fn(0, 9);
        printf("\n");
        printf("%i\n", ret);

        return 0;
    }

The output is:

0 1 2 3 4

9

The function fn() with its while-loop here, is not a recursive function. It has been presented, just to show that a recursive function can be replaced by a while-loop. The second parameter, z was not modified in the body of the fn() function definition. It was just returned by the single return statement, after the while-loop code, in the fn() body.

Repeated Calling of Function until Condition is met

The following code solves the same problem above, by iterating until a condition is met in recursion:

    #include <stdio.h>

    int fn (int i, int z) {
        printf("%i ", i);
        i = i + 1;
        if (i < 5)
            fn(i, z);

        return z;
    }

    int main(int argc, char *argv[])
    {
        int ret = fn(0, 9);
        printf("\n");
        printf("%i\n", ret);

        return 0;
    }

The output is:

0 1 2 3 4

9

as expected. fn() here is a recursive function. The return statement "return z;" in the function definition fn(), is executed only at the last iteration. Whenever the recall of fn(i, z) is made, the return statement is skipped in each previous iteration. When the condition is met at the last iteration, there is no recalling of the function and the return statement is executed. No code is saved in memory (RAM) here, for later reversed execution. The value of z is not changed in any of the iterations. However, the value of i is changed (modified) in each iteration. The changed value is passed as an argument in the recalling of the function.

Store some Code in Memory until Base Case is reached, then have Stored Code executed in Reverse Order

In the following code, the two statements, "printf("%i ", no);" and "return z;" between the recalling function call, fn(no, z) and the end of its function definition, are kept in memory (RAM) just after fn(no, z) is reached, in each iteration. They are executed as typed, in reverse order of iteration after the first 5 iterations.

    #include <stdio.h>

    int fn (int no, int z) {
            if (no == 0)
                return 7;
            no = no - 1;
            fn(no, z);
            printf("%i ", no);

            return z;
    }

    int main(int argc, char *argv[])
    {
    int ret = fn(5, 9);

The output is:

0 1 2 3 4

9

Read through the code.

The last value of z is returned, which never changed in any of the iterations. The first input value from the C main() function is 5, and not 0. It is reduced by 1 in each iteration. no is sent as argument in each function call or recall. Notice that at the output, the value of 7 of the base case is not seen. The base case is:

if (no == 0)

return 7;

Since the return type for the fn() function is int, the statement "return 7;" is just there for the sake of this return type. In fact, if "return 7;" is replaced with "return;", that is, return void, the user will just receive a warning message, and the program will still work. That is why 7 is not found at the output.

Returning Calling Function

When the calling function is returned in the returned statement, the body of the recursive function may modify some of the parameters and not modify others. Also, no statement below the returned statement are kept in memory for later execution in reverse order. The following program illustrates this for the same problem above:

    #include 
    
    int fn (int no, int z) {
        if (no == 5)
            return z;
        printf("%i ", no);
        no = no + 1;
        return fn(no, z);    //return calling function
        printf("%i ", no);    //not stored in memory and not executed, i.e. ignored
            
        return z;    //not stored in memory and not executed, i.e. ignored
    }

    int main(int argc, char *argv[])
    {
        int ret = fn(0, 9);
        printf("\n");
        printf("%i\n", ret);

        return 0;
    }

The output is:

0 1 2 3 4

9

Read through the code.

Since the statements after the return function statement, "return fn(no, z);" and before the end of the function definition are not executed, the input from the C main() function is 0 and not 5. "no = no - 1;" was changed to "no = no + 1;" , comparing with the previous example. The base case was changed from

        if (no == 0)
            return 7;
to
        if (no == 5)
            return z;

Since the vary last return statement is ignored, the return statement of the base case has to have a useful return integer value, as the function must return an int. z which did not change in any of the iterations, was returned.

The fn() function should return an int. This is achieved by the base case return statement:

    return z;

and not by the recursive (recalling) return statement:

    return fn(no, z);

in this situation. The recursive last return statement does not address that. Its aim its to cause recursion (recalling) of the function, and mark the end of each pass (iteration).

Recursive Array Summation

The summation of the 5 numbers: 0, 1, 2, 3, 4 is 0+1+2+3+4 = 10. That is: 0+1=1; 1+2=3; 3+3=6; 6+4=10 . In this section, the following array will be used:

The values are: 0, 1, 2, 3 and 4. The summation of all the elements in the array will be done in 4 ways:

This will be done as follows: using a while-loop, using a recursive function where a condition is met, using a recursive function where some or all function code is kept in memory and executed in reverse order, and using a recursive function, where the principal return statement returns the function call.

while-loop

The following program does not have a recursive function. It is just to show that a while-loop can do what a recursive function would do. The function, fn() adds all the elements of the array and returns the sum (the continuously added values are also displayed). Each call sends the next array value as argument.

    #include 

    int arr[] = {0, 1, 2, 3, 4};
    int sum = 0;
    int i=0;
    int fn(int val) {
        while (i < 5) {
            val = arr[i];
            sum = sum + val;
            printf("%i ", sum);    //i in "%i " means integer and not index
            i = i + 1;
        }
        
        return sum;
    }
    int main(int argc, char *argv[])
    {
        int total = fn(arr[0]);
        printf("\n");
        printf("%i\n", total);

        return 0;
    }

The output is:

0 1 3 6 10

10

Read through the code.

The total (final sum) is returned, coded just after the while-loop. Note that the use of arr[i] in the sum statement is avoided. It is also avoided as parameter in the function definition.

Repeated Calling of Function until Condition is met

In the following program, fn() is a recursive function. The function is called repeatedly in its definition, until a condition is met. The recursive function solves the same problem as above.

    #include 

    int arr[] = {0, 1, 2, 3, 4};
    int sum = 0;
    int i=0;
    int fn(int val) {
        val = arr[i];
        sum = sum + val;
        printf("%i ", sum);    //i in "%i " means integer and not index
        i = i + 1;
        if (i<5)
            fn(arr[i]);
        
        return sum;
    }
    int main(int argc, char *argv[])
    {
        int total = fn(arr[0]);
        printf("\n");
        printf("%i\n", total);

        return 0;
    }

The output is:

0 1 3 6 10

10

Read through the code (program).

The return statement in the function is executed, after all the 5 iterations have been made, that is, after the function has run (executed) 5 times, according to the if-condition. There is no saving of any code in memory here, for later execution, before the function finally ends.

Note that the use of arr[i] in the sum statement is avoided. It is also avoided as parameter in the function definition. Do not confuse between function definition and function call. Function definition is the description of the function, and function call is the short expression that calls (invokes) the function.

Store some Code in Memory until Base Case is reached, then have Stored Code executed in Reverse Order

In the following code, the two statements, "printf("%i ", sum);" and "return sum;" between the recalling function call, fn(sum, i) and the end of its function definition, are kept in memory (RAM) just after fn(sum, i) is reached, for each iteration. They are executed in reverse order of iteration after the first 5 forward iterations. The summation is done by code, from the back of the array.

    #include 

    int arr[] = {0, 1, 2, 3, 4};
    int sum = 0;
    int i=5;
    int fn(int sum, int i) {
        if (i == 0)
            return 8;
        i = i - 1;
        sum = sum + arr[i];
        fn(sum, i);
            
        printf("%i ", sum);    //i in "%i " means integer and not index
        return sum;
    }
    int main(int argc, char *argv[])
    {
        int total = fn(sum, i);
        printf("\n");
        printf("%i\n", total);

        return 0;
    }

The output is:

10 10 9 7 4

4

Read through the code.

The first line of the output is as expected; but the second line, though correct according to the algorithm, is not as expected, since 10 was expected. After the function has been called five times, the two particular statements are executed as a block, in reverse order of iteration, five times as well. It is the very last stored value of sum, that the last return statement returns. So the second line of the output is correct. In order to have obtained 10 as value for the last return statement, the last value for sum, before execution in reverse order of the two statements, should have been saved in (assigned to) a variable, and returned.

Note that the variable, "sum", which is the main interest, is a parameter in the function definition. Do not confuse between parameter and argument. Parameter is what is in the header line of the function definition (called function), and argument is the actual value that is sent in the calling function expression.

The first input value for i, from the C main() function is 5, and not 0. sum input is 0 at this point. Notice that at the output, the value of 8 is not seen. It is of the base case. The base case is:

    if (no == 0)

        return 8;

Since the return type for the fn() function is int, the statement "return 8;" is just there for the sake of this return type. In fact, if "return 7;" is replaced with "return;", that is, return void, the user will just receive a warning message, and the program will still work. That is why 8 is not found at the output.

Returning Calling Function

When the calling function is returned in the returned statement, the body of the recursive function may modify some of the parameters and not modify others. Also, no statement below the principal returned statement are kept in memory for later execution in reverse order. The following program illustrates this for the same problem above:

    #include <stdio.h>

    #include 

    int arr[] = {0, 1, 2, 3, 4};
    int sum = 0;
    int i=0;
    int fn(int sum, int i) {
        if (i == 5)
            return sum;    //effective this time, since there is only forward direction
        i = i + 1;
        sum = sum + arr[i];
        printf("%i ", sum);
        return fn(sum, i);    //return calling function
            
        printf("%i ", sum);    //not stored in memory and not executed, i.e. ignored
        return sum;    //not stored in memory and not executed, i.e. ignored
    }
    int main(int argc, char *argv[])
    {
        int total = fn(sum, i);
        printf("\n");
        printf("%i\n", total);

        return 0;
    }

The output is:

1 3 6 10 10

10

as expected

Read through the code.

Since the statements after the return function statement, "return fn(sum, i);" and before the end of the function definition are not executed, the i input from the C main() function is 0 and not 5. sum input is 0 at this point. "i = i - 1;" was changed to "i = i + 1;" . The base case was changed from

        if (i == 0)
            return 8;
to
        if (i == 5)
            return sum;

Since the vary last return statement is ignored, the return statement of the base case has to have a useful return integer value, as the function must return an int. sum is returned, and it is the expected (final sum) value.

The fn() function should return an int. This is achieved by the base case return statement:

return sum;

and not by the very last recursive (recalling) return statement at the end of the function definition, that is ignored in this situation.

The return fn(sum, i) statement is not to return an int. It is there to recall the function and to mark the end of the pass through the function body (mark end of an iteration).

Recursive Function for Factorial of a Whole Number

Example

      5! = 5 x 4 x 3 x 2 x 1 = 120
=>    5! = 120

5! (i.e 5 followed by !) is called 5 factorial. Notice that x1 (times 1) does not change the previous resulting product of x2.

By definition 0! = 1. So the above two mathematical statements can be written as:

      5! = 5 x 4 x 3 x 2 x 1 x 0! = 120
=>    5! = 120

So, 0! = 1, is the base case; that is, factorial(0) is the base case. Before continuing, accept that:

5! = 5 x 4! ; 4! = 4 x 3! ; 3! = 3 x 2! ; 2! = 2 x 1! ; 1! = 1 x 0! and 0! = 1 . As you can see, 0! = 1 is the base case. Though 1! = 1 and 0! =1, it is 0! that is considered as the base case.

The recursive nature is as follows:

    5! = 5 x 4!
    5! = 5 x (4 x 3!)
    5! = 5 x (4 x (3 x 2!))
    5! = 5 x (4 x (3 x (2 x 1!)))
    5! = 5 x (4 x (3 x (2 x (1 x 0!))))
    5! = 5 x (4 x (3 x (2 x (1 x (1)))))

Effective evaluation (calls in reverse order) has to begin from the innermost operation of (0! = 1).

While-loop

In the following program, the function, fn() is not a recursive function. It has a while-loop which shows that, what a recursive function can do, a while-loop can also do. The program is:

    #include 

    int fn(int no) {
        int factorial = no;
        while (no-1 > 0) {
            factorial = factorial * (no - 1);
            printf("%i ", factorial);
            no = no - 1;
        }
        return factorial;
    }
    int main(int argc, char *argv[])
    {
        int answer = fn(5);
        printf("\n");
        printf("%i\n", answer);

        return 0;
    }

The output is:

20 60 120 120

120

The first line here means: 5x4 20x3 60x2 120x1

Read through the code.

Note that the state of multiplication by 0! was not considered here. Certain problems like, finding the factorial of a number, are better coded as recursive functions and not with the while-loop, as the following 3 programs show.

Repeated Calling of Function until Condition is met

In the following program, the recursive function fn() with two parameters is called repeatedly until a condition is met. 1 is subtracted from no in each iteration, until the condition of no==1 is met.

    #include 

    int fn(int no, int factorial) {
        if (no == 1)
            return factorial;
        factorial = factorial * (no - 1);
        printf("%i ", factorial);
        no = no - 1;  
        fn(no, factorial);
    }
    int main(int argc, char *argv[])
    {
        int answer = fn(5, 5);
        printf("\n");
        printf("%i\n", answer);

        return 0;
    }

The output is:

20 60 120 120

120

The first line here means: 5x4 20x3 60x2 120x1

Read through the code.

Note that the state of multiplication by 0! has still not been considered here. It will be considered in the last example below. It is the condition with (no==1) that has been considered. Nothing was saved in memory(RAM) for execution in reverse order. This (saving) happens when some useful statements or the whole code, comes after the recalling function, in the function body.

Note that from the C main() function with fn(5, 5), the number, no whose factorial is required, is 5, and the starting factorial value is also 5.

Store some Code in Memory until Base Case is reached, then have Stored Code executed in Reverse Order

In the following code, the two statements, "printf("%i ", factorial);" and "return factorial;" between the recalling function call, fn(no, factorial) and the end of its function definition, are kept in memory (RAM) just after fn(no, factorial) is reached, for each iteration. They are executed in reverse order of iteration after the first 4 iterations (making 8 iterations altogether: 4 forward and 4 reverse).

    #include 

    int fn(int no, int factorial) {
        if (no == 1)
            return -1;
        factorial = factorial * (no - 1);
        no = no - 1;  
        fn(no, factorial);
        printf("%i ", factorial);
        return factorial;
    }
    int main(int argc, char *argv[])
    {
        int answer = fn(5, 5);
        printf("\n");
        printf("%i\n", answer);

        return 0;
    }

The output is:

120 120 60 20

20

Read through the code.

The first line of the output is as expected from reverse iterations; but the second line, though correct according to the algorithm, is not as expected, since 120 was expected. After the function has been called 4 times, the two particular statements are executed as a block, in reverse order. It is the very last return value of products, that the last return statement returns. So the second line of the output is correct from an internal programming point of view. In order to have obtained 120 as value for the last return statement, the last product value of all the numbers, before execution in reverse order of the two statements, should have been saved in (assigned to) a variable, and then returned.

Note that the variable, "factorial", which is the main interest, is a parameter in the function definition. Do not confuse between parameter and argument. Parameter is what is in the header line of the function definition (called function), and argument is the actual value that is sent in the calling function expression.

The first input value for no, from the C main() function is 5. factorial input is also 5. Notice that at the output, the value of -1 is not seen. It is of the base case. The base case is:

    if (no == 1)

        return -1;

Since the return type for the fn() function is int, the statement "return -1;" is just there for the sake of this return type. In fact, if "return -1;" is replaced with "return;", that is, return void, the user will just receive a warning message, and the program will still work. That is why -1 is not found at the output.

Returning Calling Function with Operation

When the calling function is returned in the returned statement, the values of the parameters to the function, are remembered for the next iterations. The calling function can be returned with an operation as in the following code. The body of the recursive function may modify some of the parameters and not modify others. Also, no statement below the returned statement are kept in memory for later execution in reverse order. The following program illustrates this for the same problem above:

    #include 
    
    int factorial(int number) {
        if (number == 0)
            return 1;    //else do next statement
        return number * factorial(number - 1);
    }
    int main(int argc, char *argv[])
    {
        int answer = factorial(5);
        printf("%i\n", answer);

        return 0;
    }

The output is:

120

Read through the code.

This is a good example of the situation, where all the function calls are saved in memory (RAM). When the base case is reached, reverse iterations start, and the final result is returned. The base case is:

    if (number == 0)

        return 1

This handles the situation of 0! (for the base case) . However, the 1 is not returned. It is the final result of the second (last) return statement which returns the calling function with operation (number *), that is returned. Here, the base case marks the beginning for reverse iterations to start.

Note that the function name here is factorial() and not fn().

The following listings show the forward iterations and the reverse iterations:

Forward Iterations

    5! = 5 x 4!
    5! = 5 x (4 x 3!)
    5! = 5 x (4 x (3 x 2!))
    5! = 5 x (4 x (3 x (2 x 1!)))
    5! = 5 x (4 x (3 x (2 x (1 x 0!))))
    5! = 5 x (4 x (3 x (2 x (1 x (1)))))

Reversed Iterations after Base Case is met

    (0!)       = 1
    (1 x (1))  = 1
    (2 x 1)    = 2
    (3 x 2)    = 6
    (4 x 6)    = 24
    5 x 24     = 120

The return value at the C main() function is 120 and not 1. The 1 at the base case must be 1, to account for 0! = 1 . If some other value is used in its place, the answer at the C main() function would be wrong.

Read through the above code again.

This very last example is the preferred way to code factorial.

It is good to also know that the forward iterations of the factorial function, can be written as:

    number * factorial(number * factorial(number * factorial(number * factorial(number * factorial(number - 1)))));

Which for this example is:

    5 * factorial(4 * factorial(3 * factorial(2 * factorial(1 * factorial(0)))));

And so the reverse iterations must be done from the innermost expression and go outwards.

Conclusion

A recursive function can be replaced by a while-loop. However, some problems like the factorial problem are best coded as recursive function.

A recursive function can be defined as a function that keeps calling itself repeatedly, until a specified condition is met. It can also be defined as a function that keeps calling itself; and for each call, some code of the function definition, or the whole function definition call, is stored in memory, until a base case is reached. Just after the base case is reached, the code that was stored in memory or the whole function definition call, is executed in reverse order, from the order that it was stored in memory.

When a recursive function returns its function call, that return statement recalls the function and marks the end of the evaluation (pass) through the function body. At the end of the function completion, it is the final value of that return statement that is returned, and not the value of the base case. The value of the base case is returned, when such a return statement does not have to return any value.

Chrys