1

I'm currently reading "Practical C Programming 3rd Edition" by Steve Oualline.

Currently I'm on the Chapter 2 reading about Recursion, in this chapter the author proposes an exercise where the reader must try to write a recursive function that counts the number of times a number appears in an array.

Please consider the following code:

#include <stdio.h>

size_t count(const int [], size_t, int);

enum {ARRAY_LEN = 11};

int main()
{

    const int num_array[ARRAY_LEN] = {1, 2, 3, 4, 5, 5, 6, 7, 3, 9, 0};

    int number = 0;

    puts("Type a number: (0-9)");
    scanf("%d", &number);

    printf("Number of appearances: %lu\n", count(num_array, ARRAY_LEN, number));

    return 0;

}

size_t count(const int n_array[], size_t arr_len, int num)
{
    return arr_len == 0 ? 0 : ( n_array[arr_len - 1] == num ) + count( n_array, arr_len - 1, num );

}

My questions are:

How does C know which return to take back to the main function? Because, in this example we have 3 returns, and all of them in a certain time their conditions become true, so, how does C know that with a return 0; it must exit the recursive function and not continue in search for another return inside the count() function?

Thanks.

Improve this question
7
  • return simply returns to the place from where the function has been called, there is no magic. Commented Jun 15, 2021 at 17:15
  • Each function call ultimately executes a single return. If the function calls itself recursively, then that call will return at some point, control will return to the caller, and the caller will return. The two calls do not need to execute the same return. Each call is independent of the others. Commented Jun 15, 2021 at 17:15
  • 1
    The statements are executed sequentially. If any return is taken conditionally, the function stops executing at that point and any other return isn't considered. The first one if(arr_len == 0) return 0; ends the recursion, the other two determine which recursive path to take. Commented Jun 15, 2021 at 17:15
  • For a single frame, the control flow that leads to return 0; doesn't involve a call to count, whereas the other branches do. That makes it the base case rather than a recursive case. Commented Jun 15, 2021 at 17:16
  • But if the last return, returns a 0, how is that the count() function still returns the counts of appearances? At the end, only returns what the final return sends back to main right? That in this case would be a zero Commented Jun 15, 2021 at 17:23

4 Answers 4

Reset to default
2

When you have recursive function calls, you have multiple "instances" of a function active, calling and returning to each other. To visualize this, I find it useful to imagine that, instead of a C program running on a computer, you have a bunch of people in a room, and you all give them an identical set of instructions, and then you ask them to start solving a problem for you. For the code in your question it would go something like this.

You pick a person and say, "Hey, John, here's an array of size 3: [1, 2, 3]. Can you tell me how many times the number 2 appears in it?"

John takes the array from you, and he looks at his instructions. The array is not of size 0, so he doesn't tell you 0. The last element of his array is not 2, so he doesn't do the second thing, either. But to do the third thing, he needs to make a recursive call, so he picks someone else in the room and he says, "Hey, Mary, here's an array of size 2: [1, 2]. Can you tell me how many times the number 2 appears in it?"

Mary takes the array from John, and she looks at her instructions. The array is not of size 0, so she doesn't tell John 0. But the last element of her array is 2, so she does do the second thing. But to do the second thing, she also needs to make a recursive call, so she picks someone else in the room and she says, "Hey, Fred, here's an array of size 1: [1]. Can you tell me how many times the number 2 appears in it?"

Fred looks at his instructions. The array is not of size 0, so he doesn't tell Mary 0. The last element of his array is not 2, so he doesn't do the second thing. He, too, needs to make a recursive call to do the third thing, so he picks someone else in the room and says, "Hey, Jane, here's an array of size 0: []. Can you tell me how many times the number 2 appears in it?"

Jane looks at her array, and the size is 0. So she says, "Fred, the number of times that 2 appears in that array is: 0".

That's what Fred was waiting for. Fred was working on the third return statement, so whatever he hears from Jane is his answer, too. He says, "Mary, the number of times that 2 appears in that array is: 0".

That's what Mary was waiting for. But she was working on the second return statement, so she adds 1 to whatever she hears from Fred. She says, "John, the number of times that 2 appears in that array is: 1".

That's what John was waiting for. John was working on the third return statement, so whatever he hears from Mary is his answer, too. He says to you, "The number of times that 2 appears in that array is: 1".

And now you have your answer!

I used to teach a C programming class, and one day I gave everyone in the class a handout which was some human-readable instructions on how to do a recursive, in-order traversal of a binary tree. Then I handed a "binary tree" -- a piece of cardboard with a bunch of yellow stickies arranged on it in a tree-like structure -- to a random student in the front row, to start traversing. It was absolute pandemonium, but also great fun. (I think. I thought it was fun, anyway!)

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks Steve, this answer helped me to understand what was happening from a more human-readable context. And that story of teaching how a recursive binary tree work using stickies sounds amazing haha, a really good way to teach it
1

CPUs have a stack. This is a very important data structure, which describes execution context. A stack may look like this:

count(4, {10, 20, 30}, 3)
count(4, {10, 99, 33, 22}, 4)
count(4, {10, 99, 33, 22, 44}, 5)
main(1)

When a CPU calls a function, it adds another stack frame on top (actually, some people or debuggers visualize it upside-down, so it may be at the bottom).

When a CPU returns from a function, it removes a stack frame from the top, and continues from an execution point which is now at the top.

If you visualize this stack, you will see that each return statement doesn't have any definite destination - it's the stack which tells CPU where to continue execution. If main calls count, it returns to main, but if count calls count, it returns to count. But not only that - it remembers which invocation to return to.

A stack frame contains a copy of all the parameters with which a function was called, and a copy of the function's local variables (it's not always a copy, but the simplest and most important case is when it's really a copy).

Improve this answer

1 Comment

Thanks, viewing the code from the perspective of the stack, really helped me to understand whats was happening, really appreciate the help
1

For starters the function definition with multiple return statements is bad.

Moreover the function should be declared like

size_t count( const int [], size_t, int );

The function can be defined the following way

size_t count( const int a[], size_t n, int num )
{
    return n == 0 ? 0 : ( a[n-1] == num ) + count( a, n - 1, num );
}

That is the return type of the function shall be size_t. The first parameter of the function shall have the qualifier const because the array passed to the function is not changed within the function.

And in main you should write

printf( "Number of appearances: %zu\n", count( num_array, ARRAY_LEN, number ) );

As for your question then it is clear that the control within the function will be passed to a return statement dependent on used conditions in the if statements.

if the value of arr_len is equal to 0 then the control will be passed to the return statement inside this if statement.

if(arr_len == 0)
    return 0;

Pay attention to that in each recursive call of the function the value of the parameter arr_len is decremented.

So it is the base case of the function when arr_len is equal to 0. In this case the function stops its execution.

Otherwise if arr_len is not equal to 0 then if the last element of the array is equal to num then 1 is added the value returned by the next recursive call and the sum is returned. Otherwise if the last element of the array is not equal to num then the value returned by the next recursive call of the function is returned.

if(n_array[arr_len - 1] == num)
    return (1 + count(num, n_array, arr_len - 1));
else
    return count(num, n_array, arr_len -1);
Improve this answer

4 Comments

the function definition with multiple return statements is bad That's an opinion, it's not a fact. Plenty of programmers believe that multiple return statements are fine.
@SteveSummit It is an opinion but one I share. Multiple returns are mostly for "early escapes". For: int fnc(void) { if (early_escape_1) return 1; if (early_escape_2) return 2; return do_stuff(); }, personally, I use a do/while/0 instead: int fnc(void) { int ret; do { if (early_escape_1) { ret = 1; break; } if (early_escape_2) { ret = 2; break; } ret = do_stuff(); } while (0); if (debug) printf("fnc: ret=%d\n",ret); return ret; } It allows a single breakpoint on the only return and, as in here, it's easy to add debug printf -- YMMV
@CraigEstey I meant the concrete code in the question. Actually there is a duplicated code of calling the function. So this if-else statement can confuse readers of the code because the idea is simple: if arr_len is equal to 0 then just exit with 0 otherwise call the function again. However in the function there are two if statements and one else.
Thanks @VladfromMoscow, as a beginner I didn't noticed some of the duplicated code or the misunderstanding of the data types(int and size_t), but your answers really helped
0

This is what recursive programming is all about.

The code uses the first return it encounters in the if chain. If that return recursively calls "count" then that return is put on hold until the nested "count" call returns. This continues until everything has returned on arr_len == 0.

Improve this answer

2 Comments

So C in this case, would be creating 3 temporary return variables? The first with a value of zero, the second one with the increments of count and the third one with the count( , , arr_len - 1) ?
No, as anatolyg mentioned each call to a function call gets it's own "stack frame" with it's own independent variables. Recursive functions create an arbitrary number of stack frames until the first call works down to returning, which takes more space than making mere extra variables. For simple programs this use of memory and time is not an issue. There is a whole science behind writing acceptable recursion and this is your introduction to it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.