Recursion with C++

Question

I am learning recursion in my current class and the idea is a little tricky for me. From my understanding, when we build a function it will run as many times until our "base case" is satisfied. What I am wondering is how this looks and is returned on the stack. For an example I wrote the following function for a simple program to count how many times a digit shows up in an integer.

What does this look and work in a stack frame view? I don't completely understand how the returning works. I appreciate the help!

int count_digits(int n, int digit) {
  // Base case: When n is a single digit.
  if (n / 10 == 0) {
    // Check if n is the same as the digit.
    // When recursion hits the base case it will end the recursion.
    if (n == digit) {
      return 1;
    } else {
      return 0;
    }
  } else {
    if (n % 10 == digit) {
      return (1 + count_digits(n / 10, digit));
    } else {
      return (count_digits(n / 10, digit));
    }
  }
}

At this point you probably shouldn't be worrying about the low-level implementation details like stack frames. Just know that a recursive function call works exactly like any other function call. When the call returns, you end up right back where you made the call from, with all local variables exactly how you left them. — Miles Budnek, Apr 05 '20 at 00:23
With the local variables, say I have int count = 0; Every time the recursion happens this local variable count will be zero each time it is used? — , Apr 05 '20 at 00:27
Yes. Every function call is totally independent (aside from `static` variables, but don't worry too much about those right now). A function has no knowledge of any previous calls to itself. — Miles Budnek, Apr 05 '20 at 00:35
Try doing something even more simple than counting digits (since there are a number of things you need to understand for that, beyond recursion). Such as calculating the factorial. 'unsigned factorial(unsigned n) {if (n == 0) return 1u; else return n*factorial(n-1);}` which will calculate the factorial for values up to `12` without overflow (assuming a 32--bit `unsigned`) — Peter, Apr 05 '20 at 00:43

score 0 · Accepted Answer · answered Apr 05 '20 at 07:18

What does this look and work in a stack frame view? I don't completely understand how the returning works. I appreciate the help!

Let's try to build the solution bottom-up.

If you called the function - int count_digits(int n, int digit) as count_digits(4, 4) what would happen ?

This is the base case of your solution so it is very easy to see what is the return value. Your function would return 1.

Now, let's add one more digit and call the function like- count_digits(42, 4). What would happen ?

Your function will check the last digit which is 2 and compare with 4 since they are not equal so it will call the function count_digits(4, 4) and whatever is the returned value, will be returned as the result of count_digits(42, 4).

Now, let's add one more digit and call the function like - count_digits(424, 4). What would happen ?

Your function will check the last digit which is 4 and compare with 4 since they are equal so it will call the function count_digits(42, 4) and whatever is the returned value, will be returned by adding 1 to it. Since, number of 4s in 424 is 1 + number of 4s in 42. The result of count_digits(42,4) will be calculated exactly like it was done previously.

The recursive function builds up the solution in a top-down manner. If there are n digits initially, then your answer is (0 or 1 depending on the last digit) + answer with n-1 digits. And this process repeats recursively. So, your recursive code, reduces the problems by one digit at a time and it depends on the result of the immediate sub-problem.

You can use the C++ tutor at pythontutor.com website for step by step visualization of the stack frame. http://pythontutor.com/cpp.html#mode=edit

You can also try with smaller inputs and add some debug output to help you track and see how recursion works.

Check this stackoverflow answer for understanding what a stack frame is - Explain the concept of a stack frame in a nutshell

Check this stackoverflow answer for understanding recursion - Understanding recursion

If you would like more help, please let me know in comments.

Recursion with C++

1 Answers1