0

I'm writing a program calculating the summary of all elements before x element recursively. It always returns 0. Please could you help me- and can you explain how it works orderly when I call the SumBeforeX function in main?. Here's my code and

#include <stdio.h>
int SumBeforeX(int a[], int n, int x)
{
    int i = 0;
    static int s = 0;
    if (n == 0)
        return 0;
    if (a[i] == x)
        s+=SumBeforeX(a, i -1, x) +a[i-1];
    return s;

}
void main()
{
    int a[] = {2,6,13,17,47,8};
    printf("%d",SumBeforeX(a,6,13));
    _getch();
}
AStopher
  • 4,207
  • 11
  • 50
  • 75
F.Wu
  • 55
  • 5
  • regardless of what some compilers will allow, all valid signatures for `main()` have a return type of `int` – user3629249 Apr 27 '18 at 12:52
  • @user3629249 can you explain it clearly? when the function return s, its already a type of int. – F.Wu Apr 27 '18 at 12:55
  • 1
    I suggest you take some time to [learn debugging in general](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/), and more specifically how to use a debugger to step through your code line by line. – Some programmer dude Apr 27 '18 at 12:56
  • A debugger ist the best way to see the execution order of your code. – Gerhardh Apr 27 '18 at 12:56
  • 1
    i-1 is equal to - 1 – kingW3 Apr 27 '18 at 12:57
  • 1
    You need to rethink how you use `n` and `i`. They should be connected somehow. – Gerhardh Apr 27 '18 at 12:57
  • If you use same array start and reduce length in each recursion cycle, you will not search in the first part of the array. You should pass something like `(a+1, n-1, x)` to the next level of recursion. – Gerhardh Apr 27 '18 at 12:59
  • 1
    A `static` in a recursive call kind of defeats the concept. Also makes it a *one-time-use function* in your case. –  Apr 27 '18 at 13:00
  • [Regarding return type of main() in C](https://stackoverflow.com/questions/12146594/definition-of-main-in-c) – Tormund Giantsbane Apr 27 '18 at 13:03
  • @F.Wu, My comment is not about the return value of the sub function, rather my comment is about this statement: `void main()` – user3629249 Apr 27 '18 at 13:21

3 Answers3

2

The answer given by user3629249 already explained why SumBeforeX() always returning 0 and the Felix Palmen answer talks about recursive and non-recursive ways of solving the problem. This answer is just to give you an idea about calculating the sum before "x" element using tail recursion:

int SumBeforeX(const int *a, int n, int x, int sum)
{
    if (n == 0) return 0;
    if (x == *a) return sum;

    return SumBeforeX(a + 1, n - 1, x, sum + *a);
}

Here you can see I have added one more parameter sum to the function SumBeforeX and accumulating the sum of elements into it. You can call it like this:

printf("%d\n", SumBeforeX(a, 6, 13, 0));

Seems that you are learning the recursion, its good to get familiar with tail recursion as well.

A function call is said to be tail recursive if there is nothing to do after the function returns except return its value. A tail recursive function can be easily transformed into an iterative one and hence compilers can also optimize the code for such functions by eliminating the recursion, that means, tail recursive calls run in constant stack space, i.e. they don't need to create new stack frames when they recursively call themselves. Check following for better idea:
1) Tail Recursion
2) How exactly does tail recursion work?

H.S.
  • 11,654
  • 2
  • 15
  • 32
  • 1
    This makes the function defined even if `x` isn't an element of `a[]`. Might be a good thing, but I'm quite unsure if this was the intention of OPs original code ;) –  Apr 27 '18 at 14:38
  • btw, althogh I'm unsure it's a good idea to open up this can here, if you do, I think a technical explanation **why** tail recursion could be preferable would be nice as well. It kind of boils down to help the compiler eliminate the recursion as you don't want it in the generated machine code... –  Apr 27 '18 at 14:48
  • 1
    @FelixPalmen: I agree with you but I look it into this way - OP's code passing number of elements in the array as an argument to the recursive function and also doing some check on it as well, so I believe, OP wanted to do some validation on the number of elements of the array. Thanks, as you have suggested I have added a brief about tail recursion and a couple of references to refer. May that would help. – H.S. Apr 27 '18 at 16:15
  • it gives the necessary context! As for this `n` parameter, I was under the impression OP attempted to use it for the terminating condition, having seen similar examples without really understanding them. But of course your interpretation could be correct as well -- we can't know for sure from the code posted –  Apr 27 '18 at 16:30
0

I guess the expected solution looks somewhat like this:

int sumBeforeX(const int *a, int x)
{
    if (x == *a) return 0;           // termination condition
    return *a + sumBeforeX(a+1, x);  // recursive step
}

To understand that, note that arrays can't be passed in C, therefore their type in a function parameter is adjusted to the corresponding pointer type, and a pointer to the first element is passed instead. I made this explicit in the snippet above, directly writing the pointer type.

The const is just a little improvement: the function never modifies your array through this pointer, so make this explicit as well.

Also note how this implementation never assigns anything. This is a typical property of functional programming, and recursion is especially used with functional programming. The function call is free of side effects.

Side note: don't write this recursively in real-world C code, if you're lucky, the compiler optimizes the recursion away (in this simple case, a good compiler should do it), but that shouldn't be relied upon, and if the recursion stays, performance will typically suffer and you might get the risk of stack overflows if your recursion gets really deep. Therefore, just for completeness, the real-world code should look more like this:

int sumBeforeX(const int *a, int x)
{
    int sum = 0;                  // accumulator to replace recursion
    while (*a != x) sum += *a++;
    return sum;
}
  • i think if (x==*a) , it must return a[0]. Can you explain how it works when i call the function? – F.Wu Apr 27 '18 at 13:12
  • @user3121023 this wasn't part of the specification, so I don't think so ... looks more like `n` should be a current index in the array, which really isn't needed. The contract of this function requires that `x` is actually a member of `a` (just like the contract of `puts()` requires the argument to end with a `0` byte) –  Apr 27 '18 at 13:15
  • @F.Wu if you would return `a[0]` (or simply `*a` which is the same) there, you would sum up all elements **including** `x`. According to your question, this is not what you wanted? –  Apr 27 '18 at 13:16
  • @user3121023 sure, but does it make any sense according to the spec in the text? I'd say no, it's just a confused attempt to do something similar to other recursive functions OP might have seen. –  Apr 27 '18 at 13:19
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/169950/discussion-between-felix-palmen-and-stargateur). –  Apr 27 '18 at 14:04
0

regarding: And can you explain how it works orderly when i call the SumBeforeX function in main?

#include <stdio.h>
int SumBeforeX(int a[], int n, int x)
{
    int i = 0;
    static int s = 0;
    if (n == 0)
        return 0;
    if (a[i] == x)
        s+=SumBeforeX(a, i -1, x) +a[i-1];
    return s;

}
void main()
{
    int a[] = {2,6,13,17,47,8};
    printf("%d",SumBeforeX(a,6,13));
    _getch();
}

on the first execution of SumBeforex()

  1. the value of n is 6 so no early exit
  2. the value of s is 0
  3. the value of i is 0 so the value of a[i] is 2
  4. value of x is 13
  5. so the `if( a[i] == x ) is false
  6. therefore, no recursion ever occurs
  7. so 0 is returned to 'main()`
  8. so the printed value is 0
user3629249
  • 16,402
  • 1
  • 16
  • 17