Thread: Recursion recursion recursion

I suck horribly with recursion and have never really needed to use it. I am struggling with this probably trivial issue and my brain has hit a brick wall despite having read and even watched several vids about it. What I'm thinking will happen is when someone on here corrects this error, it will "click" because I'll be able to have struggled thru an issue and now see what I was doing wrong:

Code:

#include <stdio.h>
#include <stdlib.h>

int multiply(int arr[], int size)
{
    int answer;
    if(size <= 1)
        answer = 0;
    else
        answer = arr[size-1] * multiply(arr, size-1);
    return answer;
}

int main()
{
    int myArray[] = {5,4,3,2,1};
    printf("The answer is: %d", multiply(myArray, 5));
    return EXIT_SUCCESS;    
}

I'm coming up with 0 here when the program is run. A couple other things I've tried: I changed the base case from answer = 0 to simply return 0, changed the base case from answer = 0 to answer = 1, and also changed the arr[size] to arr[size-1] as shown.

A couple of things I'm pondering: Am I going to low in the array (-1 somehow) and getting a 0 that way? Or perhaps since I set answer = 0, at some point, answer will always be 0. However, when I change it to answer = 1 instead, the correct answer still does not come out, instead I get a 24.

The answer should be 120. Thanks for your help. Gonna be in gdb trying to see if I can figure it out too.

Change your base case to be

If size is 0, return 0
Else if size is 1 return arr [0]

You're just multiplying by 0 all the time.

Originally Posted by Salem

Change your base case to be

If size is 0, return 0
Else if size is 1 return arr [0]

You're just multiplying by 0 all the time.

Salem,
So this worked just as you said:

Code:

int multiply(int arr[], int size)
{
    int answer;
    if(size == 0)
        answer = 0;
    else if(size == 1)
        answer = arr[0];
    else
        answer = arr[size-1] * multiply(arr, size-1);
    return answer;
}

So would you say that my problem was that I didn't cover enough base cases? It looks to me like the way I originally had it, I wasn't covering the size == 1 base case properly such that when size hit 1, it would multiply the whole thing by 0? I'm just trying to figure out how to attack these types of problems in the future. It seems recursion requires more if statements than iterative in which the if can be implicit inside the loop condition.

Edit: Also, I noticed since we're using if/else that the recursive process should never allow it to get to size 0 since we're specifying that when it == 1, it returns arr[0] and then exits the recursive process rather than returning that and continuing to reduce the size. Thus, the size == 0 check is mainly for an original size of 0.

Pretty much.

An array size of 0 could be an error condition, so returning 0 is as good as anything.

The trick to writing recursive functions is to make sure you know what your base cases are.
- for arrays, it's usually when you've reduced it to an array with 1 element.
- for pointers, it's usually when you reach NULL (such as traversing lists, trees).
- for numbers, it's usually when you reach 0 or 1 (say factorial).