I am currently studying recursion and wanted to understand how it loops itself and wants to know how it stops by itself. I am working on a project to use putchar using recursion and confused on how it works step by step and how it knows when to stop.
If you're willing, can you explain to me step by step what's going on in the code? If not, can you teach me how to do that in VS?
Here's the code of the recursion:
#include <stdio.h>
void printnumber(int number)
{
if (number < 0)
{
putchar('-');
number = -number;
}
if (number/10)
printnumber(number / 10);
putchar(number%10 '0');
}
int main()
{
int number;
//user input
printf("Insert an integer number: ");
scanf_s("%d", &number);
printnumber(number);
return 0;
}
CodePudding user response:
The first part of printnumber()
deals with number < 0
, and for the rest of function including the recursive call number >= 0
so let's split the last part into a separate function printposnumber()
:
void printposnumber(unsigned int number) {
if (number / 10) {
printposnumber(number / 10);
}
putchar(number % 10 '0');
}
void printnumber(int number) {
if (number < 0) {
putchar('-');
number = -number;
}
printposnumber(number);
}
Now let's rewrite the printposnumber()
, our only remaining recursive function, so it's more clear that there is a base case and a recursive case:
void printposnumber(unsigned int number) {
// base case
if (number < 10) {
putchar(number '0');
return;
}
// recursive case
printposnumber(number / 10);
putchar(number % 10 '0');
}
For printposnumber(1)
it's just like any like a regular non-recursive function call. The condition number < 10
is true so we run putchar(number '0');
and return to caller. number '0 converts a number between 0 and 9 to the corresponding ASCII character '0' and '9'. In this case this means we print '1'. Or said differently, our base case prints the first digit of a number.
For printpostnumber(12)
, the condition number < 10
is false, so we end up executing printposnumber(1)
which we know from above just prints '1'. Then remaining part is putchar(number % 10 '0');
which just prints the last digit of number as a string so in this case '2'. Or said differently our recursive case prints all but the first digit of a number.
This would be a great opportunity to familiarize yourself with a debugger. When a function is called, we push the argument onto to the stack followed by the return address. The combination of arguments and the the return address is called a stack frame. In our example, when we call printnumber(123)
we push the integer 123 on the stack, followed by the the address of the printnumber()
call in main()
and we call printnumber()
. Then we do it again, we push the unsigned integer 123 onto the stack, followed by the address of the call instruction now in printnumber()
etc. This is how the call stack looks like in gdb when we called the base case printposnumber(1)
:
#0 printposnumber (number=1) at 1.c:5
#1 0x0000555555555191 in printposnumber (number=12) at 1.c:11
#2 0x0000555555555191 in printposnumber (number=123) at 1.c:11
#3 0x00005555555551e9 in printnumber (number=123) at 1.c:20
#4 0x0000555555555227 in main () at 1.c:32
Notice how the return address 0x0000555555555191 is the same in stack frame #1 and #2? That's because we are returning to the same instruction printposnumber(number / 10);
in printposnumber()
. Also, note how the number=
changes on each stack frame particular #2 through #0 where we peel off the last digit before each call (with number / 10
).