How does that recursive function work?
Pasha
Might be a very basic question but I just got stuck with it. I am trying to run the following recursive function:
//If a is 0 then return b, if b is 0 then return a,
//otherwise return myRec(a/2, 2*b) + myRec(2*a, b/2)
but it just gets stuck in infinite loop. Can anybody help me to run that code and explain how exactly that function works? I built various recursive functions with no problems but this one just drilled a hole in my head. Thanks.
Here is what I tried to do:
#include<iostream>
int myRec(int a, int b){
if (a==0){
return b;
}
if (b==0){
return a;
}
else return myRec(a/2, 2*b) + myRec(2*a, b/2);
}
int main()
{
if (46 == myRec(100, 100)) {
std::cout << "It works!";
}
}
PatricK
I think you are missing on some case logic. I last program in C ages ago so correct my syntax if wrong. Assuming numbers less than 1 will be converted to zero automatically...
#include<iostream>
int myRec(int a, int b){
// Recurse only if both a and b are not zero
if (a!=0 && b!=0) {
return myRec(a/2, 2*b) + myRec(2*a, b/2);
}
// Otherwise check for any zero for a or b.
else {
if (a==0){
return b;
}
if (b==0){
return a;
}
}
}
UPDATE:
I have almost forgot how C works on return...
int myRec(int a, int b){
if (a==0){
return b;
}
if (b==0){
return a;
}
return myRec(a/2, 2*b) + myRec(2*a, b/2);
}
VBA equivalent with some changes for displaying variable states
Private Function myRec(a As Integer, b As Integer, s As String) As Integer
Debug.Print s & vbTab & a & vbTab & b
If a = 0 Then
myRec = b
End If
If b = 0 Then
myRec = a
End If
If a <> 0 And b <> 0 Then
myRec = myRec(a / 2, 2 * b, s & "L") + myRec(2 * a, b / 2, s & "R")
End If
End Function
Sub test()
Debug.Print myRec(100, 100, "T")
End Sub
Running the test in Excel gives this (a fraction of it as it overstacks Excel):
T: Top | L: Left branch in myRec | R: Right branch in myRec
The root cause will be the sum of the return which triggers more recursive calls.
Repeating of the original values of a and b on each branch from level 2 of the recursive tree...
Collected from the Internet
Please contact [email protected] to delete if infringement.
edited at
Related
Related Related
- 1
How does this recursive binary codes function work?
- 2
How does this interleaving recursive function work?
- 3
How does a recursive function with two recursive calls work?
- 4
How does this recursive array permutation function work under the hood?
- 5
How does a recursive function to find the minimum element of an array work?
- 6
How does this recursive code work?
- 7
How does `for` work in this recursive Clojure code?
- 8
How does this recursive SQL CTE work exactly?
- 9
How does recursive CTE work with example in the doc?
- 10
How does (co)recursive definition work in Haskell?
- 11
How does recursive of number sum work in java?
- 12
How does (co)recursive definition work in Haskell?
- 13
How does this recursive construction of a class work?
- 14
How does recursive of number sum work in java?
- 15
mathematic induction, how to prove that this work in this recursive function
- 16
Understanding how stack frames work in recursive function
- 17
mathematic induction, how to prove that this work in this recursive function
- 18
How does recursive function in C works
- 19
Recursive function using lambda's, why does this not work?
- 20
Why does not my recursive friend function work in VB6?
- 21
Recursive subtraction does not work
- 22
template work as recursive function
- 23
How does this isPrime function work?
- 24
How does this function/variable work?
- 25
How does function [x] -> ... work
- 26
How does the function pow work?
- 27
How does the GetBytes function work?
- 28
How does [ ] work in a function in Clojure?
- 29
How does the `[<-` function work in R?
Comments