Skip to main content

Recursion and Tail Recursion


Consider a simple factorial function
Here is a simple Java implementation that uses recursion:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public void factorial(int n)
     {
       if (n <= 1)
         {
            return 1;
         }
        else {
               return n*factorial(n-1);
             }
     }

If you called factorial(5), this is how recursion evaluate.
factorial(5)
5 * factorial(4)
5 * (4 * factorial(3))
5 * (4 * (3 * factorial(2)))
5 * (4 * (3 * (2 * factorial(1))))
5 * (4 * (3 * (2 * 1)))
120
Note how every recursive call has to complete before the java interpreter begins to actually do the work .
Here's a tail-recursive version of function that add N Integers.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
public static int sum(int a,int b)
               {
                    if ( a == 0 )
                        {
                           return b;
                        }
                    else{
                           return sum(a-1,b+a);
                        }
               }

Here's the sequence of events that would occur if you called sum(5,0).
sum(5, 0)
sum(4, 5)
sum(3, 9)
sum(2, 12)
sum(1, 14)
sum(0, 15)
15
In the tail-recursive case, with each evaluation of the recursive call, the b is updated.

Comments

Popular posts from this blog

creating first go program

for creating go program open your editor and paste this code, and save it as filename.go for example helloworld.go

package main import "fmt" func main() { fmt.Println("Hello, 世界") }
I will explain these codes in details for now , we will look how to run these code.

to run type go run helloworld.go  in terminal , we get


you can try golang online as well , golang