I was trying a random program to practice recursion.
I am unable to figure out what is happening
int fun(int *list,int l,int h) { if(l==h) return list[l]; int b = fun(list,l+1,h)+ fun(list,l,h-1); printf("%d \n",b); return b; } void main() { int ar[]= { 1,2,3,4}; fun(ar,0,3); } Could someone draw recursion tree maybe? Also what is the value of b at each point? Thanks!
A slight retool of your app will likely tell you exactly what you want to see. Modifying your algorithm to include a depth-parameter and some creative lead-space printing with an argument-specified left-justificaction gives us this:
#include <stdio.h> #include <stdlib.h> int fun(int *list, int l, int h, int d) { printf("%*sfunc(list, %d, %d)\n", d, "", l, h); int b = (l==h) ? list[l] : fun(list, l+1, h, d+2)+ fun(list, l, h-1, d+2); printf("%*sresult: %d \n", d, "", b); return b; } int main() { int ar[]= { 1,2,3,4}; fun(ar, 0, 3, 0); return EXIT_SUCCESS; } The results somewhat speak for themselves:
Output
func(list, 0, 3) func(list, 1, 3) func(list, 2, 3) func(list, 3, 3) result: 4 func(list, 2, 2) result: 3 result: 7 func(list, 1, 2) func(list, 2, 2) result: 3 func(list, 1, 1) result: 2 result: 5 result: 12 func(list, 0, 2) func(list, 1, 2) func(list, 2, 2) result: 3 func(list, 1, 1) result: 2 result: 5 func(list, 0, 1) func(list, 1, 1) result: 2 func(list, 0, 0) result: 1 result: 3 result: 8 result: 20 With a few modifications (not shown here; left as an exercise for the reader), you can draw the terminal-dependent line art chars to amplify even more the "what called what and returned what?" question. The following was the output of such a mod using VT100 compliant escape sequences (which SO thankfully consumes nicely in their formatting). Enjoy!
┌func(list, 0, 3) │ ┌func(list, 1, 3) │ │ ┌func(list, 2, 3) │ │ │ ┌func(list, 3, 3) │ │ │ └result: 4 │ │ │ ┌func(list, 2, 2) │ │ │ └result: 3 │ │ └result: 7 │ │ ┌func(list, 1, 2) │ │ │ ┌func(list, 2, 2) │ │ │ └result: 3 │ │ │ ┌func(list, 1, 1) │ │ │ └result: 2 │ │ └result: 5 │ └result: 12 │ ┌func(list, 0, 2) │ │ ┌func(list, 1, 2) │ │ │ ┌func(list, 2, 2) │ │ │ └result: 3 │ │ │ ┌func(list, 1, 1) │ │ │ └result: 2 │ │ └result: 5 │ │ ┌func(list, 0, 1) │ │ │ ┌func(list, 1, 1) │ │ │ └result: 2 │ │ │ ┌func(list, 0, 0) │ │ │ └result: 1 │ │ └result: 3 │ └result: 8 └result: 20 
"%*s". Nice :)
I guess it should be something like this (not very tree-ish though, just didn't know how else to draw it):
fun(ar, 0, 3) -> { (prints 20) fun(ar, 1, 3) -> { (prints 12) fun(ar, 2, 3) -> { (prints 7) fun(ar, 3, 3) + fun(ar, 2, 2) } + fun(ar, 1, 2) -> { (prints 5) fun(ar, 2, 2) + fun(ar, 1, 1) } + fun(ar, 0, 2) -> { (prints 8) fun(ar, 1, 2) -> { (prints 5) fun(ar, 2, 2) + fun(ar, 1, 1) } + fun(ar, 0, 1) -> { (prints 3) fun(ar, 1, 1) + fun(ar, 0, 0) } } } 
1 fun(list,0,3) 2 = fun(list,1,3) + fun(list,0,2) 3 = fun(list,2,3) + fun(list,1,2) + fun(list,1,2) + fun(list,0,1) 4 = fun(list,2,2) + fun(list,3,3) + fun(list,1,1) + fun(list,2,2) + fun(list,1,1) + fun(list,2,2) + fun(list,0,0) + fun(list,1,1) 4th line does not have any printf statements.
3rd line will print
7 5 5 3 2nd line will print
12 8 1st line will print
20 
bwill be undefined sincefundoesn't actually return anything.fundoesn't return anint?