I'm learning recursion , so i'm trying to create a program that reverse a number in array recursively and using divide and conquer technique (i'm not sure this is divide and conquer or not), so what my problem is, i want to know why if i delete line 11 the program still work properly, but if i delete line 16, it will goes infinitely.
And i checked through my debugger, i know why it's infinite loop, because each stacked frames index left is still less than right, this makes the loop goes infinitely, so my question, why recursive call start from check the while condition and skip the line 11? this is weird for me because i just learn some basics of recursive, so this is abit confusing for me. so in my code, the line 16 is considered as the base case? because i learn from tutorial that recursive need a base case.
#include <stdio.h>
#define size 10
void swap(int *a, int *b)
{
int temp= *b;
*b = *a;
*a = temp;
}
void revcur (int arr[], int left, int right)
{
if (left>=right) return; //This program still works even if i delete this line or comment
while (left<right)
{
swap(&arr[left],&arr[right]);
revcur(arr,left+1,right-1);
return; //This program will go to infinite recursive if i delete this
}
}
int main()
{
int arr[size]={1,2,3,4,5,6,7,8,9,10};
revcur(arr,0,size-1);
int i; for (i=0; i<size; i++)
{
printf("%d ",arr[i]);
}
}
Suppose left=2 and right=1. What happens if you leave line 11 in, the condition will be true, and you will exit the function (return) immediately. When you remove line 11, you will get to the while loop. The while statement checks if left is less than right, which it is not. Therefore, it will skip all the code inside the while loop which brings you to the end of the function, and hence it will return automatically. This is identical behaviour to the case where you leave line 11 in place.
The reason it loops infinitely when you remove line 16 is because you are not updating "left" and "right" to a new value. So if left is indeed less than right, it will enter the loop and since the value of left and right never change, the next time it gets to the line with the "while" statement, "left" will still be less than "right" and hence the loop will continue indefinitely.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With