CODEWITHSUNDEEP
c++recursioninputstack-overflow
esra
esra

Reputation: 201

My recursion does not work if I change the function input?

My recursive function stops execution and does not work at all. But if I change the input formula of the recursion, then it works perfectly fine. Can someone tell me where am I doing wrong?

I mean, if I use n/2 instead of (n+1)/2 and (n-1)/2 in the recursion formula then it works. More clearly if I use;

return 2*f(n/2)+f(n/2)+7*n-7

instead of

return 2*f((n+1)/2)+f((n-1)/2)+7*n-7

then it works, otherwise, it stops the execution. Why does this happen?

#include<stdlib.h>
#include<bits/stdc++.h> 
using namespace std; 

int f(int n) 
{ 

    if (n == 1) 
        return 2; 
    return 2*f((n+1)/2)+f((n-1)/2)+7*n-7; 

} 

   int main () 

{      int n;
       cout<< " enter odd integer n value "<<"\n";
       cin>> n;
       cout<< "Total Cost is: "<< f(n)<<"\n";
       getchar(); 
       return 0; 
}

Upvotes: 0

Views: 81

Answers (1)

Ryan Shaffer
Ryan Shaffer

Reputation: 405

Consider what is happening when n=3.

First you call f(3), which in turn will call f(2) and f(1).

Then f(2) calls f(1) and f(0).

f(1) works correctly because of your base case, but f(0) goes on to call f(0) and f(-1). And so your recursion goes on forever.

The correct fix depends on what the function is supposed to be doing, but one possibility you could consider is making the base case n <= 1 instead of n == 1.

Upvotes: 1

Related Questions