algorithm - Unable to understand Recursivly calling same method with two different input -


i have started getting hands on recursion. have gone through of online documents available, unable understand how recursion calls works when call same method different inputs.

just suppose, in case of tree have seen

return find(node.left) + find(node.right);

i unable understand how works.

in general recursion every call gets place in stack , when base condition reaches compute , return result. tried doing small program called same method tow different caller different index , if base condition reached, add both returned value.

if(n==0){         return arr[n];     }      else {         return calculatesum(arr, n-1) + arr[n];     }

the code works well. moved forward , tried this.

and giving me stack overflow. 

if(n==1){         return arr[n];     }      else {         return calculatesum(arr, n-1) + calculatesum(arr, n-2);     }

i unable understand how happening, missing out topic unable understand completely.

i have changes code on based of suggestion provided. unable understand flow. how n-2 funtioning. gave print. please find print , code below. 

private static int calculatesum(int[] arr, int n, string caller){      if(n<=1){         system.out.println(caller+" : "+n+ " : "+arr[n]);          return arr[n];     }      else {         return calculatesum(arr, n-1," minus one") + calculatesum(arr, n-2,"minus two");     }   }

prints :

minus 1 : 1 : 2

minus 2 : 0 : 1

minus 2 : 1 : 2

minus 1 : 1 : 2

minus 2 : 0 : 1

minus 1 : 1 : 2

minus 2 : 0 : 1

minus 2 : 1 : 2

sum of array :13

if can me understand how working . wondering how minus two value getting 0 in beginning , 1. , why minus one been called again after minus 2 when once has reached attained base condition.

note : have removed arr[n] return statement. so, want understand calling , how working.

your last version of program has number of problems, not least of element of array ever included in sum arr[1].

the reason stack overflow, however, is possible generate call calculatesum second argument 0 (for example, second recursive call when n==2), fail base-case test and, because subsequent recursive calls have smaller values n, never succeed.

the way have found helpful think recursion imagine else has written function solves problem "smaller" versions of problem (for example, sub-tree, or smaller value of n; whatever appropriate). write your function making use of one, making sure a) whenever call it, smaller version of problem, , b) if have small enough version of problem can solve without recursive call, don't make recursive call. (note that, if apply technique final bit of code, can see that, if recursive calls worked properly, you'd double-counting of array. , clear earlier version correct.)

here's magic: doing described above, have written function assumed else has written.


Comments

Post a Comment

Popular posts from this blog

PHP and MySQL WP -

i trying accomplish 2 things here code. writing php directly wp page using insert php plugin. 1) query mysql database , return results 1 column 4 columns. 2) make each result own hyperlink directs user new wp page runs new query on page. i able query show results , turn results dynamic hyperlink, cannot formatting down. right returns result 1 column. here have: [insert_php] $servername = "localhost"; $username = "login"; //edited privacy $password = "password"; //edited privacy $database = "database"; //edited privacy // create connection $conn = new mysqli($servername, $username, $password, $database); // check connection if ($conn->connect_error) { die("connection failed: " . $conn->connect_error); } echo "connected successfully"; //get results database $result = mysqli_query($conn,"select mine mines order mine"); $all_property = array(); //declare array saving property //showing proper...
Read more

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

go - golang pprof for c library code -

i have been trying profile golang application pprof, seems details of c code(linked static library) missed in output result. flame graph from frame graph can see c code time consuming reported within "runtime._externalcode", no details @ all. , sure static library compiled debug enable. so there way make pprof details(like stack trace) of 3rd party c code? or there other golang profiling tool this?
Read more