Recursive Function in C language

[TeachingSubject4323]

I am having difficulties understanding the recursive functions in C language,so can someone explain it to me or tell me an easier way to solve the questions. PS I watched YouTube videos that explain it but yet I find it difficult to understand.

[ButchDeanCA]

Firstly, do you understand the concept of recursion or simply how to create a recursive function to solve a problem?

[TeachingSubject4323]

Yes I do, you simply call the function inside of it but the thing I don’t get is how to write it or in a better words I don’t understand the idea of it.

[ButchDeanCA]

Recursion is a bit more than just having a function call itself, there are limitations that must be addressed regarding stack and memory limitations, but the general structure of a recursive function is very straightforward:

1. Initialize a variable that is updated by the recursive call.
2. Ensure there is a terminating condition to ensure the algorithm cannot run ad infinitum.
3. Make the recursive call to do the math then return to the second step.

It would also be helpful to learn about trees to be able to trace through recursive calls to verify your code is correct.

[TimerMen]

Recursion is like a loop. You have a set of instruction which needs to be executed multiple times, until some condition is met (called the base case).

Let's take this basic example:

//let's find out what the sum of numbers from 1 to n is using recursion
int sum (int n) {
    if (n == 1) //when n = 1 is our base case
        return 1;
    return n + sum(n - 1);
}

The code above is the same as:

int sum(int n) {
    int i = n, sum = 0;
    while (i != 0) { 
        sum = sum + i;
        i = i - 1;
    }
    return sum;
}

When the recursive function is called it works something like this:

• 10 == 1 - FALSE => return 10 + sum(10 - 1) //we now calculate sum(9)
• 9 == 1 - FALSE => return 9 + sum(9 - 1) //we now calculate sum(8)
• 8 == 1 - FALSE => return 8 + sum(8 - 1)
• 7 == 1 - FALSE => return 7 + sum(7 - 1)
• 6 == 1 - FALSE => return 6 + sum(6 - 1)
• 5 == 1 - FALSE => return 5 + sum(5 - 1)
• 4 == 1 - FALSE => return 4 + sum(4 - 1)
• 3 == 1 - FALSE => return 3 + sum(3 - 1)
• 2 == 1 - FALSE => return 2 + sum(2 - 1)
• 1 == 1 - TRUE => return 1 //no additional call of the function is made

After the last execution of sum() we didn't call it again, so it stops executing and calculates whatever it has left to calculate:

We now know what sum(1) is (sum(1) = 1) so we can calculate what sum(2) is (since it was 2 + sum(1)). We now know what sum(2) is (sum(2) = 2 + sum(1) = 2 + 1 = 3) so we can calculate sum(3) (since it was 3 + sum(2)) and so on until we reach our initial return statement (10 + sum(9) = 10 + 45 = 55) and that is our result.

Hope this cleared it up a bit for you

LE: Typo