Bifalgorithm post · Computer science one · Recursion

How can recursion be made tail-recursive in C?

How can recursion be made tail-recursive in C? (Computer science one · Recursion) — "This example was not tail-recursive as the recursive call was not the fina…

Ideas in this flowchart

Recursive C functions: tail-recursive summation and naive Fibonacci
Tail-recursive summation with recSumTail
The original summation example is not tail-recursive because the sum occurs after the recursive call
The accumulated sum is passed through each call before the recursive call
When i equals size, the function returns sum
Otherwise, the function calls recSumTail with i+1 and sum + arr[i]
Naive recursive Fibonacci implementation
For negative n, fibonacci returns 0
For n less than or equal to 1, fibonacci returns 1
For larger n, fibonacci returns fibonacci(n-1) + fibonacci(n-2)

Bifalgorithm

Feed/

How can recursion be made tail-recursive in C?

No cover

Channel

Computer science one

1 page

sam23

Ebook2w

"This example was not tail-recursive as the recursive call was not the final operation (the sum was the final operation). To make this function tail recursive, we can carry the summation through to each function call ensuring that the summation is done prior to the recursive function call.\n\nint recSumTail(const int *arr, int size, int i, int sum) {\n\nif(i == size) {\n\nreturn sum;\n\n} else {\n\nreturn recSumTail(arr, size, i+1, sum + arr[i]);\n\n}\n\n}\n\nAs a final example, consider the following C implementation of the naive recursive Fibonacci sequence. An additional condition has been included to check for “invalid” negative values of n for which zero is returned.\n\nint fibonacci(int n) {\n\nif(n < 0) {\n\nreturn 0;\n\n} else if(n <= 1) {\n\nreturn 1;\n\n} else {\n\nreturn fibonacci(n-1) + fibonacci(n-2);\n\n}\n\n}"

Flowchart preview

👍

0 comments0 shares