I need a guidance to understand where my logic is not working. I need to write a recursive function that receives array A, and array B from a user input. The function is checking if the arrays are reversed. For example: A = {1, 4, 6, 7, 5, 3, 2}, B = {2, 3, 5, 7, 6, 4, 1} the function will return 1. If they are not reversed, the function will return 0. The size of the arrays is irrelevant as it's the same for both A and B. When I run my program, no matter what's the input, the result is 0, even if the input is correct(B is reversed of A).
int areReversed(int* A, int* B, int n)
{
if (n <= 0) return 1; // all elements have been compared and are equal
// Compare first element of array A and last element of array B
if (A[0] != B[n - 1])
return 0; // elements are not equal
// Recursively compare remaining elements of arrays A and B
return areReversed(A 1, B - 1, n - 2);
}
This is my code so far. Would love to know what's the reason the function returns 0 all the time and where my logic fails. On paper it should work from what I see.
I played around a bit, and changed the recursion call to (A 1, B, n - 1) Did a few tests and it appears to be working. Would love a second opinion on the change and see if it flawless or there's still some work to do. In the original code I decremented n too much so it skipped few elements of B, thus the comparison was wrong.
CodePudding user response：
The problem with this code is that you are passing the incorrect base of B and the wrong size.
In if (A[0] != B[n - 1]) you are comparing the first element of A with the last element of B (in reference to n being the length of the array).
So on the next iteration you have to advance A by one, but the base of B must remain as it is and the size must also decrease by one. So the correct call would be return areReversed(A 1, B, n - 1);.
If you do this:
#include <stdio.h>
int areReversed(int* A, int* B, int n)
{
if (n <= 0) return 1; // all elements have been compared and are equal
printf("checking %d and %d, n is %d\n", *A, B[n-1], n);
// Compare first element of array A and last element of array B
if (A[0] != B[n - 1])
return 0; // elements are not equal
// Recursively compare remaining elements of arrays A and B
return areReversed(A 1, B, n - 1);
}
int main()
{
int a[] = {1,2,3,4,5};
int b[] = {5,4,3,2,1};
printf("Palindrom? %d\n", areReversed(a,b, sizeof a / sizeof *a));
return 0;
}
then you get the right result:
$ ./a
checking 1 and 1, n is 5
checking 2 and 2, n is 4
checking 3 and 3, n is 3
checking 4 and 4, n is 2
checking 5 and 5, n is 1
Palindrom? 1
CodePudding user response：
Alright, so, we want to see whether array B is a reverse copy of A.
Here are two arrays:
A = 1 2 3 4 5
B = 5 4 3 2 1
Recursion works by doing something repeatable to reduce the problem to a simpler version. OP has a right idea (not the only right idea, but a valid one):
A = [1] 2 3 4 5 these are equal
B = 5 4 3 2 [1]
A = 1 2 3 4 [5] and these are equal
B = [5] 4 3 2 1
Since the first and last elements of both arrays are reversed, we can continue with the inner elements of each array:
A′ = 2 3 4
B′ = 4 3 2
Repeat until we run out of elements:
A″ = 3
B″ = 3
A‴ =
B‴ =
No more elements, return true.
Do it with code
As an argument to a function, an array is just given by a pointer. Very conveniently, we can just add one to the pointer value to get the next element, or, more to-the-point, a sub-array starting with the next element.
We also need to decrement the number elements in each array. How many elements come off of the array each time?
Notice that an array of a single element is a special condition: if we subtract 2 elements we wind-up with... -1.
Make sure that you check that n is greater-than zero (and definitely not less-than zero) before trying to compare first and last elements.
Remember, thinking a problem through, using paper and pencil (or a text editor), before writing any code — it is an invaluable exercise when programming. (Especially with tricky recursive stuff!)
CodePudding user response：
Suggestion: we don't need to modify the A and `B pointers at all in the recursion if we add an offset argument which increments up.
We also don't need to check the entire length of both arrays, but just halfway.
#include <stdio.h>
int areReversed(int* A, int* B, int n, int offset) {
if (offset > n / 2) return 1;
if (A[offset] == B[n - offset - 1] && A[n - offset - 1] == B[offset])
return areReversed(A, B, n, offset 1);
return 0;
}
int main(void) {
int A[] = {1, 2, 3, 4, 5};
int B[] = {5, 4, 3, 2, 1};
if (areReversed(A, B, 5, 0)) {
printf("They are mirrors of each other.\n");
}
return 0;
}
As a further note, consider that it's important to understand how recursion works, but unless your compiler is optimizing tail calls, with larger enough arrays you may encounter a stack overflow. This algorithm is readily adapted to a loop which runs in constant stack space.
int areReversed(int* A, int* B, int n) {
for (int offset = 0; offset < n / 2; offset )
if (A[offset] != B[n - offset - 1] || A[n - offset - 1] != B[offset])
return 0;
return 1;
}
CodePudding user response：
At least in my view, it's much cleaner and simpler if you make a choice up front: either deal entirely with pointers, or deal entirely with array subscripts.
But mixing the two as you are here, using subscripts off of moving pointers, is a recipe for code that's hard to get working, and hard to maintain in the long term.
If I were gong to do it, I'd use just pointers. For the moment, let's assume that you're required to use the function signature you did:
int areReversed(int* A, int* B, int n)
If so, I'd use this solely as a front-end for another function that presumes it's receiving a pointer to the beginning of A and the end of B:
int areReversed(int *A, int *B, int n) {
return areReversedImpl(A, B n-1, n);
}
That function would then implement something like:
- if n == 0, we're done--return true
- if *A != *B, we're done--return false
- otherwise (i.e., if *A equals *B) do a recursive call on (A 1, B-1, n-1)
Sorry, but no, I'm not going to completely write your homework for you though.