Recursion confusion: why does my function print the numbers in reverse order?
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…
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.