Has Path Sum (binary tree)
June 11, 2012Basic Tree Traversals (Preorder, Inorder, Postorder)
June 11, 2012Understanding Recursion
What is recursion? What is head-recursion and tail-recursion? Should we use recursive or non-recursive functions?
Answer:
In programming, Recursion is way of designing an Algorithm where a function is defined in terms of itself. Typically the function performs some part of the task and rest is defined in terms of itself.
For example: Sum of first n numbers (n being positive) can be defined in terms of Sum of first (n-1) numbers as below.
Few points to note in the above recursion:
1. A recursion always have a terminating condition (else it will be infinite recursion).
In the above case the condition that if (n==1) then stop recursion and return 1.
2. The function performs some tasks and delegate some.
In the above example, the function performs the addition of n with the return value of the Sum(n-1)
but delegate the computation of Sum(n-1).
The function (in C language) for the above recursion will be (Not putting a check for n being non-positive)
or to write it in more compact form:
A Iterative version of the above recursion will be
As seen above a recursion can normally be mapped to a loop. So we have two versions a recursive version and an iterative version. Which one of the above do you think is better from a performance point of view?
Next Page : How recursions happens internally…
8 Comments
[…] I have written in my earlier posts also, Tree problems are better solved using recursion (But recursion comes with its side effect). Finding the Mirror can also be visualized […]
[…] function to reverse the linked list is recursive, but as I said earlier that recursion comes with its costs. so its always better to recursive functions because of time and space […]
[…] Note, that Recursion comes with its own cost. to learn more, see this post… […]
[…] is a classical example of both head recursion and tail recursion happening in the same function. You may also want to see my previous post on ‘Recursive […]
[…] printing the remainders in reverse order (Tail Recursion). 00 Read more from C, C++ Recursion Click here to cancel […]
[…] is an example of Head Recursion. In Head recursion the recursive function is called first and then perform the […]
Best explanation so far found on internet
thanks..