Recursion confusion: why does my function print the numbers in reverse order?
Zainab Malik@zainab_isb
Assalam o Alaikum all. I am a 2nd year CS student. I am having a confusion in recursion. Here is my code:
#include <stdio.h>
void print(int n) {
if (n == 0) return;
print(n - 1);
printf("%d ", n);
}
int main() {
print(5);
return 0;
}I expected 5 4 3 2 1 but it prints 1 2 3 4 5. When I move the printf above the recursive call, it prints 5 4 3 2 1. Why is the position of one line changing the whole order?
Our teacher said "it is because of the stack" but I am not understanding what that means. Kindly guide. Thank you in advance.
Accepted answer
Walaikum assalam Zainab. Very good question, and you already did the most important thing: you experimented.
Think of each call as a person who has to wait in a queue.
print(5) says: "first let print(4) finish, THEN I will print 5."
print(4) says: "first let print(3) finish, then I will print 4."
... all the way down to print(0), which just returns.
Now they finish in the reverse order of being called. print(1) is the first one whose wait is over, so it prints 1. Then print(2) finishes waiting and prints 2. And so on up to 5.
That waiting list is the call stack: the last call in is the first one out.
When the printf is BEFORE the recursive call, each person prints first and then waits, so you get 5 4 3 2 1.
Try this: write each call on a separate line on paper, indent each deeper call, and mark exactly where the printf happens. 10 minutes of this and recursion clicks.
Get the best of #rubber-duck-club weekly
One email each Monday with the most useful posts. No spam; unsubscribe in one click.
Comments
Sign in to join the conversation.
Sign in to commentAccepted answer
Kunal Bhatia@kunal_dsa
Walaikum assalam Zainab. Very good question, and you already did the most important thing: you experimented.
Think of each call as a person who has to wait in a queue.
print(5) says: "first let print(4) finish, THEN I will print 5."
print(4) says: "first let print(3) finish, then I will print 4."
... all the way down to print(0), which just returns.
Now they finish in the reverse order of being called. print(1) is the first one whose wait is over, so it prints 1. Then print(2) finishes waiting and prints 2. And so on up to 5.
That waiting list is the call stack: the last call in is the first one out.
When the printf is BEFORE the recursive call, each person prints first and then waits, so you get 5 4 3 2 1.
Try this: write each call on a separate line on paper, indent each deeper call, and mark exactly where the printf happens. 10 minutes of this and recursion clicks.
Zainab Malik@zainab_isb
Bhai this is so clear!! I did it on paper with the indentation and now I see why. JazakAllah, shukriya so much.
Harshit Gangwar@harshit_2005
omg i had the EXACT same dobut today in my recurssion lecture 😭 this explanation is so good. zainab thank u for asking
Mahin Hasan@mahin_cp
tip: add a depth parameter and print depth*2 spaces before each line, like printf("%*s", depth * 2, ""). you'll literally see the tree of calls. works for fib too
Ayesha Siddiqui@laravel_ayesha
Zainab, MashaAllah, asking with your code attached and saying what you already tried is exactly how good engineers ask. Keep going 💪
Lakshmi Prasad@lakshmi_teaches_py
I teach Python to school kids and I use the same "people waiting in a queue" picture. Kunal's explanation is perfect. Next, try printing both before AND after the call, you'll get 5 4 3 2 1 1 2 3 4 5 and it will make even more sense!
Nikhil Sharan@nikhil_twopointers
Beautiful question. Moving the printf to test your idea is the scientist's way. Most people only ask "why not working". Keep this habit.