CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Dec 2022
    Posts
    1

    Javascript: Understanding Recursion

    Really confused with recursion. For eg: take problem of adding two numbers.
    the recursive function for it(I saw it somewhere) is either:

    sum(a+1,b-1) or sum(a+b-1)+1. You can use any of them for positive numbers. Only the first one works for negative numbers. But I'm failing to understand the logic of how we got to this point? How to find the function?

  2. #2
    Join Date
    Feb 2017
    Posts
    677

    Re: Javascript: Understanding Recursion

    Quote Originally Posted by polaryeti View Post
    Really confused with recursion.
    A recursive call in isolation does not explain how the recursive function works. That requires, at least, that the termination criterion is also known. Here is my guess as to what the recursive function corresponding to your first recursive call may look like (in C),
    Code:
    int sum_(int a, int b) {
    	if (a == 0) return b;
    	if (b == 0) return a;
    	return sum_(a + 1, b - 1);
    }
    And here is the iterative counterpart,
    Code:
    int sum_(int a, int b) {
    	while (true) {
    		if (a == 0) return b;
    		if (b == 0) return a;
    		a = a+1;
    		b = b-1;
    	}
    }
    In this case, the transformation to iteration is easy because the recursive call is last in the function. It is called tail recursion, which allows the iterative version to operate without a stack. An optimizing compiler certainly would take this opportunity to produce faster code and, as a side-effect, prevent the stack overflow that would occur when both a and b are big. Stack overflow is a risk you must always consider when using recursion. When the recursive calls grow linearly with the input, as in this case, recursion seldom is a good idea.

    The above functions work by repeatedly incrementing a and decrementing b. When either a or b reaches zero, the other miraculously holds the sum of both. But there is a glitch. A call with a>0 and b<0 will result in an infinite loop because the termination criterion fails in that case. Thankfully there is a quick fix,
    Code:
    int sum(int a, int b) {
    	return (a<b) ? sum_(a,b) : sum_(b,a);
    }
    It resolves the issue by making sure sum_ is called with a<b. That is possible because a+b equals b+a. But it is unsatisfactory. It makes me believe there is a better solution. Maybe you could post a link to "I saw it somewhere."

    Your second recursive call seems wrong. It does not fit the sum(int a, int b) signature. So I leave that be.
    Last edited by wolle; December 17th, 2022 at 03:49 AM.

  3. #3
    Join Date
    Nov 2022
    Location
    Mohali, Punjab, India
    Posts
    1

    Re: Javascript: Understanding Recursion

    In the most basic terms, recursion is when a function keeps calling itself until it doesn't have to anymore.

    Think of recursion as a circuit race. It's like running the same track over and over but the laps are getting shorter each time. Eventually, you're going to run the last, shortest lap and the race will be over.

    Same with recursion: the function keeps calling itself with smaller inputs and eventually it stops.

    But the function itself doesn't decide when to stop. We tell it when to stop. We give a condition to the function which is known as base case.

    The base case is the condition that tells the function when to stop calling itself. It like telling the function what the last lap in the race will be so it stops running after that lap.

  4. #4
    Join Date
    Feb 2017
    Posts
    677

    Re: Javascript: Understanding Recursion

    Quote Originally Posted by ditinustechnology View Post
    In the most basic terms,
    Your reply is cut & pasted from the "What is recursion?" section here,

    https://www.freecodecamp.org/news/un...in-javascript/

    If you are not familiar with the concept of plagiarism, I suggest you check it out,

    https://en.wikipedia.org/wiki/Plagiarism
    Last edited by wolle; December 27th, 2022 at 04:03 AM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured